EC17-判断二叉树是否为满二叉树
代码实现
| C |
|---|
| // 函数 func：递归计算二叉树的节点总数和最大深度
// 参数：
// p - 当前节点
// n - 指向节点总数的指针
// L - 指向当前深度的指针
// max_L - 指向最大深度的指针
void func(BiTree p, int *n, int *L, int *max_L) {
if (p != NULL) {
++(*L); // 当前深度加 1
// 更新最大深度
if ((*L) > (*max_L)) {
*max_L = *L;
}
++(*n); // 节点总数加 1
// 递归处理左子树和右子树
func(p->lchild, n, L, max_L);
func(p->rchild, n, L, max_L);
--(*L); // 回溯时深度减 1（恢复状态）
}
}
// 函数 Is_True：判断二叉树是否为满二叉树
bool Is_True(BiTree p) {
int n = 0; // 节点总数
int L = 0; // 当前深度
int max_L = 0; // 最大深度
// 调用辅助函数 func 计算节点总数和最大深度
func(p, &n, &L, &max_L);
// 判断是否满足满二叉树性质
// 满二叉树的节点总数 = 2^max_L - 1
if (pow(2, max_L) - 1 == n) {
return true; // 是满二叉树
} else {
return false; // 不是满二叉树
}
}
|
代码逻辑解析
1. 满二叉树的定义
- 满二叉树是指每个非叶子节点都有两个子节点，并且所有叶子节点都在同一层。
- 对于深度为
h 的满二叉树，其节点总数为：
[
n = 2^h - 1
]
其中 h 是树的高度（从根节点开始计数，根节点高度为 1）。
2. 算法思路
- 使用递归遍历整棵树，同时记录以下信息：
- 节点总数
n
- 树的最大深度
max_L
- 遍历完成后，检查是否满足满二叉树的性质：
[
n = 2^{max_L} - 1
]
3. func 函数详解
- 递归终止条件：如果当前节点为空，则返回。
- 递归过程：
- 增加当前深度
L。
- 如果当前深度大于已知的最大深度
max_L，更新 max_L。
- 增加节点总数
n。
- 递归访问左子树和右子树。
- 回溯时减少当前深度
L（恢复状态）。
4. Is_True 函数详解
- 调用
func 函数计算节点总数 n 和最大深度 max_L。
- 根据公式 \( 2^{max\_L} - 1 \) 计算满二叉树应有的节点总数。
- 比较实际节点总数
n 和理论值，判断是否为满二叉树。
时间复杂度分析
1. func 函数时间复杂度
- 每个节点被访问 exactly 一次。
- 时间复杂度：O(n)，其中
n 是节点总数。
2. Is_True 函数时间复杂度
- 主要开销在于调用
func 函数。
- 时间复杂度：O(n)。
3. 总体时间复杂度
O(n)。
空间复杂度分析
1. 额外空间使用
- 只使用了常量级别的局部变量（
n, L, max_L）。
2. 递归调用栈空间
- 递归深度取决于树的高度
h。
- 最好情况（完全二叉树）：O(log n)。
- 最坏情况（退化为链表）：O(n)。
3. 总体空间复杂度
O(h)，其中 h 是树的高度。
在最坏情况下为 O(n)。
较难理解部分的说明
1. 回溯时的深度恢复
这段代码的作用是恢复当前深度的状态。递归返回到上一层时，需要将深度减 1，以确保下一次递归时深度计算正确。
图解说明：
假设二叉树结构如下：
递归过程中的深度变化：
| Text Only |
|---|
| 进入 A: L = 1
进入 B: L = 2
进入 D: L = 3
退出 D: L = 2
退出 B: L = 1
进入 C: L = 2
退出 C: L = 1
退出 A: L = 0
|
2. 满二叉树性质验证
图解说明：
满二叉树示例：
| Text Only |
|---|
| A // 第 1 层
/ \
B C // 第 2 层
/ \ / \
D E F G // 第 3 层
|
- 节点总数：\( n = 7 \)
- 最大深度：\( max\_L = 3 \)
- 验证公式：
[
2^{max_L} - 1 = 2^3 - 1 = 7
]
符合公式，因此是满二叉树。
非满二叉树示例：
| Text Only |
|---|
| A // 第 1 层
/ \
B C // 第 2 层
/ \
D E // 第 3 层
|
- 节点总数：\( n = 5 \)
- 最大深度：\( max\_L = 3 \)
- 验证公式：
[
2^{max_L} - 1 = 2^3 - 1 = 7
]
不符合公式，因此不是满二叉树。
延伸知识点
1. 改进版本 - 非递归实现
| C |
|---|
| // 使用层次遍历（BFS）计算节点总数和最大深度
bool Is_True_Iterative(BiTree root) {
if (root == NULL) return true; // 空树是满二叉树
int n = 0; // 节点总数
int max_L = 0; // 最大深度
Queue* queue = createQueue(); // 假设有队列实现
enqueue(queue, root);
while (!isEmpty(queue)) {
int level_size = size(queue);
max_L++; // 每次进入新层，深度加 1
for (int i = 0; i < level_size; i++) {
BiTree node = dequeue(queue);
n++; // 节点总数加 1
if (node->lchild) enqueue(queue, node->lchild);
if (node->rchild) enqueue(queue, node->rchild);
}
}
// 判断是否满足满二叉树性质
if (pow(2, max_L) - 1 == n) {
return true;
} else {
return false;
}
}
|
2. 满二叉树与其他特殊二叉树的关系
- 满二叉树：每层节点数达到最大值，且所有叶子节点在同一层。
- 完全二叉树：除最后一层外，其他层都是满的，且最后一层的节点从左到右连续排列。
- 完美二叉树：与满二叉树等价。
3. 满二叉树的应用场景
- 数据存储：堆结构（如最大堆、最小堆）通常基于满二叉树构建。
- 哈夫曼编码：哈夫曼树是一种特殊的满二叉树。
- 分治算法：许多分治算法（如归并排序、快速排序）的递归树可以近似看作满二叉树。
- 网络拓扑：某些通信协议的路由结构基于满二叉树设计。
4. 性能优化建议
| C |
|---|
| // 优化版本 - 提前终止
bool Is_True_Optimized(BiTree p) {
int n = 0; // 节点总数
int max_L = 0; // 最大深度
Queue* queue = createQueue();
enqueue(queue, p);
while (!isEmpty(queue)) {
int level_size = size(queue);
max_L++;
// 检查当前层是否满足满二叉树性质
if (pow(2, max_L - 1) != level_size && !isEmpty(queue)) {
return false; // 当前层节点数不满足满二叉树性质
}
for (int i = 0; i < level_size; i++) {
BiTree node = dequeue(queue);
n++;
if (node->lchild) enqueue(queue, node->lchild);
if (node->rchild) enqueue(queue, node->rchild);
}
}
return true;
}
|
这种方法体现了数学性质验证的思想，通过简单的公式计算即可高效地判断二叉树是否为满二叉树，是计算机科学中经典问题之一。