c语言设计一个算法求二叉树深度,写出完整代码,并标注出中心算法代码
时间: 2024-12-22 16:13:32 浏览: 3
在C语言中,我们可以使用递归的方式设计一个算法来计算二叉树的深度。这里是一个简单的示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 中心递归算法 - 计算二叉树深度
int maxDepth(TreeNode* root) {
// 如果根节点为空,返回0表示树的高度为0
if (root == NULL) {
return 0;
}
// 递归地计算左子树和右子树的最大深度,然后取较大值加1
int left_depth = maxDepth(root->left);
int right_depth = maxDepth(root->right);
// 返回当前节点的最大深度
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
// 主函数测试
int main() {
// 创建一个简单的二叉树作为示例
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = NULL;
// 测试maxDepth函数
int depth = maxDepth(root);
printf("The maximum depth of the binary tree is: %d\n", depth);
free(root); // 释放内存
return 0;
}
```
在这个例子中,`maxDepth`函数是中心算法,它负责递归地遍历树并返回最大深度。如果树为空,那么深度就是0;否则,通过比较左右子树的深度来确定当前节点所在的最大深度。
阅读全文