c++数据结构8——二叉树的性质

一、二叉树的基本性质

示图1：

性质1：层节点数上限

在一棵二叉树中，第i层至多有2^{i-1}个节点（首层是第1层）

这个性质可以通过数学归纳法证明：

• 第1层：2^{1-1}=2^0=1个节点（根节点）

• 第2层：2^{2-1}=2^1=2个节点

• 第3层：2^{3-1}=2^2=4个节点

• ...

• 第k层：2^{k-1}个节点

例：示图1的第三层最多有4个节点。 

性质2：总结点数上限

深度为k的二叉树至多有2^k-1个节点

这是对性质1的求和结果：
S = 2^0 + 2^1 + 2^2 + ... + 2^{k-1} = 2^k - 1

例：示图1深度为4的二叉树最多有2^4-1=15个节点

性质3：叶子节点与度为2节点的关系

对任意二叉树，叶子节点数n_0和度为2的节点数n_2满足：n_0 = n_2 + 1

证明：

设：

• n：总结点数

• n_0：叶子节点数（度为0）

• n_1：度为1的节点数

• n_2：度为2的节点数

则有：

1. n = n_0 + n_1 + n_2（节点分类）

2. 从边的角度：树的总边数= n - 1

3. 这些边由度为1和度为2的节点产生：n - 1 = n_1 + 2n_2

联立两个方程：
n_0 + n_1 + n_2 = n_1 + 2n_2 + 1
简化得：
n_0 = n_2 + 1

练习：

已知一棵二叉树有10个节点，则其中至多有（ ）个节点有2个子节点
A. 4 B. 5 C. 6 D. 7

解答：
n = n_0 + n_1 + n_2 = 10
由性质3：n_0 = n_2 + 1
代入得：(n_2 + 1) + n_1 + n_2 = 10 → 2n_2 + n_1 = 9
要使n_2最大，则n_1应最小，且n_1必须是奇数（因为2n_2是偶数，9是奇数）
取n_1 = 1，则2n_2 = 8，$n_2 = 4
答案为A

二、特殊二叉树及其性质

1. 满二叉树

定义：每一层的节点数都达到最大值的二叉树

特点：

• 深度为k的满二叉树有2^k-1个节点

• 所有叶子节点都在最底层

编号性质（按层序编号，根节点为1）：

• 节点i的父节点编号： i/2 

• 节点i的左孩子编号：2i

• 节点i的右孩子编号：2i+1

示图：

2. 完全二叉树

示图：

定义：如果有个二叉树(右边)，按照从上到下从左到右的次序对每个结点进行顺序编号，编号为i的结点和满二叉树中编号为i的结点在二叉树中位置相同，则这个二叉树称为完全二叉树。

如何把满二叉树变成完全二叉树？

把一棵满二叉树，从最下层开始，自右向左（连续，不可跳跃）剪掉若干个结点，得到的就是一棵完全二叉树

性质1（深度计算）：n个节点的完全二叉树，如果满足 2^{k-1}≤n<2^k，则深度为k

性质2（节点关系）：

• 若i=1，则为根节点（无父节点）

• 若i>1，则父节点编号为 i/2 

• 若2i > n，则无左孩子，更没有右孩子

• 若 i 结点有左孩子，则左孩子为2i

• 若 i 结点有右孩子，则其右孩子的编号为2i+1

三、典型例题解析

例题1

题目：一棵二叉树如图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1,若某结点的下标为i ,则其左孩子位于下标2i处、右孩子位于下标2i+l处），则该数组的最大下标至少为（ ）

A. 6 B. 10 C. 15 D. 12

解析：答案c,完全二叉树的根据性质1可得。

例题2

题目：根节点深度为 0，一棵深度为 h 的满 k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有（ ）个结点。
A. (k^{h+1}-1)/(k-1) B. k^h-1 C. k^h D. (k^h-1)/(k-1)

解析：
深度为h（根深度0），实际有h+1层。
节点数求和：S = k^0 + k^1 + ... + k^h = {k^{h+1}-1}{k-1}
答案为A

例题3

题目：根高度为1，61个节点的完全二叉树高度为（ ）(2015-17)
A. 5 B. 6 C. 7 D. 8

解析：
设高度为h，则满足：2^{h-1} - 1 < 61 < 2^h - 1
计算可得h=6
答案为B

例题4

题目：5层满二叉树的节点数为（ ）(2014-16)
A. 31 B. 32 C. 33 D. 16

解析：
2^5 - 1 = 31，答案为A

例题5

题目：2015个节点的二叉树最多有（ ）个叶子节点(2015-22)

解析：
设叶子节点数为n_0，度为2的节点数为n_2
由性质3：n_0 = n_2 + 1
总结点数：n_0 + n_1 + n_2 = 2015
代入得：(n_2+1) + n_1 + n_2 = 2015→ 2n_2 + n_1 = 2014
要使n_0最大，需n_2最大，则n_1最小（取0）
2n_2 = 2014 → n_2 = 1007→ n_0 = 1008

四、总结与思考

二叉树的性质揭示了树形结构的数学规律：

1. 层节点数：指数级增长（性质1）

2. 叶-枝关系：叶子数总比二度节点多1（性质3）

3. 完全二叉树：高效存储的基础（数组表示）

4. 满二叉树：理想平衡状态

实际应用：

• 二叉堆（优先队列）：基于完全二叉树

• 哈夫曼编码：基于最优二叉树

• 数据库索引：B/B+树的基础

思考题：
在一棵完全二叉树中，编号为i和j的两个节点的最近公共祖先(LCA)编号如何计算？
（提示：利用完全二叉树的编号性质，不断除以2比较）