学习二叉树，完全二叉树，完全二叉树的规律

目录

• 树的基本术语
  • 结点 与 叶子结点
  • 深度 与 高度 与 度
• 二叉树
• 满二叉树
• 完全二叉树
• 完全二叉树的应用
• 数学学习时间
  • 满二叉树的总结点数与层结点的关系
  • 完全二叉树的编号问题

树的基本术语

结点 与 叶子结点

结点就是树的一个节点，叶子结点是指度为0的结点，即没有分支的结点。

深度 与 高度 与 度

对于某个结点，深度是指结点从根结点到自己的层数（根结点深度为1），高度是指结点所在的最长路径的叶子结点到自己的层数（叶子结点高度为1），度是指结点的儿子分支数。

对于整棵树，最深的叶子结点的深度是树的深度，树根的高度是树的高度，结点中最大的度是树的度。（可见，整棵树的深度和高度是相等的）。

如图：
根结点：深度为1，高度为4，度为2。
A 结点：深度为2，高度为3，度为2。
B 结点：深度为4，高度为1，度为0。
整棵树：深度为4，高度为4，度为2。

小结：

1. 空树，深度是1，根结点的度是0度。
2. 像上面的满二叉树，深度是2，根结点的度是2度，两个叶结点的度是0度。
3. 结点的深度和高度不一定相同，很容易理解，深度是从上而下，高度是自底向上。
4. 整棵树而言，深度和高度相等。

二叉树

每个结点最多有两个儿子的特殊的树。

二叉树的应用范围很广，一颗多叉树可以转换为二叉树。

满二叉树

顾名思义，满二叉树是每个结点都有两个儿子的特殊的二叉树。

满二叉树：深度为n，则有2^n - 1个结点，深度为n的层，则有2^(n - 1)个结点。

完全二叉树

如果二叉树除了最后一层有缺失外，其它是满的，且最后一层缺失的叶子结点只出现在右侧，则这样的二叉树叫完全二叉树。定义是：若二叉树的深度为n，除第n层外，其余各层的结点都达到了最大，且第n层的结点都连续集中在最左边。简而言之，就是从左到右结点是连续不断的二叉树就叫完全二叉树。满二叉树是特殊的完全二叉树。

完全二叉树：

1. 完全二叉树只有最后一层右侧可能出现缺失。
2. 度为1的结点最多有一个（二叉树结点的度最多为2，缺1个就是1度，缺2个就是0度）。
3. 右子树的深度为h，则左子树的深度必为h或h+1（完全二叉树只可能右侧缺失）。

完全二叉树规律：

1. 深度(高度)为n的完全二叉树，最多有2^n - 1个结点，因为最多是满二叉树。
2. 反过来，如果完全二叉树有N个结点，那么深度（高度）最多为log(2)N，（能简写为logN吗？）。（证明：2^n-1 = N）。
3. 完全二叉树的层数 = 深度 - 1，即``
4. 深度为n的层，最多有2^(n-1)个结点（和上面很相似）。（证明：每一层是上一层的2倍）。
5. 总结点数为N，深度为n的结点，其高度为h = log(2)N - n + 1。（深度为1的结点，高度等于树的高度；高度为1的结点，深度等于树的深度）。

像下面这样，从左到右，没有跳过结点，能够连续串起来的二叉树就是完全二叉树：

下面是一些非完全二叉树：

完全二叉树的应用

把完全二叉树从根结点从左到右，依次编号

1. 只要按照编号，存储到一维数组里，就可以通过一维数组的顺序还原一颗完全二叉树（上面的一维数组是：012345）。
2. 若结点的编号为k（k>=0），则该结点的左儿子是2*k+1，右儿子是左儿子加1，即2*k+2（跳跃式访问规律）。
3. 反过来，如果儿子的编号是x，则父结点的编号是(int)(x-1)/2（证明：(int)(2*k+1-1)/2 == (int)(2*k+2-1)/2 == k）。

堆是特殊的完全二叉树，详见《堆》。

数学学习时间

满二叉树的总结点数与层结点的关系

1. 深度为n的层，最多有2^(n-1)个结点。
2. 深度为n的树，总结点数其实是各层求和。

也即是，求结点总和，即是等比数列求和的问题。上面的满二叉树各层的结点数为1 2 4 8 ... 2^(n-1)。

代入等比数列求和公式S = a1 * (1 - q^n) / (1 - q) 即 S = 1 * (1 - 2^n) / (1 - 2)，结果为S = 2^n - 1。

所以，深度为n的满树，总结点数为2^n - 1。

完全二叉树的编号问题

以上是将根结点编号为0的规律，比较符合数组下标以0开始的访问方式。有另外的一些以1开始的规律，虽然不是错的，但是不太适合写代码：

若结点的高度为h，则该结点的左儿子是2*h，右儿子是左儿子加1，即2*h+1。反过来，如果儿子的编号为y，则父结点的编号是(int)x/2。高度h的规律，其实是上面的树的编号从1开始，而不是从0开始。

所以问题也来了，树的编号从0开始，从1开始，从n开始呢，表达式是怎样呢。直观上可以知道，结点和儿子的关系是不变的，变的只是编号，所以应该可以利用其中一个规律推导出编号改变后的表达式。

首先，把完全二叉树用数组的形式表示：
0 开始：0 1 2 3 4 5 6 7…
1 开始：1 2 3 4 5 6 7…
2 开始：2 3 4 5 6 7…

可以看出，总体编号是往左移的。以编号0开始为例，左儿子为x，右儿子为y，当前结点为k，那么规律是x = 2*k + 1和y = 2*k + 2，其中x、y、k都是数组里面的元素。

当以编号1开始时，总体编号相当于往左移动了1位。其中，相当于x往左移动了1位，相当于y向左移动了1位，k也往左移动了1位，因为它们都是数组里面的元素。

设新的关系，左儿子为x1，右儿子为y1，当前结点为k1，那么得到关系x1 - 1 = x、y1 - 1 = y和k1 - 1 = k，代入编号为0的表达式：
x = 2*k + 1 => x1 - 1 = 2*(k1 - 1) + 1 推导出 x1 = 2*k1
y = 2*k + 2 => y1 - 1 = 2*(k1 - 1) + 2 推导出 y1 = 2*k1 + 1。也可以直接使用右儿子 = 左儿子 + 1直接得出。

所以，也即是说，当编号从1开始，结点与儿子结点的关系是x = 2k和y = 2k+1，这和高度h那里得到的表达式一致。

当编号从n开始，就相当于数组往左移动了n位，思路参考上面，和高中数学里移动x、y坐标轴一样（没想到是高中数学）。

学习笔记，仅供参考