北京住房与城乡建设厅网站,微信官方网站怎么进入,万网一台虚拟主机做多个网站,网站域名一年大概多少二叉树采用二叉链表存储#xff1a;编写计算整个二叉树高度的算法 (二叉树的高度也叫二叉树的深度)
代码思路#xff1a; 首先你要明白什么是树的高度#xff0c;简言之就是树有多少层#xff0c;如下图#xff1a; 下面这棵树的高度就是4 首先我们观察根节点#xff0…二叉树采用二叉链表存储编写计算整个二叉树高度的算法 (二叉树的高度也叫二叉树的深度)
代码思路 首先你要明白什么是树的高度简言之就是树有多少层如下图 下面这棵树的高度就是4 首先我们观察根节点根节点左子树高度是2右子树高度是3 那么我们取左右子树高度较大值3再加上根节点自己一个那根节点高度就是314
那么问题来了我们怎么知道根节点左右子树高度呢 那就遍历一下根节点左右子树呗问题转换成求结点左右子树高度 再然后问题就转换成求根节点左右子树的子树高度了。。。
这样是不是就是我们熟悉的递归啊。
代码实现如下
int BiTreeDepth(BiTree T) {if (T ! NULL) {//递归退出条件return 0;}int i 0;//标记左子树高度int j 0;//标记右子树高度if (T-lchild) {//如果还有左子树往下递归i BiTreeDepth(T-lchild);}else {i 0;}if (T-rchild) {//如果还有右子树往下递归j BiTreeDepth(T-rchild);}else {j 0;}return i j ? i1 : j1;//向上一层结点返回该子树的深度注意这里要1因为还有一个根节点高度
}
