用C语言简易编写计算二叉树最大宽度的算法。(二叉树最大宽度指二叉树所有层中结点个数的最大值)
时间: 2024-02-06 18:11:22 浏览: 29
这里给出一份简易的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点结构体
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
// 求二叉树高度
int getHeight(Node *root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return leftHeight > rightHeight ? (leftHeight + 1) : (rightHeight + 1);
}
// 计算二叉树某一层的结点个数
int getNodeNum(Node *root, int level) {
if (root == NULL || level < 1) {
return 0;
}
if (level == 1) {
return 1;
}
int leftNum = getNodeNum(root->left, level - 1);
int rightNum = getNodeNum(root->right, level - 1);
return leftNum + rightNum;
}
// 计算二叉树最大宽度
int maxWidth(Node *root) {
if (root == NULL) {
return 0;
}
int height = getHeight(root); // 先求出二叉树的高度
int max = 1; // 记录最大宽度,默认为1
for (int i = 1; i <= height; i++) {
int num = getNodeNum(root, i); // 计算第i层的结点个数
if (num > max) {
max = num; // 更新最大宽度
}
}
return max;
}
int main() {
// 构造如下二叉树
// 1
// / \
// 2 3
// / \ \
// 4 5 6
Node *root = (Node *)malloc(sizeof(Node));
root->data = 1;
root->left = (Node *)malloc(sizeof(Node));
root->left->data = 2;
root->left->left = (Node *)malloc(sizeof(Node));
root->left->left->data = 4;
root->left->right = (Node *)malloc(sizeof(Node));
root->left->right->data = 5;
root->right = (Node *)malloc(sizeof(Node));
root->right->data = 3;
root->right->right = (Node *)malloc(sizeof(Node));
root->right->right->data = 6;
printf("二叉树最大宽度为:%d\n", maxWidth(root)); // 输出:二叉树最大宽度为:3
return 0;
}
```
注:这份代码实现使用了递归来求二叉树高度和某一层的结点个数,可能会存在效率上的问题。但考虑到代码简洁易懂,也可以作为参考。