|
題目:二叉樹用二叉鏈表表示,編寫求二叉樹深度的算法。
答案是:
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)
}
關(guān)于遞歸,你可以看成是一句一句往下運(yùn)行嘛。需要保存狀態(tài)的時(shí)候,系統(tǒng)就會(huì)自動(dòng)用棧幫你保存。就依你說得那個(gè)為例:
n為全局變量,初值為0;
第一次調(diào)用height(T),假設(shè)T!=NULL
由于T!=NULL:跳過if (T==NULL) return 0;
關(guān)鍵到了u=height(T->lchild); 調(diào)用本身的函數(shù):此時(shí)的T->lchild保存在棧中,既然是調(diào)用就得從函數(shù)開頭執(zhí)行:
看下這時(shí)候T2(其實(shí)就是T->lchild),if (T==NULL) return 0;
這里假設(shè)T不是NULL,就繼續(xù)運(yùn)行在遇到u=height(T->lchild); 在調(diào)這個(gè)函數(shù)本身——
這里就假設(shè)它為T->lchild==NULL吧。這下可好,這個(gè)函數(shù)執(zhí)行return 0;
慢著:第二次函數(shù)調(diào)用u=height(T->lchild)中的函數(shù)值已經(jīng)計(jì)算出來啦。這時(shí)u=0;
你還記得第二次調(diào)用運(yùn)行到了v=height(T->rchild); 這句話吧?好,這個(gè)過程就和u=height(T->lchild)完全一樣。
這里也假設(shè)得到的v=0
則第二次調(diào)用到了if (u>n) return (u+1)
return (v+1)
得到一個(gè)返回值,不如就假設(shè)u〉n,于是返回值1;
好,這一波完畢;
你還記得第一次調(diào)用的height吧,這時(shí)把返回值給u,u=1;
然后執(zhí)行到第一次調(diào)用中的v=height(T->rchild); 了。分析同上。
這個(gè)過程的確比較復(fù)雜。慢慢琢磨吧。呵呵。
基本思路就是如果當(dāng)前節(jié)點(diǎn)還有子節(jié)點(diǎn),則繼續(xù)訪問,遞歸的找尋子節(jié)點(diǎn)直到葉子節(jié)點(diǎn)為止。
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是全局變量,是結(jié)果
實(shí)際上最好不用什么全局變量
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));
}
|
|