假设二叉树采用二叉链表存储结构,试设计一个算法求二叉树的高度。c语言实现
时间: 2024-12-21 18:11:36 浏览: 27
头歌数据结构二叉树的二叉链表存储及基本操作
5星 · 资源好评率100%
在C语言中,我们可以使用递归的方式来计算二叉链表表示的二叉树的高度。以下是算法的设计:
```c
// 定义二叉节点结构
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 计算二叉树高度的函数
int heightOfBinaryTree(TreeNode* root) {
// 如果根节点为空,高度为0
if (root == NULL) {
return 0;
}
// 左右子树的高度分别递归计算,取较大者加1即为当前节点的高度
int leftHeight = heightOfBinaryTree(root->left);
int rightHeight = heightOfBinaryTree(root->right);
// 返回较大的那个高度加1(因为根节点的高度包含左右子高度)
return (leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
}
```
这个`heightOfBinaryTree`函数首先检查根节点是否为空,如果为空则返回0。然后递归地对左子树和右子树分别计算高度,并返回其中的最大值加1,这是因为每层的高度比下一层多1。
阅读全文