Question

二叉树有一些需要理解并记住的特性，以便于我们更好地使用它。

6.6.1　二叉树性质1

性质1：在二叉树的第i层上至多有2^i-1个结点（i≥1）。

这个性质很好记忆，观察一下图6-5-5。

第一层是根结点，只有一个，所以2^1-1=2⁰=1。

第二层有两个，2^2-1=2¹=2。

第三层有四个，2³-1=2²=4。

第四层有八个，2^4-1=2³=8。

通过数据归纳法的论证，可以很容易得出在二叉树的第i层上至多有2

i-1个结点（i≥1）的结论。

6.6.2　二叉树性质2

性质2：深度为k的二叉树至多有2^k-1个结点（k≥1）。

注意这里一定要看清楚，是2^k后再减去1，而不是2^k-1。以前很多同学不能完全理解，这样去记忆，就容易把性质2与性质1给弄混淆了。

深度为k意思就是有k层的二叉树，我们先来看看简单的。

如果有一层，至多1=2¹-1个结点。

如果有二层，至多1+2=3=2²-1个结点。

如果有三层，至多1+2+4=7=2³-1个结点。

如果有四层，至多1+2+4+8=15=2⁴-1个结点。

通过数据归纳法的论证，可以得出，如果有k层，此二叉树至多有2^k-1个结点。

6.6.3　二叉树性质3

性质3：对任何一棵二叉树T，如果其终端结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1。

终端结点数其实就是叶子结点数，而一棵二叉树，除了叶子结点外，剩下的就是度为1或2的结点数了，我们设n₁为度是1的结点数。则树T结点总数n=n₀+n₁+n₂。

比如图6-6-1的例子，结点总数为10，它是由A、B、C、D等度为2结点，F、G、H、I、J等度为0的叶子结点和E这个度为1的结点组成。总和为4+1+5=10。

图6-6-1

我们换个角度，再数一数它的连接线数，由于根结点只有分支出去，没有分支进入，所以分支线总数为结点总数减去1。图6-6-1就是9个分支。对于A、B、C、D结点来说，它们都有两个分支线出去，而E结点只有一个分支线出去。所以总分支线为4×2+1×1=9。

用代数表达就是分支线总数=n-1=n₁＋2n₂。因为刚才我们有等式n=n₀＋n₁＋n₂，所以可推导出n₀＋n₁＋n₂-1=n₁＋2n₂。结论就是n₀=n₂＋1。

6.6.4　二叉树性质4

性质4：具有n个结点的完全二叉树的深度为|log₂n+1|（|x|表示不大于x的最大整数）。

由满二叉树的定义我们可以知道，深度为k的满二叉树的结点数n一定是2^k-1。因为这是最多的结点个数。那么对于n=2^k-1倒推得到满二叉树的深度为k=log₂(n＋1)，比如结点数为15的满二叉树，深度为4。

完全二叉树我们前面已经提到，它是一棵具有n个结点的二叉树，若按层序编号后其编号与同样深度的满二叉树中编号结点在二叉树中位置完全相同，那它就是完全二叉树。也就是说，它的叶子结点只会出现在最下面的两层。

它的结点数一定少于等于同样深度的满二叉树的结点数2^k-1，但一定多于2^k-1-1。即满足2^k-1-1<n≤2^k-1。由于结点数n是整数，n≤2^k-1意味着n<2^k，n>2^k-1-1，意味着n≥2^k-1，所以2^k-1≤n<2^k，不等式两边取对数，得到k-1≤log₂n<k，而k作为深度也是整数，因此k=|log₂n|+1。

6.6.5　二叉树性质5

性质5：如果对一棵有n个结点的完全二叉树（其深度为）的结点按层序编号（从第1层到第层，每层从左到右），对任一结点i（1≤i≤n）有：

1．如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点。

2．如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。

3．如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

我们以图6-6-2为例，来理解这个性质。这是一个完全二叉树，深度为4，结点总数是10。

图6-6-2

对于第一条来说是很显然的，i=1时就是根结点。i>1时，比如结点7，它的双亲就是，结点9，它的双亲就是。

第二条，比如结点6，因为2×6=12超过了结点总数10，所以结点6无左孩子，它是叶子结点。同样，而结点5，因为2×5=10正好是结点总数10，所以它的左孩子是结点10。

第三条，比如结点5，因为2×5+1=11，大于结点总数10，所以它无右孩子。而结点3，因为2×3+1=7小于10，所以它的右孩子是结点7。