二叉树4:二叉树求树高度(超级详细)
一、思路什么是树高?树的高度(或深度)就是树中结点的最大层数。在这里二、代码实现typedef struct TreeNode{int data;//数据域TreeNode *RChild;//右孩子指针TreeNode *LChild;//左孩子指针}TreeNode, *BiTree;int PostTreeHeight(BiTree *T){//通过后序遍历实现求树的高度int h = 0,
文章共1,196字 · 阅读需要大约4分钟
一键AI生成摘要,助你高效阅读
问答
·
一、思路
什么是树高?
树的高度(或深度)就是树中结点的最大层数。
在这里使用后序遍历的递归算法。
对每一个结点都进行如下操作:
- 后序遍历其左子树求树高
- 后序遍历其右子树求树高
- 对这个结点进行下面操作:
- 比较其左右子树的高度大小
- 若左>右,则选择左的高度;反之,选择右的高度
- 将上一步选出的
高度+1
,并作为返回值返回
递归算法比较抽象,这里举个例子
比如上面这个图,按照后序遍历的序列,第1个遍历到的会是①这个结点。
然后,对①进行上面的处理。
- ①左子树高度为0,右子树高度为0
- 比较左右子树大小,若左大于右,则选择左。此时,左不大于右,那么选右:0
- 对0+1,然后将1返回给上一层。即就是,作为结点④其左子树的高度返回上去。
第2个遍历到的是②这个结点:
同样的道理,可以得到②结点会返回给上一层1。
第3个遍历的是④结点:
遍历到④的时候,其左右子树的高度已经由前两步骤得出来了,都是1。
接着,对4进行同样的操作,比较其左右子树的高度。
若左子树高于右子树,就选择左子树的高度,否则选择右子树。
这里左右都是1。那么选右子树的1。
接着,1+1=2。
这个结果就是遍历根节点⑤的左子树所得到的结果。
然后用同样的方式遍历右子树,最后回到根节点。
对根节点的处理方式也相同:
比较左右树的高度,选高的,然后+1返回最终的结果就是树高。
二、代码实现
这个是代码实现,如果看不明白的,上去看看对每个结点处理的方式,和上面举的例子
typedef struct TreeNode{
int data;//数据域
TreeNode *RChild;//右孩子指针
TreeNode *LChild;//左孩子指针
}TreeNode, *BiTree;
int getdepth(TreeNode* node) {
//1.确定递归函数的返回值和参数:参数-传入根节点 返回值-int
//2.终止条件:如果为空节点,返回0,表示高度为0
if (node == NULL) return 0;
//3.确定单层递归的逻辑
int leftdepth = getdepth(node->LChild);//递归求左子树高度
int rightdepth = getdepth(node->RChild);//递归求右子树高度
//int depth = 1 + max(leftdepth, rightdepth);//树的高度是根到叶子最长路径上的结点的数量
int depth = 1 + (leftdepth > rightdepth?leftdepth:rightdepth);//这样写和上一行一样
//所以,每次要找最高的那个子树,所以要使用max函数
//调用两个递归函数直接可以算出来两个子树的高度,取最高的子树就作为子树高度,再加上根节点高度就行
return depth;//在这个题目中,我们认为的高度是从根节点到叶子节点最长路径上结点的数量
//所以,如果这个二叉树只有一个节点,那么这个树的高度就是1
}
更多推荐
已为社区贡献1条内容
所有评论(0)