企业官网建设流程全解析

第三章 二叉树

前言

大家好！今天让我们来一起了解一下二叉树的知识～
不知道大家在第一次看到“树🌲”这个字的时候有没有好奇，它为什么叫树？和树有什么关系？这里的树指什么？哈哈，今天就为大家讲解，现在让我们开始吧！

一、树型结构

1.“树”是什么？

树是⼀种非线性的数据结构，它是由n（n>=0）个有限结点组成⼀个具有层次关系的集合。
把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 有⼀个特殊的结点，称为根结点，根结点没有前驱结点(就是第一个节点前面没有东西了～

• 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、…、Tm，其中每⼀个集合Ti(1 <= i <= m) 又是⼀棵与树类似的⼦树。每棵子树的根结点有且只有⼀个前驱，可以有0个或多个后继

• 树是递归定义的。
  注意：树形结构中，⼦树之间不能有交集，否则就不是树形结构
  就像图中的5，是不可能和2，3同时连接的！

2.概念

这些很重要，无论是选择题还是oj题经常有他们的身影～

• 结点的度：⼀个结点含有子树的个数称为该结点的度； 如图：A的度为3
• 树的度：⼀棵树中，所有结点度的最大值称为树的度； 如图：树的度为3
• 叶子结点或终端结点：度为0的结点称为叶结点； 如上图：E,F,C,D这些节点为叶结点
• 双亲结点或父结点：若⼀个结点含有子结点，则这个结点称为其子结点的父结点； 如图：A是B的父结点
• 孩子结点或子结点：⼀个结点含有的子树的根结点称为该结点的子结点； 如图：B是A的孩子结点
• 根结点：⼀棵树中，没有双亲结点的结点；如上图：A
• 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
• 树的高度或深度：树中结点的最⼤层次； 如图：树的⾼度为3

树的以下概念只需了解，在看书时只要知道是什么意思即可：

• ⾮终端结点或分支结点：度不为0的结点； 如上图：A，B为分⽀结点
• 兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C、D是兄弟结点
• 堂兄弟结点：双亲在同⼀层的结点互为堂兄弟;
• 结点的祖先：从根到该结点所经分支上的所有结点；如图：A是所有结点的祖先
• 子孙：以某结点为根的子树中任⼀结点都称为该结点的子孙。如上图：所有结点都是A的⼦孙
• 森林：由m（m>=0）棵互不相交的树组成的集合称为森林（大自然的力量）

3.树的表示形式

相信大家从刚刚的概念中就能看出树的亲戚有很多——
所以！🎄的表示方法也有很多。
双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。
看到这么多先不要闹心！很简单，这里让我们先从孩子兄弟表示法来了解一下～

classNode{intval;Nodechild;Nodebrother;}

怎么样？这样一看就简单了不少吧～
读到这里，大家会不会有个疑惑——标题明明是“二叉树”，为什么文章一直揪着这棵“🎄”不放？别急，它来啦～

二、二叉树

1.概念

⼆叉树是结点的⼀个有限集合，该集合：

1. 或者为空
2. 或者是由⼀个根节点加上两棵别称为左子树和右子树的⼆叉树组成。

也就是要么什么都没有（空树），要么一个节点上，或是不叉东西，或是最多叉两个，而插上的这些节点都可以和它父节点一样按规则继续延伸，就像是递归一样，看图更好理解～

总结一下，从上图可以看出：

1. ⼆叉树不存在度大于2的结点
2. ⼆叉树的子树有左右之分，次序不能颠倒，因此⼆叉树是有序树
   

2.特殊的二叉树

1.满⼆叉树:
⼀棵⼆叉树，如果每层的结点数都达到最⼤值，则这棵⼆叉树就是满⼆叉树。
也就是，每个节点每一层有位置的地方都插上了！则它就是满⼆叉树。

2.完全⼆叉树:
完全⼆叉树是效率很⾼的数据结构，是由满⼆叉树⽽引出来的。
对于深度为K的，有n个结点的二叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是⼀种特殊的完全⼆叉树。

说人话就是从上到下从左到右依次放，一个萝卜一个坑，每一层两个相邻节点之间没有空位！
就像图中的7，不可以放到3的右边，也就是3的右子树，不然那左边空着

3.二叉树的性质

1. 若规定根结点的层数为1，则⼀棵非空⼆叉树的第i层上最多有2^（i-1）(i>0)个结点
2. 若规定只有根结点的二叉树的深度为1，则深度为K的⼆叉树的最大结点数是(2^k)－1(k>=0)
3. 对任何⼀棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1
4. 具有n个结点的完全⼆叉树的深度k为上取整
5. 对于具有n个结点的完全⼆叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
   若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
   若2i+1<n，左孩子序号：2i+1，否则无左孩子
   若2i+2<n，右孩子序号：2i+2，否则无右孩子

4.二叉树的存储

二叉树的存储结构分为：顺序存储和类似于链表的链式存储。
二叉树的链式存储是通过⼀个⼀个的节点引用起来的，常见的表示方式有二叉和三叉表示方式

题里面经常是这样的！

classNode{intval;// 数据域Nodeleft;// 左孩⼦的引⽤，常常代表左孩⼦为根的整棵左⼦树Noderight;// 右孩⼦的引⽤，常常代表右孩⼦为根的整棵右⼦树}

5.二叉树的遍历

二叉树大多是从根节点开始，从上到下，从左到右来~

• NLR：前序遍历(Preorder Traversal 亦称先序遍历)⸺访问根结点—>根的左子树—>根的右子树。

人话：就是按正常的遍历，现走到的现打印出来，后走到的后打印

• LNR：中序遍历(Inorder Traversal)⸺根的左子树—>根节点—>根的右子树。

人话：就是按正常走，把自身节点下面的左子树都走完后，在遍历自己的右树之前打印出来

• LRN：后序遍历(Postorder Traversal)⸺根的左子树—>根的右子树—>根节点。

人话：和前序遍历相反，自身节点要在本身的左树和右树都遍历完之后才能打印

※二叉树的层序遍历相当于广度优先遍历，前序遍历相当于深度优先遍历

三、一些题

这个是在刷题题软件上看到的

已知一棵完全二叉树的第6层（设根为第1层)有8个叶结点，则该完全二叉树的结点个数最多是()。
A.39
B.52
C.111
D.119

答案：111。这里问最多有多少，那就证明第六层并不是最后一层，有第七层，而第六层有8个叶子结点，证明第七层比满二叉树第七层少了16个，结合递增公式可得2^7-1-16=111

力扣题：二叉树的中序遍历

总结

本章主要讲了树和二叉树的结构概念以及表现形式，还有两个特殊的二叉树——满二叉树和完全二叉树的存储方式，遍历等等。
大家后续可以在力扣上面找点题做，如果发现不会的话也不要着急，很正常，多做点捋一捋思路慢慢就好了，一定补药焦虑啊喂！
虽然小编目前也有点吐血了，但一起加油叭！

对了，小编的学校最近让弄一个项目出来，就是带着网页能点击的那种，小编在接下来一周会继续发数据结构的题，偶尔会穿插着发一些关于vibe coding的文章，希望能让我们再次相遇！