c语言实现求二叉树的高度
时间: 2023-06-09 09:07:47 浏览: 92
好的,我可以为您提供一种实现方法:
首先,我们需要定义二叉树的结构体,包括左右子树指针和节点值:
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
```
然后,我们可以通过递归的方式,先求出左右子树的高度,然后取两者中的较大值加一即可得到整棵二叉树的高度:
```c
int maxDepth(struct TreeNode* root) {
if (root == NULL) { // 如果节点为 NULL,则返回高度为 0
return 0;
}
int leftDepth = maxDepth(root->left); // 递归求左子树高度
int rightDepth = maxDepth(root->right); // 递归求右子树高度
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; // 左右子树高度较大者加一即为整棵树的高度
}
```
以上就是求二叉树高度的 C 语言实现方法,希望能对您有所帮助!
相关问题
用c语言实现统计二叉树的高度
以下是用 C 语言实现统计二叉树高度的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int getHeight(struct Node* root) {
if (root == NULL) {
return 0;
} else {
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
if (leftHeight > rightHeight) {
return (leftHeight + 1);
} else {
return (rightHeight + 1);
}
}
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Height of binary tree is: %d\n", getHeight(root));
return 0;
}
```
输出结果:
```
Height of binary tree is: 3
```
在这个示例中,我们创建了一棵二叉树,并使用 `getHeight` 函数计算了它的高度。`getHeight` 函数使用递归方法计算二叉树的高度。如果节点为空,则返回 0,否则在左子树和右子树中找到最大高度,并将其加 1 返回。最后,在主函数中,我们调用 `getHeight` 函数并打印输出二叉树的高度。
用C语言实现平衡二叉树的判定
判定一棵二叉树是否为平衡二叉树的方法是,对于每个节点,计算其左子树的高度和右子树的高度,如果两者之差不超过1,则该节点满足平衡条件,否则不满足平衡条件。递归判断每个节点是否满足平衡条件即可。
以下是C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点的定义
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 计算二叉树的高度
int getHeight(TreeNode *root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
// 判断一棵二叉树是否为平衡二叉树
bool isBalanced(TreeNode *root) {
if (root == NULL) {
return true;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
if (abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}
```
其中,getHeight函数计算二叉树的高度,isBalanced函数则使用递归判断每个节点是否满足平衡条件。
相关推荐
![](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)