题目：二叉树用二叉链表表示，编写求二叉树深度的算法。 答案是： 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) } 关于递归，你可以看成是一句一句往下运行嘛。需要保存状态的时候，系统就会自动用栈帮你保存。就依你说得那个为例： 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); 了。分析同上。 这个过程的确比较复杂。慢慢琢磨吧。呵呵。 基本思路就是如果当前节点还有子节点，则继续访问，递归的找寻子节点直到叶子节点为止。 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)); }

评论