|
|
題目：二叉樹用二叉鏈表表示，編寫求二叉樹深度的算法。
答案是：
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));
}
|
|
