求讲授二叉树求高度的递归算法-Java教程-爱易网页

求讲授二叉树求高度的递归算法

日期：2014-05-20　浏览次数：21015 次

求讲解二叉树求高度的递归算法
这是一个二叉树求高度的算法我看了半天没弄明白他是递归比较两个左子树和右子树的高度然后再把较大的那个+1 得到二叉树的高度但是他的递归是到底怎样算出高度的？？？就是最后那句怎么算出高度的？？？？

Java code


public int height(BinaryTreeNode p) {  //p是一个二叉树根节点的引用
    if(p == null){
       System.out.println("高度为0")
       return 0;
     }else{
       return 1 + max(height(llink),height(rlink));  //这个LLINK 和RLINK分别是p的两个指针，指向左子树和右子树
     }
}

------解决方案--------------------
你可以这样理解：
首先你就当height可以求出某个节点的高度
从根节点开始，怎么表示这棵树的高度？根节点一层，左右子树，谁层数多，当然加上谁的啦
所以 return 1 + max(height(llink),height(rlink))；
然后对llink或者rlink都是同样的理解
最后什么时候返回？当然是节点为空的时候啦，因为一个叶子节点已经是最后一层，它的左右节点
都是空的。

希望能帮到lz
------解决方案--------------------
排版有点问题

Java code


左子树的高度height(llink) 
右子树的高度height(rlink) 
这两个高度当然要取更大的数 对吧 
加上自己的节点 1： 
      本次递归的p------> O(p) 
                      /  \ 
                     /    \ 
height(llink)------>左子树  右子树 <----------height(rlink) 
总的高度 为 1 + max(height(llink),height(rlink));