NO IMAGE

轉載於:http://blog.pfan.cn/edwardguo/52433.html

題目:二叉樹用二叉連結串列表示,編寫求二叉樹深度的演算法。

答案是:
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));
}