EC15-使用层次遍历计算二叉树的宽度
代码实现
方法一：层次遍历思想（广度优先搜索）
| C |
|---|
| // 函数 level：使用层次遍历计算二叉树的宽度
// 二叉树的宽度定义为各层节点数的最大值
int level(BiTree bt) {
BiTree que[maxsize]; // 使用数组实现队列
int front = 0, rear = 0; // 队列的头指针和尾指针
int res = 0; // 当前层的节点计数器
int last = 1; // 当前层的最后一个节点在队列中的位置
int width = 0; // 记录最大宽度
// 如果二叉树不为空
if (bt != NULL) {
que[++rear] = bt; // 将根节点入队
// 当队列不为空时继续遍历
while (front != rear) {
bt = que[++front]; // 出队一个节点
res++; // 当前层节点数加1
// 将左子节点入队
if (bt->lchild != NULL) {
que[++rear] = bt->lchild;
}
// 将右子节点入队
if (bt->rchild != NULL) {
que[++rear] = bt->rchild;
}
// 如果当前出队的是当前层的最后一个节点
if (front == last) {
// 更新最大宽度
if (res > width) {
width = res;
}
res = 0; // 重置当前层节点计数器
last = rear; // 更新下一层的最后一个节点位置
}
}
}
return width; // 返回二叉树的最大宽度
}
|
方法二：递归遍历思想（深度优先搜索）
| C |
|---|
| // 函数 func：递归遍历二叉树，统计每层的节点数
// 参数：bt - 当前节点，A[] - 存储每层节点数的数组，L - 当前层数指针
void func(BiTree bt, int A[], int *L) {
// 如果当前节点不为空
if (bt != NULL) {
++(*L); // 进入下一层，层数加1
A[(*L)]++; // 当前层的节点数加1
// 递归处理左子树
func(bt->lchild, A, L);
// 递归处理右子树
func(bt->rchild, A, L);
--(*L); // 回退到上一层，层数减1
}
}
// 函数 max_width：计算二叉树的最大宽度
int max_width(BiTree bt) {
int A[maxsize] = {0}; // 初始化数组，存储每层的节点数
int L = 0; // 初始化当前层数为0
// 递归遍历二叉树，统计每层节点数
func(bt, A, &L);
int width = 0; // 初始化最大宽度为0
// 遍历数组，找出最大值
for (int i = 1; i < maxsize; i++) {
if (A[i] > width) {
width = A[i]; // 更新最大宽度
}
}
return width; // 返回二叉树的最大宽度
}
|
代码逻辑解析
方法一：层次遍历（BFS）
1. 核心思想
- 按层遍历二叉树
- 统计每一层的节点数
- 记录所有层中节点数的最大值
2. 关键变量
que[]：循环队列，存储待访问的节点front, rear：队列的头尾指针res：当前层的节点计数器last：标记当前层的最后一个节点在队列中的位置width：记录最大宽度
3. 层次控制机制
| C |
|---|
| // 当处理完当前层的最后一个节点时
if (front == last) {
// 更新最大宽度
if (res > width) width = res;
res = 0; // 重置计数器
last = rear; // 设置下一层的结束位置
}
|
方法二：递归遍历（DFS）
1. 核心思想
- 通过深度优先遍历记录每个节点所在的层数
- 使用数组统计每层的节点数
- 找出节点数最多的层
2. 递归机制
| C |
|---|
| ++(*L); // 进入子节点，层数加1
A[(*L)]++; // 当前层节点数加1
// 递归处理子树
--(*L); // 回退，屌数减1
|
时间复杂度分析
方法一：层次遍历
- 节点访问：每个节点被访问 exactly 一次
- 队列操作：入队和出队操作都是 O(1)
- 时间复杂度：O(n)，其中 n 是节点总数
方法二：递归遍历
- 递归调用：每个节点被访问 exactly 一次
- 数组操作：每次访问进行常数时间的数组操作
- 查找最大值：需要遍历数组，但数组大小与节点数相关
- 时间复杂度：O(n)
空间复杂度分析
方法一：层次遍历
- 队列空间：最坏情况下队列需要存储一层的所有节点
- 完全二叉树：O(n/2) ≈ O(n)
- 链式结构：O(1)
- 空间复杂度：O(w)，其中 w 是树的最大宽度
方法二：递归遍历
- 数组空间：O(h)，其中 h 是树的高度
- 递归栈：O(h)
- 空间复杂度：O(h)
较难理解部分的说明
1. 层次遍历中的 last 变量
| C |
|---|
| // 图示说明
// A(1)
// / \
// B(2) C(3)
// / \ \
// D(4)E(5)F(6)
队列状态变化：
初始：[A] last=1, front=0, rear=1
第1层：出队A，入队B,C → [B,C] last=3, res=1
第1层结束：front=2==last=3 → width=1, res=0, last=3
第2层：出队B，入队D,E → [C,D,E] last=5, res=1
第2层：出队C，入队F → [D,E,F] last=6, res=2
第2层结束：front=5==last=6 → width=2, res=0, last=6
|
2. 递归遍历的层数管理
| C |
|---|
| // 递归深度变化示例
// A(1)
// / \
// B(2) C(2)
// /
// D(3)
调用栈变化：
func(A, L=0) → L=1, A[1]++
├─ func(B, L=1) → L=2, A[2]++
│ ├─ func(D, L=2) → L=3, A[3]++
│ │ └─ 回退：L=2
│ └─ 回退：L=1
└─ func(C, L=1) → L=2, A[2]++
└─ 回退：L=1
|
图解说明
假设二叉树结构如下：
| Text Only |
|---|
| A(1) // 第1层：1个节点
/ \
B(2) C(3) // 第2层：2个节点
/ \ \
D(4)E(5)F(6) // 第3层：3个节点
/
G(7) // 第4层：1个节点
|
方法一执行过程：
| Text Only |
|---|
| 第1层：A → 节点数 = 1
第2层：B, C → 节点数 = 2
第3层：D, E, F → 节点数 = 3
第4层：G → 节点数 = 1
最大宽度 = 3
|
方法二执行结果：
| Text Only |
|---|
| A[1] = 1 // 第1层1个节点
A[2] = 2 // 第2层2个节点
A[3] = 3 // 第3层3个节点
A[4] = 1 // 第4层1个节点
最大宽度 = 3
|
延伸知识点
1. 改进版本 - 返回宽度和层数
| C |
|---|
| typedef struct {
int maxWidth;
int maxLevel;
} WidthInfo;
WidthInfo getWidthWithLevel(BiTree root) {
if (root == NULL) {
WidthInfo info = {0, 0};
return info;
}
int levelCount[maxsize] = {0};
int maxLevel = 0;
// 使用队列进行层次遍历
typedef struct { BiTree node; int level; } QueueItem;
QueueItem queue[maxsize];
int front = 0, rear = 0;
queue[rear].node = root;
queue[rear].level = 1;
rear++;
while (front < rear) {
QueueItem item = queue[front++];
int currentLevel = item.level;
levelCount[currentLevel]++;
if (currentLevel > maxLevel) maxLevel = currentLevel;
if (item.node->lchild) {
queue[rear].node = item.node->lchild;
queue[rear].level = currentLevel + 1;
rear++;
}
if (item.node->rchild) {
queue[rear].node = item.node->rchild;
queue[rear].level = currentLevel + 1;
rear++;
}
}
int maxWidth = 0;
int maxWidthLevel = 1;
for (int i = 1; i <= maxLevel; i++) {
if (levelCount[i] > maxWidth) {
maxWidth = levelCount[i];
maxWidthLevel = i;
}
}
WidthInfo info = {maxWidth, maxWidthLevel};
return info;
}
|
2. 使用 STL 队列的现代版本
| C++ |
|---|
| #include <queue>
#include <algorithm>
int getWidthSTL(BiTree root) {
if (!root) return 0;
std::queue<BiTree> q;
q.push(root);
int maxWidth = 0;
while (!q.empty()) {
int levelSize = q.size(); // 当前层的节点数
maxWidth = std::max(maxWidth, levelSize);
// 处理当前层的所有节点
for (int i = 0; i < levelSize; i++) {
BiTree node = q.front();
q.pop();
if (node->lchild) q.push(node->lchild);
if (node->rchild) q.push(node->rchild);
}
}
return maxWidth;
}
|
3. 计算宽度的其他定义
| C |
|---|
| // 最大宽度（考虑节点间空隙）
int getMaxWidthWithGaps(BiTree root) {
if (!root) return 0;
std::queue<std::pair<BiTree, int>> q; // 节点及其位置编号
q.push({root, 1});
int maxWidth = 0;
while (!q.empty()) {
int levelSize = q.size();
int leftPos = q.front().second;
int rightPos = leftPos;
for (int i = 0; i < levelSize; i++) {
auto [node, pos] = q.front();
q.pop();
rightPos = pos;
if (node->lchild) q.push({node->lchild, 2 * pos});
if (node->rchild) q.push({node->rchild, 2 * pos + 1});
}
maxWidth = std::max(maxWidth, rightPos - leftPos + 1);
}
return maxWidth;
}
|
4. 实际应用场景
- 界面布局：计算树形结构 UI 组件的最大宽度
- 打印格式化：确定树形数据的打印宽度
- 内存分配：预估树形结构的存储空间需求
- 性能分析：分析树形算法的空间复杂度
- 图形渲染：确定树状图的最大横向跨度
5. 算法比较总结
| 方法 |
时间复杂度 |
空间复杂度 |
优点 |
缺点 |
| 层次遍历 |
O(n) |
O(w) |
直观易懂，可边遍历边计算 |
需要队列空间 |
| 递归遍历 |
O(n) |
O(h) |
代码简洁 |
需要额外数组，递归栈开销 |
两种方法各有优势，选择哪种取决于具体的应用场景和性能要求。