具有結點的完全二叉樹的深度為,具有256個結點的完全二叉樹的深度為 。

時間 2021-07-18 15:47:25

1樓:匿名使用者

根據「二叉樹的第i層至多有2^(i − 1)個結點;深度為k的二叉樹至多有2^k − 1個結點(根結點的深度為1)」這個性質:

因為2^9-1 < 700 < 2^10-1 ,所以這個完全二叉樹的深度是10,前9層是一個滿二叉樹,

這樣的話,前九層的結點就有2^9-1=511個;而第九層的結點數是2^(9-1)=256

所以第十層的葉子結點數是700-511=189個;

現在來算第九層的葉子結點個數。

由於第十層的葉子結點是從第九層延伸的,所以應該去掉第九層中還有子樹的結點。因為第十層有189個,所以應該去掉第九層中的(189+1)/2=95個;

所以,第九層的葉子結點個數是256-95=161,加上第十層有189個,最後結果是350個。

還是根據「二叉樹的第i層至多有2^(i − 1)個結點;深度為k的二叉樹至多有2^k − 1個結點(根結點的深度為1)」這個性質:

2^4-1 <16< 2^5-1,所以這個完全二叉樹有5層,其深度為5.

2樓:我叫多了個餘

什麼叫二叉樹的度?帶你瞭解它的特點

3樓:匿名使用者

為9啊255個結點排滿8層

多一個結點

所以一共有9層

12個結點的平衡二叉樹的最大深度為

4樓:蹦迪小王子啊

假設nh表示深bai度為h的平衡二叉樹中含有du的最少的結點數目。zhi那麼,

daon0=0,n1=1,n2=2,並且nh=nh-1+nh-2+1。

根據公式內先計算出n3

n3=2+1+1

計算出n4

n4=4+2+1

最後出容結果

n5=7+4+1

這時候n5就等於12

n後面跟的數字就是深度

5樓:還傻傻的等你

那個是o(log2n)是數量級,不能在公式裡算。

你層層巢狀算就好了。

n5=n4+n3+1

依次類推。

n1=1 n2=2 n3=4 n4=7

6樓:堯堯堯掉線了

這個公式的根節點不算高度,所以結果要加,1

7樓:走在鄉間的天蠍

二叉樹的深度為

bai12。

因為葉子節點為

du1個,按zhi二叉樹理論得出(任意一dao棵專二叉樹中度為0的節點總是比

屬度為2的節點多一個),故得出此二叉樹度為2的節點為0個。

12(總節點)-1(度為0)- 0(度為2)=11(度為1)。

故證明此二叉樹每層只有1個節點,總共12層。

8樓:qq群

o(log2n)當n無窮大時忽略常數的

9樓:匿名使用者

上面答案是錯的,明顯

明顯 用公式nh=n(h-1)+n(h-2)+1

你算一下 當h=5時 正好是12

10樓:依然愛的不是你

n5=12 五層 結點12個

11樓:花語花惜

是五 我感覺那個公式不合適

12樓:想問什麼專業

開玩笑,12層怎麼平衡

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

13樓:

具有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時,命題成立。

14樓:荔枝in時尚

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

二叉樹的計算方法:

若一棵二叉樹為空,則其深度為0,否則其深度等於左子樹和右子樹的最大深度加1,即有如下遞迴模型:

depth(b)=0 /*如果b=null*/

depth(b)=max(depth(b->left,b->right)+1 /*其它*/

因此求二叉樹深度的遞迴函式如下:

int depth(btree *b) }

二叉樹的基本性質

★樹的基本定義

1、樹是n(n>=0)個結點的有限集

2、樹的結點包含一個資料元素及若干指向其子樹的分支

3、結點擁有的子樹數稱為結點的度

4、度為0的結點稱為葉子或終端結點

5、樹的度是樹內各結點的度的最大值

6、結點的層次從根開始定義起,根為第一層,根的孩子為第二層

7、樹中結點的最大層次稱為樹的深度或高度

8、如果將樹中結點的各子樹看成從左至右是有次序的(即不能互換),則稱該樹為有序樹,否則稱為無序樹。在有序樹中,最左邊的子樹的根稱為第一個孩子,最右邊的稱為最後一個孩子。

★二叉樹的定義

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

★二叉樹的性質

性質一 在二叉樹的第i層上至多有2i-1個結點

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

性質三 對任何一棵二叉樹t,如果其終端結點數為n0,度為2的結點數為n2,則n0=n2+1

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

性質五 如果對一棵有n個結點的完全二叉樹(其深度為「log2n」+1)的結點按層序編號(從第1層到第「log2n」+1層,每層從左到右),則對任一結點i(1≤i≤n),有

①如果i=1,則結點i是二叉樹的根,無雙親;如果i>1,則其雙親parent(i)是結點「i/2」

②如果2i>n,則結點n無左孩子(結點i為葉子結點);否則其左孩子lchild(i)是結點2i

③如果2i+1>n,則結點i無右孩子,否則其右孩子rchild(i)是結點2i+1

★先序遍歷二叉樹的操作定義

若二叉樹為空,則空操作,否則

(1)訪問根結點

(2)先序遍歷左子樹

(3)先序遍歷右子樹

★中序遍歷二叉樹的操作定義

若二叉樹為空,則空操作,否則

(1)中序遍歷左子樹

(2)訪問根結點

(3)中序遍歷右子樹

★後序遍歷二叉樹的操作定義

若二叉樹為空,則空操作,否則

(1)後序遍歷左子樹

(2)後序遍歷右子樹

(3)訪問根結點

15樓:匿名使用者

k層完全二叉樹,就是前(k-1)層為滿二叉樹,第k層均為葉結點,可以不滿。所以結點與深度的關係為:

2 ^ ( k - 1 ) - 1 < n <= 2 ^ k - 1。 所以k = [ ( n + 1 ) 以 2 為底取對數,然後向上取整 ]。

16樓:it達人

結論:⌊log2k⌋+1

一棵完全二叉樹共有結點則在該二叉樹中有多少葉子結點

迮玉芬能寅 完全二叉樹是指這樣的二叉樹 除最後一層外,每一層上的結點數均達到最大值 在最後一層上只缺少右邊的若干結點。更確切地說,如果一棵具有n個結點的深度為k的二叉樹,它的每一個結點都與深度為k的滿二叉樹中編號為1 n的結點一一對應,這棵二叉樹稱為完全二叉樹。可以根據公式進行推導,假設n0是度為0...

設一棵完全二叉樹共有結點,則在該二叉樹中有

你錯誤在 所以缺少了11個右結點 的 右 字上。是事實是最後一層上少了倒著少了11個結點。明確的說是少了6個右,5個左。所以,應該256 11,但是由於最後一層少了11個結點,所以上一層多了5個葉子結點,所以最終答案應該是 256 11 5 250 根據二叉樹的性質 對於一棵非空的二叉樹,如果葉子節...

在具有2n個結點的完全二叉樹中,葉子結點個數為

甜美志偉 選c。解析 根據完全二叉樹的性質 具有n個結點的完全二叉樹的深度為 log2n 1。本題中完全二叉樹共有256個結點,則深度為 log2256 1 8 1 9。完全二叉樹的性質 1 所有的葉結點都出現在第k層或k l層 層次最大的兩層 2 對任一結點,如果其右子樹的最大層次為l,則其左子樹...