二叉树的相关性质
二叉树性质
结点的总个数=总度数+1
在图中我们可以看出
对于任意一个结点
这个结点的度=这个结点的连线数量=这个结点的下一层结点数量
在经过我们处理之后可以发现根节点是没有对应的这就是1的来源
度为0的结点个数为度为2的结点个数+1
设非空二叉树中
- 度为0的结点个数$n_0$
- 度为1的节点个数$n_1$
- 度为2的节点个数$n_2$
当二叉树的总结点个数为$n$时，可以由
- 结点的总个数=度为0的结点个数+度为1的节点个数+度为2的节点个数
- 结点的总个数=总度数+1
得到以下两个式子
- $n=n_0+n_1+n_2\cdots①$
- $n=0\times n_0+1\times n_1+2\times n_2+1\cdots②$
将①-②得到
$0=n_0-n_2-1\Rightarrow n_0=n_2+1$
所以说
度为0的结点个数为度为2的结点个数+1
叶子结点个数比二分支结点个数多一个
二叉树的第$i$层至多有$2^{i-1}$个结点
可以由以下逻辑数学归纳得到结论
- 对于二叉树的第一层显然最多只能有$1=2^0$个结点
- 第二层由于第一层最多只能有$1=2^0$个结点，而一个结点最多延伸出两个结点（两个度），所以第二层最多只能有$2^1$个结点
- 第三层由于第二层最多只能有$2=2^1$个结点，而一个结点最多延伸出两个结点（两个度），所以第三层最多只能有$4=2^2$个结点
- 第四层由于第三层最多只能有$2^2$个结点，而一个结点最多延伸出两个结点（两个度），所以第四层最多只能有$2^3$个结点
- $\cdots$
- 第$n$层由于第$n-1$层最多只能有$2^{n-1-1}$个结点，而一个结点最多延伸出两个结点（两个度），所以第$n$层最多只能有$2^{n-1}$个结点
高度为$h$的二叉树至多有$2^h-1$个结点 （高度为$h$的$m$叉树至多有$\frac{m^h-1}{m-1}$个结点）
下证高度为$h$的$m$叉树至多有$\frac{m^h-1}{m-1}$个结点
高度为$h$的$m$叉树最多有$h$层
- 对于第一层我们知道最多只能有$m^0$个结点
- 对于第二层我们知道最多只能有$m^1$个结点
- 对于第三层我们知道最多只能有$m^2$个结点
- $\cdots$
- 对于第$h$层我们知道最多只能有$m^{h-1}$个结点
我们想要计算高度为$h$的$m$差数至多有多少个结点本质上就是计算下面的等比数列
这是一个首项$a_0$为$m^0$的,公比$q$为$m$的,项数$n$为$h$的等比数列
我们知道等比数列的前$n$项和公式为
我们将数值代入后计算得到$\frac{1-m^h}{1-m}$
特别地对于二叉树我们可以进一步化简得到$\frac{1-2^h}{1-2}=2^h-1$
对于有$n$个结点的完全二叉树高度为$\lceil log_2(n+1)\rceil$这里的符号$\lceil\rceil$为向上取整符号
假设现在有一个高度为$h$的完全二叉树
我们知道完全二叉树的结点是有顺序的（在第$n$层未满时不会出现第$n+1$层）
我们知道高度为$h$的完全二叉树结点个数最多应该为$2^h-1$个
我们也知道高度为$h-1$的完全二叉树结点个数最多为$2^{h-1}-1$个
那么对于高度为$h$的完全二叉树的结点个数就应该比$h-1$层的最大结点个数来得多($\gt$) 比$h$层的最大结点个数来的小或者等于($\leq$) 写成数学不等式即为
两边同时$+1$
两边同时取2的对数
那么对于高度为$h$的结点数为$n$的完全二叉树
| $n$ | $log_2(n+1)$ | $h$ |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1.5850 | 2 |
| 3 | 2 | 2 |
| 4 | 2.3219 | 3 |
我们可以看出现在的$h$其实就是$log_2(n+1)$向上取整
所以对于结点数为$n$的完全二叉树它的高度应该为$\lceil log_2(n+1)\rceil$
对于完全二叉树可以由结点个数推出$n_0,n_1,n_2$(这里的下标代表度)
由于完全二叉树在第$n$层未满的情况下不会有$n+1$层
完全二叉树的度为1的结点只有两种情况
- 0 此时为最后一个结点正好和上一个结点一起被连接到同一个父结点上
- 1 此时最后一个结点独自一人连接到父节点上
对于第一种情况
- 假设当前一共有$h$层
- 那么前$h-1$层是满的
- 此时前$h-1$层一共有$2^{h-1}-1$个结点 (这一定是一奇数)
- 对于第$h$层的结点个数一定是偶数 (因为此时为最后一个结点正好和上一个结点一起被连接到同一个父结点上)
- 所以在这种情况下结点总数一定是奇数 （奇数+偶数=奇数）
对于第二种情况
- 假设当前一共有$h$层
- 那么前$h-1$层是满的
- 此时前$h-1$层一共有$2^{h-1}-1$个结点 (这一定是一奇数)
- 对于第$h$层的结点个数一定是奇数 (因为此时最后一个结点独自一人连接到父节点上)
- 所以在这种情况下结点总数一定是偶数 （奇数+奇数=偶数）
同时我们知道$n_0=n_2+1$
- 当$n_0$为奇数时，$n_2$一定为偶数
- 当$n_2$为奇数时，$n_0$一定为偶数
- 并且保持$n_0$的个数比$n_2$多1
现在如果有$2k$（偶数）个结点
我们可以马上确定$n_1=1$
同时有以下两个等式
- $n_0=n_2+1$
- $n_0+n_1+n_2=2k\Rightarrow n_0+n_2=2k-1$
联立两个式子后可以求出
现在如果有$2k-1$（奇数）个结点
我们可以马上确定$n_1=0$
同时有以下两个等式
- $n_0=n_2+1$
- $n_0+n_1+n_2=2k\Rightarrow n_0+n_2=2k-1$
联立两个式子后可以求出