计算二叉树最大的宽度 用C实现
时间: 2023-12-01 11:41:19 浏览: 61
以下是用C语言实现计算二叉树最大宽度的代码,具体实现思路见注释:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 定义队列结构体
typedef struct Queue {
TreeNode **data;
int front, rear;
int size;
} Queue;
// 初始化队列
Queue *initQueue(int size) {
Queue *q = (Queue *)malloc(sizeof(Queue));
q->data = (TreeNode **)malloc(sizeof(TreeNode *) * size);
q->front = q->rear = 0;
q->size = size;
return q;
}
// 判断队列是否为空
int isEmpty(Queue *q) {
return q->front == q->rear;
}
// 入队
void enQueue(Queue *q, TreeNode *node) {
if (q == NULL || node == NULL) {
return;
}
q->data[q->rear++] = node;
}
// 出队
TreeNode *deQueue(Queue *q) {
if (q == NULL || isEmpty(q)) {
return NULL;
}
return q->data[q->front++];
}
// 计算二叉树最大宽度
int maxWidthOfBinaryTree(TreeNode *root) {
if (root == NULL) {
return 0;
}
Queue *q = initQueue(1000); // 初始化队列
enQueue(q, root); // 根节点入队
int maxWidth = 1; // 初始化最大宽度为1
while (!isEmpty(q)) {
int size = q->rear - q->front; // 当前层的节点数
maxWidth = size > maxWidth ? size : maxWidth; // 更新最大宽度
for (int i = 0; i < size; i++) {
TreeNode *node = deQueue(q); // 出队
if (node->left != NULL) {
enQueue(q, node->left); // 左子节点入队
}
if (node->right != NULL) {
enQueue(q, node->right); // 右子节点入队
}
}
}
return maxWidth;
}
// 计算二叉树深度
int depth(TreeNode *root) {
if (root == NULL) {
return 0;
}
int leftDepth = depth(root->left); // 左子树深度
int rightDepth = depth(root->right); // 右子树深度
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; // 取较大值加1
}
int main() {
// 构建二叉树
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode *)malloc(sizeof(TreeNode));
root->left->val = 2;
root->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->val = 3;
root->left->left = (TreeNode *)malloc(sizeof(TreeNode));
root->left->left->val = 4;
root->left->right = (TreeNode *)malloc(sizeof(TreeNode));
root->left->right->val = 5;
root->right->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->right->val = 6;
// 计算二叉树最大宽度
int maxWidth = maxWidthOfBinaryTree(root);
printf("The maximum width of the binary tree is: %d\n", maxWidth);
// 计算二叉树深度
int d = depth(root);
printf("The depth of the binary tree is: %d\n", d);
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)