【大话数据结构】第六章总结——树（中）
目录
前言
有一段时间没继续写《大话数据结构》了，说到底还是因为懒！
由于树的知识点太多了，所以我分三部分来总结，下面进入二叉树环节！！
（如果忘记之前的内容，可以点击右边直达【大话数据结构】第六章总结——树（上））
二叉树
在上一部分，最后提到了用孩子兄弟表示法可以形成一棵二叉树，那么什么是二叉树呢？先看图再看含义
这是一棵二叉树
这也是一棵二叉树
同理，这也是二叉树
从图上可以发现一个特点，二叉树中树的度最大为2，下面看一下二叉树的解释
二叉树：
二叉树（Binary Tree）是n（n ≥ 0）个结点的有限集合，该集合或者为空集（称为空二叉树），
或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
其实直接看解释或许有点懵，不过我们可以根据它的特点出发，帮助我们理解
二叉树的特点：
- 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。
（注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的）
- 左子树和右子树是有顺序的，次序不能任意颠倒。
- 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。例如下图中是两棵不同的二叉树
如果一棵二叉树由三个结点组成的话，那么这棵二叉树有几种形态呢？（建议先自己想一想，或者在纸上画一下再往下看）
。
。
。
。
。
就当你已经在大脑中想了一遍了，下面公布答案
总共有5种，不知道你是否答对了，答对的话继续往下看吧，答错或者答漏的话可以继续看看上图，应该不难理解。
特殊二叉树：
在数据结构中，总是会有一些特例，二叉树也不例外
斜树：
像上图中，所有结点都只有左子树的二叉树叫左斜树；所有结点都只有右子树的二叉树叫右斜树
左斜树跟右斜树统称为斜树。
它的特点就是每一层只有一个结点，类似线性表（线性表可以理解为树的一种极其特殊的表现形式）
满二叉树：
如上图所示，可以发现，这样的二叉树每个分支结点都存在左右子树（叶子除外），叶子呢都在同一层，这种二叉树称为满二叉树。
满二叉树的特点有：
1. 叶子只出现在最下一层
2. 非叶子结点的度一定为2
3. 在同样深度的二叉树中，满二叉树结点个数最多，叶子数最多
完全二叉树：
上面这些都是完全二叉树，你没看错，第三张图也是完全二叉树。有人懵了，这不是满二叉树吗？
难点来了，“满”跟“完全”这两种类型的二叉树中，第二种是比较难理解的，先看一下比较官方的解释
对一棵具有n个结点的二叉树按层序编号，如果编号为i（1 ≤ i ≤ n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树
这上面的解释估计看晕了不少人，还是我来解释一下吧
完全二叉树呢，其实是建立在满二叉树的基础上的，具体而言就是在满二叉树右下角的地方开始往左边依次砍n个结点后形成的即为完全二叉树！看图理解吧
如上图所示，在满二叉树右下角往左边依次砍掉1个结点后，就变成了完全二叉树
同理，在满二叉树右下角往左边依次砍掉2个结点后，就变成了完全二叉树
当砍掉0个结点后，也是一棵完全二叉树，只是这时也是一棵满二叉树
（注意：从上图可以得知满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树）
下面这些二叉树就不是完全二叉树了！
上图中，没有依次砍掉结点
上图中也是一样，如果要砍掉第三层（从上往下数第三层）的结点，那么一定要把第四层的结点都砍掉形成一棵满二叉树，才能砍第三层
即如下图所示才是完全二叉树
再次回忆一下完全二叉树吧
完全二叉树呢，其实是建立在满二叉树的基础上的，具体而言就是在满二叉树右下角的地方开始往左边依次砍n个结点后形成的即为完全二叉树！
记住几个关键点：满二叉树、右下角开始、依次往左
完全二叉树的特点：
1. 叶子结点只能出现在最下两层
2. 最下层的叶子一定集中在左部连续位置
3. 倒数二层，若有叶子结点，一定都在右部连续位置
4. 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况
5. 同样结点数的二叉树，完全二叉树的深度最小
二叉树的性质：
1. 在二叉树的第i层上至多有2 ^ （i - 1）个结点（i ≥ 1）
2. 深度为k的二叉树至多有2 ^ k - 1个结点（k ≥ 1）
3. 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1
4. 具有n个结点的完全二叉树的深度为⌊log2n⌋ + 1（⌊x⌋表示不大于x的最大整数）
5. 如果对一棵有n个结点的完全二叉树（其深度为⌊log2n⌋ + 1）的结点按层序编号（从第1层到第⌊log2n⌋ + 1层，每层从左到右），对任一结点i（1 ≤ i ≤ n）有：
- 如果i = 1，则结点i是二叉树的根，无双亲；如果i ＞ 1，则其双亲是结点⌊i / 2⌋
- 如果2i ＞ n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i
- 如果2i + 1 ＞ n，则结点i无右孩子；否则其右孩子是结点2i + 1
前4点性质中，其实不难理解，建议大家可以通过画图来证明以上性质，加深记忆。
第5点性质可能不好理解，我们以下图为例加以说明，下图是一棵完全二叉树，深度为4，结点总数为10
5.1 如果i = 1，则结点i是二叉树的根，无双亲；如果i ＞ 1，则其双亲是结点⌊i / 2⌋
对于性质5的第一条来说，这是很显然的，因为i = 1时就是根结点。
i > 1时，比如结点5，那么它的双亲就是⌊i / 2⌋，也就是⌊5 / 2⌋ = 2，
结点9，它的双亲就是⌊i / 2⌋，也就是⌊9 / 2⌋ = 4
5.2 如果2i ＞ n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i
对于性质5的第二条来说，比如结点7，因为2 × 7 = 14超过结点总数10，所以结点7没有左孩子
同理，对于结点5，因为2 × 5 = 10等于结点总数10，所以它的左孩子是结点2i，也就是2 × 5 = 10结点
5.3 如果2i + 1 ＞ n，则结点i无右孩子；否则其右孩子是结点2i + 1
对于性质5的第三条，比如结点5，因为2 × 5 + 1 = 11，大于结点总数10，所以它没有右孩子
同理，结点3，因为2 × 3 + 1 = 7，小于结点总数10，所以它的右孩子是结点7
总结
这就是《大话数据结构》第六章树的中篇啦，如果有不懂的地方，欢迎在下方留言评论。
一个人有了目标，如果因为懒惰而不去执行，那么这个目标很快就废了
就像写博客一样，如果一直保持一个月几篇博客，突然某个月因为懒而没有坚持写，那么就很难继续坚持下去了
所以为了避免出现这种情况，我得马上行动！不要给自己找那么多借口！坚持写博客，利己利他！