導航:首頁 > 源碼編譯 > 求樹的深度遞歸演算法

求樹的深度遞歸演算法

發布時間:2022-05-23 21:17:39

⑴ 關於遞歸演算法求二叉樹深度演算法

u,v 分別求出當前節點左子樹和右子樹的深度(高度),
然後當前節點的 深度就等於左右子樹裡面較大的那個+1.

if (u>n) return (u+1)
return (v+1)
這句就是返回較深的+1.

u=height(T->lchild);
v=height(T->rchild);

這兩句就是遞歸的調用,求深度了。

if (T==NULL) return 0;

這個就是終止條件了,如果沒有子節點就返回。

⑵ 關於求二叉樹深度的遞歸演算法

關於遞歸,你可以看成是一句一句往下運行嘛。需要保存狀態的時候,系統就會自動用棧幫你保存。就依你說得那個為例:
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); 了。分析同上。

這個過程的確比較復雜。慢慢琢磨吧。呵呵。

⑶ Java數據結構二叉樹深度遞歸調用演算法求內部演算法過程詳解

二叉樹

1

2
3
4
5
6
7
這個二叉樹的深度是3,樹的深度是最大結點所在的層,這里是3.
應該計算所有結點層數,選擇最大的那個。
根據上面的二叉樹代碼,遞歸過程是:
f
(1)=f
(2)+1
>
f
(3)
+1
?
f(2)
+
1
:
f(3)
+1
f(2)
跟f(3)計算類似上面,要計算左右結點,然後取大者
所以計算順序是f(4.left)
=
0,
f(4.right)
=
0
f
(4)
=
f(4.right)
+
1
=
1
然後計算f(5.left)
=
0,f(5.right)
=
0
f
(5)
=
f(5.right)
+
1
=1
f(2)
=
f(5)
+
1
=2
f(1.left)
計算完畢,計算f(1.right)
f(3)
跟計算f(2)的過程一樣。
得到f(3)
=
f(7)
+1
=
2
f(1)
=
f(3)
+
1
=3
12345if(depleft>depright){ return depleft+1;}else{ return depright+1;}
只有left大於right的時候採取left
+1,相等是取right

⑷ 試編寫一個計算二叉樹深度的遞歸演算法

int Depth(BiTree T)/* 深度 */
{if(T==NULL)
return(0);
else
return 1+(Depth(T->lchild)>Depth(T->rchild)? Depth(T->lchild):Depth(T->rchild));
}

⑸ 如何求二叉樹深度的遞歸演算法是什麼

int height(Bitree T) { if (T==NULL) return 0; u=height(T->lchild); v=height(T->rchild); if (u>n) return (u+1) //n應該是v return (v+1) } if 中的n應該是v。 其思想是,一個節點的深度是他的兩個子節點中深度的最大值再加上1。

⑹ 求解具有n個結點的完全二叉樹的深度,寫出計算過程

具有n個結點的完全二叉樹的深度為「log2n」+1

計算過程如下:

採用數學歸納法證明。

當n=1=2^1-1時,命題成立。

假設當n<=2^k-1時具有n個結點的完全二叉樹的深度為「log2n」+1,

則當n=2^k(以及2^k+1,...,2^(k+1)-1)時,由歸納假設知:

前2^k-1個結點構成深度為「log2n」+1的樹;

再由完全二叉樹的定義知:

剩餘的1(或2,...,2^k)個結點均填在第「log2n」+2層上(作為「葉子」),深度剛好增加了1,

故n<=2^(k+1)-1時,命題成立。

(6)求樹的深度遞歸演算法擴展閱讀:

二叉樹是一種樹型結構,它的特點是每個結點至多隻有二棵子樹(即二叉樹中不存在度大於2的結點),並且,二叉樹的子樹有左右之分,其次序不能任意顛倒。

二叉樹的性質

1、在二叉樹的第i層上至多有2i-1個結點;

2、深度為k的二叉樹至多有2k-1個結點(k>=1);

3、對任何一棵二叉樹T,如果其終端結點數為N0,度為2的結點數為N2,則N0=N2+1;

4、具有n個結點的完全二叉樹的深度為「log2n」+1。

⑺ 寫出二叉樹深度的演算法

基本思路就是如果當前節點還有子節點,則繼續訪問,遞歸的找尋子節點直到葉子節點為止。
procere
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));
}

⑻ 用遞歸的方法設計一個建立二叉樹並求其深度的演算法,求完整的。

先序遍歷求二叉樹高度int PreTreeDepth(BiTree root)
#define null 0
typedef struct node
{
elementtype data;
struct node *RChild,*LChild;
}BitNode,*BiTree;
int PreTreeDepth(BiTree root)
{/*先序遍歷求二叉樹高度,root為指向二叉樹根結點的指針*/
int lc,rc,max=0;
if(root==null)
return max;
lc=PreTreeDepth(root->LChild);
rc=PreTreeDepth(root->RChild);
max=lc>rc?lc:rc;
return max+1;
}
後序遍歷求二叉樹高度int PostTreeDepth(BiTree root)
#define null 0
typedef struct node
{
elementtype data;
struct node *RChild,*LChild;
}BitNode,*BiTree;
int PostTreeDepth(BiTree root)
{/*後序遍歷二叉樹,root為指向二叉樹(或某一子樹)根結點的指針*/
int max=0;
if(root!=null)
{
max=PostTreeDepth(root->LChild)+1;
if(max<=PostTreeDepth(root->RChild))
max=PostTreeDepth(root->RChild)+1;
}
return max;
}

⑼ 用遞歸演算法求二叉樹的深度

return語句僅結束當前的函數調用。如果是循環調用,僅結束當前層次的調用,並返回上一層次。
對於
int depth(BTree root){
...
if(!root)
return 0;
else{
...
if(ldepth >= rdepth)
return ldepth+1;
else
return rdepth+1;
}
return 1;
}
最後一個「return 1;」不會被執行到的。

⑽ 在求二叉樹的深度遞歸演算法中程序是如何實現深度的計算的

空節點(指針值為NULL)的深度為0;
葉子節點(左、右子樹均為空節點)的深度為1;
其它節點,其深度為其左、右子樹中深度較大者加1。

閱讀全文

與求樹的深度遞歸演算法相關的資料

熱點內容
程序員面試金典第6版 瀏覽:718
內存2g編譯安卓 瀏覽:414
單片機小數點怎麼亮 瀏覽:414
安卓手機怎麼設置健康碼雙擊兩下就出來 瀏覽:266
同一個文件夾可以存在兩個相同的文件嗎 瀏覽:535
動態重編譯jit 瀏覽:132
android藍牙音頻 瀏覽:451
mc國際版怎麼加伺服器 瀏覽:816
phphtaccess配置 瀏覽:747
dos命令鎖定 瀏覽:486
python中調換數據位置 瀏覽:300
武漢市中石油加油什麼APP優惠 瀏覽:545
程序員33歲以後的規劃 瀏覽:858
招標文件加密流轉 瀏覽:897
源碼數據盈利可信嗎 瀏覽:860
android閃爍圖標 瀏覽:942
程序員呼蘭搞笑 瀏覽:352
蘋果怎麼關閉自動排序app 瀏覽:963
國外可以訪問到用什麼伺服器地址 瀏覽:949
揚州前端程序員私活價格 瀏覽:990