当初我要是这么学习二叉树就好了「附图文解析」_二叉树初级学习

1. 树形结构

1.1 概念(了解)

树不再是顺序表, 链表, 栈, 队列那样一对一的线性结构. 而树则是一种一对多的数据结构, 由n(n>=0)个互不相交有限节点组层有层次关系的集合.
特点如下:

• 有一个特殊的节点, 称为根节点, 根节点没有前驱节点
• 除根节点外, 其余节点被分成M(M > 0)个互不相交的集合T1, T2, …, Tm，其中每一个集合 <= m) 又是一棵与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有0个或多个后继
• 树是递归定义的[树的定义中用到了树的概念]

错误的二叉树 D和E不应该相交, I节点有两个父节点

正确的树:

1.2 概念(重要)

用的是上图中正确的二叉树来解释概念

1. 节点的度: 一个节点含有的子树的个数称为该节点的度[A的度就是2]

2. 非终端节点或分支节点:度不为0的节点[A, B, C, D, E]
   

3. 树的度: 一棵树中，最大的节点的度称为树的度; 如上图:树的度为3

4. 叶子节点或终端节点: 度为0的节点称为叶节点; 如上图:G、H、I、J节点为叶节点

5. 双亲节点或父节点: 若一个节点含有子节点，则这个节点称为其子节点的父节点; 如上图:A是B的父节点

6. 孩子节点或子节点: 一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点

7. 兄弟节点: 具有相同父节点的节点互称为兄弟节点[B和C, E和F, G, H和I]

8. 堂兄弟节点: 双亲在同一层的节点互称为堂兄弟节点[D和E, D和F]

9. 节点的祖先: 从根到该节点的所有分支经历所有节点[A]

10. 根结点: 一棵树中，没有双亲结点的结点;如上图:A

11. 森林: 由m(m>=0)棵互不相交的树的集合称为森林
    

12. 节点的层次: 从根开始定义起，根为第1层，根的子节点为第2层，以此类推

13. 树的高度或深度: 树中节点的最大层次; 如上图:树的高度为4
    

1.3 树的表示形式

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如:双亲表示法、孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法【在线OJ常考的就是这种表示形式】

class Node {
    int value;// 树中存储的数据
    Node child;// 第一个孩子引用
    Node brother;// 下一个兄弟引用
}
1
2
3
4
5

1.4 树的应用

文件系统管理(目录和文件)

2. 二叉树(BinaryTree重点)

2.1 概念

我们从经典的猜数字游戏开始, 由浅入深介绍二叉树.
在100以内猜数字, 最多几次可以猜对呢?答案是:7
下面是根据每次猜的大小来构建二叉树


我们发现利用这个大小关系来查找指定范围内某个数字, 效率不是高的一丁半点. 因此对于这种具有对立关系的情况: 0和1, 真与假, 上与下, 正与反, 对与错都适合用树来建模. 这种特殊的树状结构称为二叉树

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
特点:

1. 每个节点最多有2颗子树, 即不存在度大于2的节点
2. 二叉树有左右子树之分, 次序不能颠倒, 因此二叉树也是一颗有序树

2.2 二叉树的5种基本形态

1. 空二叉树
2. 只有一个根节点
3. 根节点只有左子树
4. 根节点只有右子树
5. 根节点即有左子树又有右子树
   

2.3 两种特殊的二叉树

2.3.1 斜树

顾名思义, 斜树一定要是斜的, 往哪儿斜也是有讲究的.所有的节点都只有左子树叫做左斜树; 所有的节点都只有右子树叫做右斜树
左斜树:

右斜树:

斜树有明显特点: 每一层都只有一个节点, 结点个数和树的深度相同.

有些同学就奇怪了: 这也能叫树吗, 这不是我们熟悉的线性表吗?
解释: 对的, 线性表结构可以理解为树的一种极其特殊的表现形式

2.3.2 满二叉树

在一棵二叉树中, 如果所有分支结点都存在左子树和右子树, 并且所有叶子节点都在同一层上, 这样的二叉树称为满二叉树

它的样子看得很美, 很匀称

满二叉树特点:

1. 叶子结点只能出现在最下一层, 出现在其它层就不可能达到平衡
2. 非叶子结点的度一定是2, 否贼就是"缺胳膊少腿"
3. 在同样深度的二叉树中, 满二叉树结点个数最多, 叶子结点最多

2.3.3 完全二叉树

把一颗具有 n 个节点的二叉树按层序编号, 编号i(<1=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中所在位置完全相同

这是一种有些难以理解的特殊二叉树
首先从字面上理解区分, "满"和"完全"的差异: 满二叉树一定是一颗完全二叉树, 但是完全二叉树不一定是一颗满二叉树
什么是按层序编号?
上图中就是按照从上到下, 从左到右一次按照1, 2, 3, …, n的序号

完全二叉树特点:

1. 叶子结点只能出现在最下两层
2. 最下层的叶子结点一定集中在左部连续位置
3. 倒数第二层, 如果有叶子结点, 一定都在右部连续位置
4. 如果结点的度为1, 则该节点只有左孩子, 即不存在只有右子树的情况
5. 同样结点数的二叉树, 完全二叉树的深度最小

从上面的列子中, 也给了我们一个判断某二叉树是否为完全二叉树的办法: 看着二叉树的示意图, 心中默默给每个节点按照满二叉树的结构逐层顺序编号, 如果编号出现了空档, 就说明不是完全二叉树否则就是完全二叉树

2.4 二叉树的性质

2.4.1 第i层结点个数

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^i-1(i>0)个结点

2.4.2 树的所有最大点个数

若规定根节点的层数为1，则深度为K的二叉树最大节点数是 2^k-1(k>0)个结点

2.4.3 叶子结点和非叶子结点数量关系

对任何一棵二叉树, 如果其叶结点个数为 n₀, 度为2的非叶结点个数为 n₂,则有n₀=n₂+1[最下一层的叶子结点个数=上面的所有非叶子结点个数+1]

2.4.4 根据结点求树深度

具有n个节点的二叉树的深度K为log₂ⁿ+1向上取整

2.4.5 父子结点编号关系

对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有:

• 若i>0，双亲序号:(i-1)/2;
• 若i=0，i为根节点编号，无双亲节点
• 若2i+1<n，左孩子序号:2i+1，否则无左孩子
• 若2i+2<n，右孩子序号:2i+2，否则无右孩子
  这个规律很重要, 涉及到堆排, 二叉搜索树需要用到这个规律

2.4.6 小练兵

设一棵完全二叉树中总共有1000个节点, 则该二叉树中 500 个叶子节点, 500个非叶子节点, 1个节点只有左孩子, 0个只有右孩子.

500个叶子结点计算步骤

1. 叶子结点总个数=第10层叶子结点个数+第9层叶子结点个数
   有同学会想: 为何第9层会有叶子结点呢?
   解释: 因为我们发现此树共有 1000 个结点, 而满二叉树的话会有 2^10-1 个结点, 所以说明 第10层没满, 第9层一定有叶子结点

有了这个理解后再做进一步的计算

2. 第10层全是叶子结点个数: 树的总结点个数 - 9层及以上所有结点个数
   因为是一颗完全二叉树, 所以可以保证第9层一定是满二叉树
   算式: 1000-(2⁹-1)–>1000-511=489

现在我们还差第9层的叶子结点个数

3. 第9层叶子结点个数: 第9层结点个数 - 第10层父节点个数
   算式: 2^9-1-第10层父节点个数

最后的问题就是求第10层父节点个数

4. 第10层父节点个数求法
   如果结点个数n是偶数, 则其父结点个数为 n/2
   如果结点个数n是奇数, 则其父结点个数n/2+1
   在第一步中我们求得了第10层节点个数, 求第10层父节点个数就是: 489/2 + 1–>245
5. 现在可以计算第 3 步得出第9层叶子结点个数:
   2^(9-1)-245–>256-245=11
6. 现在可以计算第 1 步中的所有整棵树的叶子结点;
   第 10 层结点数 + 第 9 叶子结点数: 489+11 = 500
7. 有了叶子结点个数, 很容易知道非叶子节点
   总结点个数-叶子结点个数: 1000-500
8. 由于完全二叉树第10层结点个数为489, 为奇数, 所以一定有1个节点只有左孩子, 有 0 个节点只有右子树

将一颗有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根节点编号为 1 ，则编号为 98 的节点的父节点编号为: (98-1)/2 = 48

设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是: 中序遍历

将一棵二叉树的根结点放入队列，然后递归的执行如下操作，将出队结点所有子结点加入队。以上操作可以实现层序遍历.

n个节点的完全二叉树，最多可以有多少层: log₂^N+1上取整

2.5 二叉树的存储

2.5.1 顺序存储

二叉树的顺序存储就使用一维数组存储二叉树中的节点并且存储的位置应该要能体现节点之间的逻辑关系, 比如孩子双亲, 左右兄弟节点

2.5.1.1 完全二叉树的形式存储

将这颗二叉树存储数组中, 相应的下标对应其相等的位置

这下看出完全二叉树的优越性了吧, 由于它定义的严格, 所以顺序结构也能表现出二叉树的结构来

2.5.1.2 一般树的形式存储

对于一般二叉树而言, 层序编号不能反映逻辑关系, 但是可以按照完全二叉树编号, 只不过把不存在的结点设施为 ‘^’ 而已.浅色节点代表不存在

考虑一下极端情况: 又斜树【左斜树】

一颗深度为 k 的右斜树, 只有 k 个节点, 却需要分配 2^k-1 个存储单元, 这显然是对存储空间的浪费. 所以顺序存储只适用于完全二叉树

2.5.2 链式存储

既然顺序存储适应性不强, 我们就要考虑链式存储结构. 二叉树每个节点最多有两个孩子, 所以设计一个数据域和两个指针域比较理想. 这就是二叉链表
孩子表示法

class Node {
    int val;// 数据域
    Node left;// 左孩子的引用，常常代表左孩子为根的整棵左子树
    Node right;// 右孩子的引用，常常代表右孩子为根的整棵右子树
}
1
2
3
4
5

孩子双亲表示法主要用在在平衡树，本文采用孩子表示法来构建二叉树, 大多数的在线OJ题目也都采用的这种方法来构建二叉树.

3. 二叉树由浅入深解析

3.1 遍历二叉树

3.1.1 二叉树遍历原理

导言: 假设有20张100元的和2000张1元的奖券, 同时撒向了空中, 大家比赛看谁最中间的最多.

相信同学都会说: 先捡100元的. 道理非常简单, 因为捡1张100元的等于捡100张1元的, 效率好的不是一点点

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/923223