利用编程思维做题之计算二叉树最大宽度
1. 理解问题
我们需要设计一个算法来计算给定二叉树的最大宽度。二叉树的宽度是指某一层中节点的数量，最大宽度则是所有层中的最大值。如果树为空，则宽度为 0。
示例
假设我们有如下的二叉树：
1
/ \
2 3
/ \ \
4 5 6
在这棵树中，第 3 层的宽度是 3（节点 4、5 和 6），因此最大宽度为 3。
2. 输入输出
输入：
root：指向二叉树根节点的指针，表示二叉树的起始节点。
输出：
- 返回值：返回二叉树的最大宽度。
3. 二叉树结构
二叉树节点的定义如下：
struct TreeNode {
int data; // 节点的值
struct TreeNode* left; // 指向左子节点的指针
struct TreeNode* right; // 指向右子节点的指针
};
4. 制定策略
为实现计算二叉树最大宽度的算法，我们可以使用层序遍历（广度优先搜索）。在遍历过程中，记录每一层的节点数量，找到最大宽度。
关键步骤：
- 使用队列存储当前层的节点。
- 对于每一层，记录该层的节点数，并更新最大宽度。
- 将下一层的节点加入队列。
5. 实现代码
5.1 关键函数实现
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 定义队列的最大大小
// 定义二叉树节点结构
struct TreeNode {
int data; // 节点的数据
struct TreeNode* left; // 指向左子节点的指针
struct TreeNode* right; // 指向右子节点的指针
};
// 创建一个新节点
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 定义队列结构
struct Queue {
struct TreeNode* nodes[MAX_SIZE]; // 队列的节点数组
int front; // 队列前端
int rear; // 队列后端
};
// 初始化队列
void initQueue(struct Queue* queue) {
queue->front = 0;
queue->rear = 0;
}
// 判断队列是否为空
int isEmpty(struct Queue* queue) {
return queue->front == queue->rear;
}
// 入队
void enqueue(struct Queue* queue, struct TreeNode* node) {
queue->nodes[queue->rear++] = node;
}
// 出队
struct TreeNode* dequeue(struct Queue* queue) {
return queue->nodes[queue->front++];
}
// 计算二叉树的最大宽度
int calculateMaxWidth(struct TreeNode* root) {
if (root == NULL) return 0;
struct Queue queue;
initQueue(&queue);
enqueue(&queue, root); // 根节点入队
int maxWidth = 0;
while (!isEmpty(&queue)) {
int size = 0; // 当前层的节点数量
int currentSize = queue.rear - queue.front;
// 遍历当前层的所有节点
for (int i = 0; i < currentSize; i++) {
struct TreeNode* current = dequeue(&queue);
size++;
// 将子节点入队
if (current->left != NULL) {
enqueue(&queue, current->left);
}
if (current->right != NULL) {
enqueue(&queue, current->right);
}
}
// 更新最大宽度
maxWidth = (size > maxWidth) ? size : maxWidth;
}
return maxWidth;
}
5.2 完整 C 代码
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 定义队列的最大大小
// 定义二叉树节点结构
struct TreeNode {
int data; // 节点的数据
struct TreeNode* left; // 指向左子节点的指针
struct TreeNode* right; // 指向右子节点的指针
};
// 创建一个新节点
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 定义队列结构
struct Queue {
struct TreeNode* nodes[MAX_SIZE]; // 队列的节点数组
int front; // 队列前端
int rear; // 队列后端
};
// 初始化队列
void initQueue(struct Queue* queue) {
queue->front = 0;
queue->rear = 0;
}
// 判断队列是否为空
int isEmpty(struct Queue* queue) {
return queue->front == queue->rear;
}
// 入队
void enqueue(struct Queue* queue, struct TreeNode* node) {
queue->nodes[queue->rear++] = node;
}
// 出队
struct TreeNode* dequeue(struct Queue* queue) {
return queue->nodes[queue->front++];
}
// 计算二叉树的最大宽度
int calculateMaxWidth(struct TreeNode* root) {
if (root == NULL) return 0;
struct Queue queue;
initQueue(&queue);
enqueue(&queue, root); // 根节点入队
int maxWidth = 0;
while (!isEmpty(&queue)) {
int size = 0; // 当前层的节点数量
int currentSize = queue.rear - queue.front;
// 遍历当前层的所有节点
for (int i = 0; i < currentSize; i++) {
struct TreeNode* current = dequeue(&queue);
size++;
// 将子节点入队
if (current->left != NULL) {
enqueue(&queue, current->left);
}
if (current->right != NULL) {
enqueue(&queue, current->right);
}
}
// 更新最大宽度
maxWidth = (size > maxWidth) ? size : maxWidth;
}
return maxWidth;
}
// 主函数
int main() {
// 创建二叉树的节点
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->right = createNode(6);
// 计算二叉树的最大宽度
int maxWidth = calculateMaxWidth(root);
printf("二叉树的最大宽度是: %d\n", maxWidth);
return 0;
}
5.3 代码说明
calculateMaxWidth(struct TreeNode* root)：计算二叉树的最大宽度。- 使用队列进行层序遍历，计算每一层的节点数量，并更新最大宽度。
5.4 模拟过程
以上面的二叉树为例：
1
/ \
2 3
/ \ \
4 5 6
步骤 1：计算最大宽度
- 从根节点 1 开始，将其入队。当前队列状态：
[1] - 当前层的节点数量为 1，最大宽度更新为 1。
步骤 2：第二层
- 出队节点 1，入队其左右子节点 2 和 3。当前队列状态：
[2, 3] - 当前层的节点数量为 2，最大宽度更新为 2。
步骤 3：第三层
- 出队节点 2 和 3，入队其子节点 4、5 和 6。当前队列状态：
[4, 5, 6] - 当前层的节点数量为 3，最大宽度更新为 3。
步骤 4：结束遍历
- 继续出队，队列为空，遍历结束。
最终，二叉树的最大宽度为 3。
6. 运行结果
对于上述示例，运行结果为：二叉树的最大宽度是: 3。
7. 时间和空间复杂度分析
-
时间复杂度：O(n)，其中 n 为树中节点的总数。最坏情况下，算法需要遍历整个二叉树中的所有节点。
-
空间复杂度：O(w)，其中 w 是二叉树的最大宽度。在最坏情况下，队列需要存储所有