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

時間 2021-09-15 00:13:00

1樓:甜美志偉

選c。【解析】根據完全二叉樹的性質:具有n個結點的完全二叉樹的深度為[log2n]+1。本題中完全二叉樹共有256個結點,則深度為[log2256]+1=8+1=9。

完全二叉樹的性質:

(1)所有的葉結點都出現在第k層或k-l層(層次最大的兩層)。

(2)對任一結點,如果其右子樹的最大層次為l,則其左子樹的最大層次為l或l+l。

擴充套件資料:

完全二叉樹的特點

葉子結點只可能在最大的兩層上出現,對任意結點,若其右分支下的子孫最大層次為l,則其左分支下的子孫的最大層次必為l 或 l+1;

出於簡便起見,完全二叉樹通常採用陣列而不是連結串列儲存,其儲存結構如下:

var tree:array[1..n]of longint;

對於tree[i],有如下特點:

(1)若i為奇數且i>1,那麼tree的左兄弟為tree[i-1];

(2)若i為偶數且i(3)若i>1,tree的父親節點為tree[i div 2];

(4)若2*i<=n,那麼tree的左孩子為tree[2*i];若2*i+1<=n,那麼tree的右孩子為tree[2*i+1];

(5)若i>n div 2,那麼tree[i]為葉子結點(對應於(3));

(6)若i<(n-1) div 2.那麼tree[i]必有兩個孩子(對應於(4))。

(7)滿二叉樹一定是完全二叉樹,完全二叉樹不一定是滿二叉樹。

完全二叉樹第i層至多有2^(i-1)個節點,共i層的完全二叉樹最多有2^i-1個節點。

完全二叉樹的特性是:

1)只允許最後一層有空缺結點且空缺在右邊,即葉子結點只能在層次最大的兩層上出現;

2)對任一結點,如果其右子樹的深度為j,則其左子樹的深度必為j或j+1。 即度為1的點只有1個或0個

2樓:l家的銀

答案選a. 望採納

由二叉樹的定義可知,樹中必定存在度為0的結點和度為2的結點,設度為0的結點有a個,根據度為0的結點(即葉子結點)總比度為2的結點多一個,則度為2的結點有a-1個。

再根據完全二叉樹的定義,度為1的結點有0個或1個,假設度為1的結點有0個,則a+0+a-1=2n,得2a=2n+1,由於結點個數必須為整數,假設不成立;當度為1的結點為1個時,a+1+a-1=2n,得a=n,即葉子結點個數為n。

3樓:聽不清啊

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

這應該是答案d吧?

二叉樹有n個度為2的節點,該二叉樹中葉子結點個數為多少 5

4樓:子不語望長安

n+1。

解題過程:

一、對任何一棵二叉樹t,如果其終端節點數為n0,度為2的節點數為n2,則n0=n2+1.

二、設n1為二叉樹t中度為1的結點數

三、因為二叉樹中所有結點的度軍小於或等於2,

所以其結點總數為

n=n0+n1+n2 (1)

再看二叉樹中的分支數.除了根結點外,其餘結點都有一個分支進入,設b為分支總數,則n=b+1.由於這些分支是由度為1或2的結點射出的,所以b=n1+2n2.

於是得n=n1+2n2+1 (2)

四、由式(1)(2)得

n0=n2+1

擴充套件資料:

二叉樹具有以下的特點:

(01) 每個節點有零個或多個子節點;

(02) 沒有父節點的節點稱為根節點;

(03) 每一個非根節點有且只有一個父節點;

(04) 除了根節點外,每個子節點可以分為多個不相交的子樹。

基本術語:

結點的度:結點擁有的子樹的數目。

葉子:度為零的結點。

分支結點:度不為零的結點。

樹的度:樹中結點的最大的度。

層次:根結點的層次為1,其餘結點的層次等於該結點的雙親結點的層次加1。

樹的高度:樹中結點的最大層次。

無序樹:如果樹中結點的各子樹之間的次序是不重要的,可以交換位置。

有序樹:如果樹中結點的各子樹之間的次序是重要的, 不可以交換位置。

森林:0個或多個不相交的樹組成。對森林加上一個根,森林即成為樹;刪去根,樹即成為森林。

5樓:匿名使用者

自己畫一下圖很快就可以研究出來

度為2的一定比度為0(葉子)多一個,因此葉子為n+1個

6樓:匿名使用者

n+1對任何一個二叉樹,度為0的點(即葉子節點)總是比度為2的結點多一個。這是二叉樹的主要性質之一。

7樓:匿名使用者

該二叉樹中葉子結點個數為n+1個

證明下具有n個結點的非空滿二叉樹,其葉結點的數目為(n+1)/2

8樓:隨機因子

設內部節點數為a,葉節點數為b,明顯有a+b=n (1)非空滿二叉樹中所有節點的出度正好等於入度,每個內部節點出度為2,葉節點出度為0,所有節點的出度和為2a;根節點入度為0,其他節點的入度為1,所有節點的入度和為a+b-1;因此有2a=a+b-1 (2)

由(1),(2)得 b=(n+1)/2, a=(n-1)/2另外可得 b=a+1

也就是說,非空滿二叉樹的葉節點數正好比內部節點數多1

n個結點的滿二叉樹共有多少葉子結點

9樓:匿名使用者

源數為(n + 1) / 2

推導過程為:

由二叉樹的屬性可知n2 = n0 - 1。由於滿二叉樹沒有度為1的結點,所以n0 + n2 = n

因此2 × n0 - 1 = n。n0 = (n + 1) / 2

數列問題:一個完全二叉樹中,如果葉子結點的個數為n。則這顆二叉樹一共有幾個結點

10樓:匿名使用者

有二叉樹基本性質n0=n2+1和總結的個數=n0+n1+n2,=》節點個數=n0+n0-1+n1,即2n0-1+n1

其中n0為度為0的節點,也就是葉子節點,n1為度為1的節點,由於完全二叉樹中度為1的節點只有1個,或者沒有,並且這兩種情況普遍存在,故節點數=2n0-1+1或者2n0-1,由於n0=n,故二叉樹共有2n或者2n-1個節點。

11樓:

解:因是完全二叉樹,故度數只能是1,2,3.設度數為2的結點為m,則全部結點數為m+n+1

所有度數之和=3m+n+2=邊的2倍,另一方面,樹中邊的數目=結點數-1

所以:3m+n+2=2(m+n),解得:m=n-2,故全部結點數為2n-1

重新看了上述解答,感覺沒錯。完全二叉樹的概念保證了每個點的出度為2或者0,為2時,該點的度數為3,為0時度數為1,就是葉子。

既然樓主就這樣講了,就再不說什麼了,對完全二叉樹的概念的描述,很多書上有定義的。

在深度為5的滿二叉樹中,葉子結點的個數為多少?

12樓:晚夏落飛霜

葉子結點共有16個。

在一棵滿二叉樹中,節點的個數為2^n-1,葉子節點的個數為:2^(n-1)。

一個二叉樹,如果每一個層的結點數都達到最大值,則這個二叉樹就是滿二叉樹。也就是說,除最後一層外,每一層上的所有節點都有兩個子節點,即在滿二叉樹的第k層上有2^(k-1)個節點,且深度為m的滿二叉樹中有2^m-1個節點。

滿二叉樹滿足如下性質。

1、一個層數為k 的滿二叉樹總結點數為:2^k-1。因此滿二叉樹的結點數一定是奇數個。

2、第i層上的結點數為:2^i-1

3、一個層數為k的滿二叉樹的葉子結點個數(也就是最後一層):2^k-1。

滿二叉樹和完全二叉樹的區別

1、定義不同

完全二叉樹指除最後一層外,每一層上的節點數都達到最大值;在最後一層上只缺少右邊的若干節點。

滿二叉樹指每一個層的結點數都達到最大值,即除最後一層外,每一層上的所有節點都有兩個子節點。

2、關係不同

滿二叉樹一定是完全二叉樹,完全二叉樹不一定是滿二叉樹。

13樓:路莉霜安陽

其實有一種巧算的方法,深度為5,也就說滿二叉樹的最大層次是5,而葉子結點對於滿二叉樹來說就是最後一層,根據性質一在第k層上,最多有2的k-1次方的結點,所以2的5-1次方,也就是16,這樣找到規律,多大的數都不怕了

14樓:住在山崖上

在滿二叉樹的第k層上有:2的k次方減再1個結點 (樹的最大層次稱為樹的深度,沒有後件的結點稱為葉子結點。) 深度為5的滿二叉樹的葉子結點為31個

15樓:匿名使用者

在滿二叉樹的第k層上有:2^(k-1)個節點。全部的結點是2^k-1 個。

葉子節點是沒有左右孩子的節點,所以應該是16個。

16樓:安橙暖

16個 滿二叉樹最後一層結點個數就是葉子結點的個數

17樓:z暮夏錦年

啊?應該是16吧!總結點數是31個,但問的是葉子節點的個數啊,應該是16

18樓:走心逸

深度是層次最大的結點所在的層次,葉子結點是度為0的結點,深度為5的滿二叉樹,葉子結點都在第5層,n=32-1=31

19樓:匿名使用者

我想你們看了上面的圖就知道 誰對誰錯了。上圖是一個深度為5的滿二叉樹中。

往往有些事,你大可舉個例子來證明你的正誤。

正確的答案為 16

如上圖最下一排的圓圈數----16

20樓:匿名使用者

32個。根的深度為0,深度為5也就是在第6層,第6層的最多結點數位2^(6-1)

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

根據 二叉樹的第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 所以第十...

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

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

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

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