假设二叉树采用二叉链存储结构进行存储。设计一个算法采用分治法求一棵二叉树bt的高度
时间: 2023-05-29 10:01:58 浏览: 169
数据结构课程设计,包含实验报告和代码
递归的思想可以很好地应用于二叉树高度的求解。如果二叉树为空,则高度为0。否则,树的高度为左子树高度与右子树高度的最大值加1。因此,可以采用分治法递归地求解左右子树的高度。
具体算法如下:
```
int height(BiTree bt) {
if (bt == NULL) {
return 0;
}
int left_height = height(bt->lchild);
int right_height = height(bt->rchild);
return max(left_height, right_height) + 1;
}
```
其中,max()函数返回两个参数中的最大值。算法的时间复杂度是O(n),其中n是二叉树的节点数。
阅读全文