Question

关于求二叉树深度的递归算法

题目：二叉树用二叉链表表示，编写求二叉树深度的算法。
答案是：
int height(Bitree T)
{
if (T==NULL) return 0;
u=height(T->lchild);
v=height(T->rchild);
if (u>n) return (u+1)
return (v+1)
}

能不能解释下，这个递归算法，在计算机内部是如何运行的？
u和v在递归的过程中，会自动加1？？
我是这样想的：
程序执行，若树不为空，则执行查找左孩子的递归，直到没有左孩子，这时返回u的值为0，
然后，计算机的堆栈弹出，继续执行程序，查找右子树，如果右子树为空，亦返回v=0。
但是，整个遍历过程是怎么将u和v继续增加的？我想不通。

谢谢了，如果能说明白的话，追50是肯定的。

Answer 1

关于递归，你可以看成是一句一句往下运行嘛。需要保存状态的时候，系统就会自动用栈帮你保存。就依你说得那个为例：
n为全局变量，初值为0；

第一次调用height(T)，假设T！=NULL
由于T!=NULL：跳过if (T==NULL) return 0;

关键到了u=height(T->lchild); 调用本身的函数：此时的T->lchild保存在栈中，既然是调用就得从函数开头执行：
看下这时候T2（其实就是T->lchild），if (T==NULL) return 0；
这里假设T不是NULL，就继续运行在遇到u=height(T->lchild); 在调这个函数本身——
这里就假设它为T->lchild==NULL吧。这下可好，这个函数执行return 0；

慢着：第二次函数调用u=height(T->lchild)中的函数值已经计算出来啦。这时u=0；

你还记得第二次调用运行到了v=height(T->rchild); 这句话吧？好，这个过程就和u=height(T->lchild)完全一样。
这里也假设得到的v=0

则第二次调用到了if (u>n) return (u+1)
return (v+1)
得到一个返回值，不如就假设u〉n，于是返回值1；
好，这一波完毕；

你还记得第一次调用的height吧，这时把返回值给u,u=1；
然后执行到第一次调用中的v=height(T->rchild); 了。分析同上。

这个过程的确比较复杂。慢慢琢磨吧。呵呵。

Answer 2

我记得数据结构书上好像是有，可能是非递归的，具体的忘记了，不过当时我也是挺懵的，到现在也不是很明白其所以然！

Answer 3

基本思路就是如果当前节点还有子节点，则继续访问，递归的找寻子节点直到叶子节点为止。

procedure tree(a:node,depth:integer);
begin
if result<depth then result:=depth;
if a.leftchild<>nil then tree(a.leftchild,depth+1);
if a.rightchild<>nil then tree(a.rightchild,depth+1);
end;

注:result是全局变量,是结果

实际上最好不用什么全局变量
int depth(node *bt)
{ if (bt==NULL)
return 0;
ldepth=depth(bt->left)+1;
rdepth=depth(bt->right)+1;
return max(ldepth,rdepth);
}

全局变量是bug
int Height(BiTree T){
int m,n;
if(!T) return(0);
else
m=Height(T->lchild);
n=Height(T->rchild);
return((m>n?m:n)+1);
}

求树深度的递归算法
// struct bnode{struct bnode *lc,*rc);
int depth(struct bnode *r)
{
return r==NULL?0:1+max(depth(r->lc),depth(r->rc));
}

Answer 4

意思就是
某结点的深度height(T)

等于他的深度最大的子树的深度height(T的最深子树)

加1 return heitht(T的最深子树)+1

Answer 5

这样理解对吗？同学？