二叉树的性质总结（含讲解/应用习题）
二叉树的性质总结（含讲解/应用习题）
在深入探讨二叉树的性质之前，我们需要先了解一些基本的树的概念和术语。
二叉树的基本性质
1. 第k层的最大节点数
若规定根节点的层数是1，则第k层最大节点数为 (2^{(k-1)})。
2. 一个树的总节点数
如果规定根节点为树的第一层，那么深度为k的树的总结点数为 (2^k - 1)。
3. 叶子节点与度为2的节点的关系
对于任意一颗二叉树，如果叶子节点数为a，度为2的节点数为b，那么一定有：a = b + 1。也就是说，度为0的节点永远比度为2的节点多一个。
4. 完全二叉树的深度计算
具有n个结点的完全二叉树的深度k为 (\lceil \log_2(n+1) \rceil)（向上取整）。
公式推导理解
为了方便记忆，我们可以将求完全二叉树深度的问题简化为求满二叉树的深度。以一个深度为4的完全二叉树为例：
根据性质3，我们知道：
- 深度k = 4
- 总节点数n = (2^k - 1 = 17)
将公式变形：
[2^k = n + 1]
使用对数知识求深度k：
[k = \log_2(n+1)]
这个公式只能求出满二叉树的深度。对于非满的完全二叉树，例如在上述树中添加一个节点使其深度变为5：
此时节点数变为18，带入公式：
[k = \log_2(19)]
显然，k是一个非整数且大于4，因此需要向上取整：
[深度 = \lceil 4 + 1 \rceil = 5]
5. 双亲节点和左右孩子节点的求法（数组存储方式）
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
- 若i > 0，双亲节点的序号为 (\frac{i-1}{2})
- 若i == 0，则该节点为根节点，没有双亲节点
- 若2i+1 < n，左孩子节点的序号为2i+1，否则第i个节点没有子节点
- 若2i+2 < n，右孩子节点的序号为2i+2（其实就是左孩子节点序号+1），否则第i个节点没有右孩子节点
应用习题
- 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A. 不存在这样的二叉树
B. 200
C. 198
D. 199
答案：B
解析：
根据性质3，套用公式即可得出答案。
- 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A. n
B. n+1
C. n-1
D. n/2
注意：n是非负整数
答案：A
解析：
因为n是非负整数，所以这颗二叉树的节点数一定是偶数。通过对比偶数和非偶数个节点的完全二叉树，可以发现偶数个节点的完全二叉树中，度为1的节点有且仅有一个。根据二叉树节点总数的计算公式：
[n0(度==0的节点数) + n1(度==1的节点数) + n2(度==2的节点数) = 2n]
由叶子节点和度为2的节点数目关系可得：
[2n = n1 + (n1 - 1) + 1]
[n1 = n]
所以答案是A。
- 一棵完全二叉树的节点数为531个，那么这棵树的高度为（ ）
A. 11
B. 10
C. 8
D. 12
答案：B
解析：
直接套用求深度的公式即可得出答案。