Question

用c#递归算法求二叉树的深度

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

int depth(BTree root){
int ldepth,rdepth;
if(!root)
return 0;
else{
ldepth = depth(root-＞lchild);
rdepth = depth(root-＞rchild);
if(ldepth ＞= rdepth) //取左右子树深度的最大值加一返回
return ldepth+1;
else
return rdepth+1;
}
return 1; //只有根节点
}