森林的高度递归求解
问题描述:设计算法求解森林的高度
【算法设计思想】
两个函数,一个用于计算单个二叉树的高度,另一个用于计算二叉树森林(即一组二叉树)的最大高度。下面是对两个函数的详细解释:
1. treeHeight
函数
这个函数用于计算单个二叉树的高度。二叉树的高度定义为从根节点到最远叶子节点的最长路径上的边数。函数的参数是指向二叉树根节点的指针 root
。
函数的逻辑如下:
- 如果
root
是NULL
(即空指针),表示当前节点为空,因此返回高度为0。 - 如果
root
不为空,函数会递归地计算左子树root->lChild
和右子树root->rChild
的高度。 - 通过比较左右子树的高度,取较大的那个高度,并在其基础上加1(因为还要包括当前节点),得到当前树的高度。
- 返回当前树的高度。
2. forestHeight
函数
这个函数用于计算二叉树森林的最大高度。二叉树森林是一组二叉树的集合,每棵树由一个数组 forest
表示,其中数组的每个元素是一个指向二叉树根节点的指针。参数 numTrees
表示森林中树的数量。
函数的逻辑如下:
- 初始化一个变量
maxHeight
为0,用于记录遍历过程中发现的最大高度。 - 使用一个
for
循环遍历森林中的每一棵树。对于每棵树,通过调用treeHeight
函数计算其高度。 - 将计算得到的高度与当前记录的最大高度
maxHeight
进行比较,如果当前树的高度更大,则更新maxHeight
。 - 在遍历完所有树后,返回记录的最大高度
maxHeight
。
这段代码展示了如何通过递归和迭代的方式计算二叉树及其森林的高度。在实际应用中,这种计算对于理解数据结构的复杂性和设计算法非常重要。
【算法描述】
// 定义二叉树节点结构
typedef struct BiNode {
char data;
struct BiNode *lChild;
struct BiNode *rChild;
} BiNode;
// 求解二叉树的高度
int treeHeight(BiNode* root) {
if (root == NULL)
return 0;
// 递归计算左右子树的高度,并取最大值
int leftHeight = treeHeight(root->lChild);
int rightHeight = treeHeight(root->rChild);
// 返回左右子树高度的最大值加上当前节点的高度(1)
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// 求解森林的高度
int forestHeight(BiNode** forest, int numTrees) {
int maxHeight = 0;
// 遍历每棵树,求解其高度,并记录最大高度
for (int i = 0; i < numTrees; ++i) {
int height = treeHeight(forest[i]);
if (height > maxHeight) {
maxHeight = height;
}
}
return maxHeight;
}
标签:函数,递归,int,maxHeight,高度,笔记,二叉树,数据结构,root
From: https://www.cnblogs.com/zeta186012/p/18187299