以二叉链存储二叉树b,设计算法求二叉树的高度。 typedef struct node { ElemType data; struct node* lchild; struct node* rchild; }BTNode; int GetHeight(BTNode* b)
时间: 2024-10-18 22:18:00 浏览: 22
二叉树的二叉链表表示及实现实验报告.docx
为了求解二叉树的高度,可以采用递归的方式,因为二叉树的高度就是其左右子树高度的最大值加1。以下是用给定的二叉链表示的结构体`BTNode`编写的一个算法:
```c
int GetHeight(BTNode* b) {
// 如果树为空,则高度为0
if (b == NULL) {
return 0;
}
// 分别计算左右子树的高度
int left_height = GetHeight(b->lchild);
int right_height = GetHeight(b->rchild);
// 返回较大的那一边的高度加1(即当前节点的高度)
return (left_height > right_height ? left_height + 1 : right_height + 1);
}
```
这个函数接受一个指向二叉树根节点的指针`b`,然后递归地访问左子树和右子树,直到找到空节点(表示到达叶节点或空树)。每次递归调用都会增加1来表示当前层级,所以最终返回的是整个树的高度。
如果你想要直接查看二叉树的高度而不是编写算法,可以遍历整棵树并记录深度,但在没有额外数据结构的情况下,递归是最直观且常用的方法。
阅读全文