用C语言,请用递归思想写出求二叉树深度的实现函数,要求先定义出tree_t结构体,再写出完整实现。 int getBTreeHeight(tree_t* root)
时间: 2024-10-02 22:04:24 浏览: 53
在C语言中,我们可以使用递归的方式来计算二叉树的高度。首先,我们需要定义一个`tree_t`结构体来表示二叉树节点,包含数据以及指向左右子节点的指针。
```c
// 定义二叉树节点结构体
typedef struct tree_node {
int data;
struct tree_node* left;
struct tree_node* right;
} tree_t;
// 求二叉树高度的递归函数
int getBTreeHeight(tree_t* root) {
// 基本情况:空树高度为0
if (root == NULL) {
return 0;
}
// 递归情况:计算左右子树的高度,取较大者加1作为当前节点的高度
int left_height = getBTreeHeight(root->left);
int right_height = getBTreeHeight(root->right);
// 返回较大的高度加1
return (left_height > right_height ? left_height : right_height) + 1;
}
```
这个函数的工作原理是从根节点开始,如果遇到空节点(即NULL),则返回0,因为空树的高度就是0。对于非空节点,它会递归地计算左子树和右子树的高度,并选择其中较大的一个加1,这就是当前节点的高度。最后返回的结果就是整个二叉树的最大深度。
相关问题
C语言编写一个递归函数,计算二叉树深度。
在C语言中,计算二叉树的深度通常涉及到递归算法。你可以定义一个递归函数`binaryTreeDepth`,其基本思路是从根节点开始,如果当前节点非空,则向左和右子节点递归地求深度,并返回其中的最大值加一。下面是简单的代码示例:
```c
#include <stdio.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 计算二叉树深度的递归函数
int binaryTreeDepth(TreeNode* root) {
// 如果树为空,深度为0
if (root == NULL) {
return 0;
}
// 否则,左右子树深度加上1即为当前树的深度
int left_depth = binaryTreeDepth(root->left);
int right_depth = binaryTreeDepth(root->right);
// 返回较大的那个子树深度作为当前节点的深度
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
int main() {
// 创建一个示例二叉树
TreeNode* tree = /* 初始化二叉树... */;
int depth = binaryTreeDepth(tree);
printf("The depth of the binary tree is %d.\n", depth);
return 0;
}
```
在这个例子中,
请用c语言编写求二叉树深度的递归算法
在C语言中,可以使用递归来计算二叉树的深度。这里是一个简单的递归函数示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 计算二叉树深度的辅助函数
int maxDepth(struct TreeNode* root) {
// 如果根节点为空,返回0
if (root == NULL) return 0;
// 否则分别计算左子树和右子树的深度,并取较大值加1作为当前的高度
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
// 返回最大深度
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 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;
int depth = maxDepth(root);
printf("The maximum depth of the binary tree is %d\n", depth);
// 清理内存
free(root->left);
free(root->right);
free(root);
return 0;
}
```
在这个例子中,`maxDepth` 函数会一直递归地检查左右子树,直到找到空节点,然后返回当前层数。当处理完整个树后,最终的深度即为树的最大深度。
阅读全文