用c语言计算二叉树的最大宽度
时间: 2024-06-13 22:06:27 浏览: 19
以下是用C语言计算二叉树最大宽度的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int depth(TreeNode* root) {
if (!root) {
return 0;
}
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
int levelWidth(TreeNode* root, int level) {
if (!root) {
return 0;
}
if (level == 1) {
return 1;
}
return levelWidth(root->left, level - 1) + levelWidth(root->right, level - 1);
}
int width(TreeNode* root) {
int maxWidth = 0;
int treeDepth = depth(root);
for (int i = 1; i <= treeDepth; i++) {
int levelWidthValue = levelWidth(root, i);
if (levelWidthValue > maxWidth) {
maxWidth = levelWidthValue;
}
}
return maxWidth;
}
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 = width(root);
printf("The maximum width of the binary tree is: %d\n", maxWidth);
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)