找回密碼
 立即注冊(cè)

QQ登錄

只需一步,快速開始

搜索
查看: 2396|回復(fù): 0
打印 上一主題 下一主題
收起左側(cè)

二叉樹的深度問題

[復(fù)制鏈接]
跳轉(zhuǎn)到指定樓層
樓主
ID:109770 發(fā)表于 2016-3-22 23:37 | 只看該作者 回帖獎(jiǎng)勵(lì) |倒序?yàn)g覽 |閱讀模式
題目:二叉樹用二叉鏈表表示,編寫求二叉樹深度的算法。
答案是:
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));
}



分享到:  QQ好友和群QQ好友和群 QQ空間QQ空間 騰訊微博騰訊微博 騰訊朋友騰訊朋友
收藏收藏 分享淘帖 頂 踩
回復(fù)

使用道具 舉報(bào)

本版積分規(guī)則

小黑屋|51黑電子論壇 |51黑電子論壇6群 QQ 管理員QQ:125739409;技術(shù)交流QQ群281945664

Powered by 單片機(jī)教程網(wǎng)

快速回復(fù) 返回頂部 返回列表