題目：二叉樹用二叉鏈表表示，編寫求二叉樹深度的算法。
答案是：
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));
}
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
