1樓:匿名使用者
完全二叉樹,可以來看做是滿二叉源樹在最bai後一層從右往左砍掉一些節點。注du意,zhi滿二叉樹的所有節點的度都是dao2或者0,沒有度為1的節點。
如果從滿二叉樹中在最後一層自左向右砍掉的節點數是偶數,那麼該完全二叉樹中度為1的節點數就是0。如果砍掉的節點數是奇數,那麼該完全二叉樹中就有且僅有一個節點的度為1.
為什麼完全二叉樹中度為1的結點只能是1或0?
2樓:流火之雲
滿二叉樹的所有節點的度都是2或者0,沒有度為1的節點。
完全二叉樹,可以看做是滿二叉樹在最後一層從右往左砍掉一些節點。
如果從滿二叉樹中在最後一層自左向右砍掉的節點數是偶數,那麼該完全二叉樹中度為1的節點數就是0。
如果砍掉的節點數是奇數,那麼該完全二叉樹中就有且僅有一個節點的度為1.
完全二叉樹:
若設二叉樹的深度為h,除第 h 層外,其它各層 (1~h-1) 的結點數都達到最大個數,第 h 層所有的結點都連續集中在最左邊,這就是完全二叉樹。
完全二叉樹是由滿二叉樹而引出來的。對於深度為k的,有n個結點的二叉樹,當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。
一棵二叉樹至多隻有最下面的一層上的結點的度數可以小於2,並且最下層上的結點都集中在該層最左邊的若干位置上,則此二叉樹成為完全二叉樹。
滿二叉樹 :
又叫full binary tree. 除葉子節點外,每一層上的所有節點都有兩個子節點(最後一層上的無子結點的結點為葉子結點)。也可以這樣理解,除葉子結點外的所有節點均有兩個子節點。
節點數達到最大值。所有葉子結點必須在同一層上.
兩者的區別:
完全二叉樹:除最後一層可能不滿以外,其他各層都達到該層節點的最大數,最後一層如果不滿,該層所有節點都全部靠左排
滿二叉樹:所有層的節點數都達到最大
3樓:您輸入了違法字
因為二叉樹所有結點滴個數都不大於2,所以結點總數n=n0+n1+n2 (1)
又因為度為1和度為2的結點分別有1個子樹和2個子樹,所以,二叉樹中子樹結點就有n(子)=n1+2n2
二叉樹中只有根節點不是子樹結點,所以二叉樹結點總數n=n(子)+1 即 n=n1+2n2+1 (2)
結合(1)式和(2)式就得n0=n2+1
完全二叉樹是效率很高的資料結構,完全二叉樹是由滿二叉樹而引出來的。對於深度為k的,有n個結點的二叉樹,當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。
可以根據公式進行推導,假設n0是度為0的結點總數(即葉子結點數),n1是度為1的結點總數,n2是度為2的結點總數,則 :
1n= n0+n1+n2 (其中n為完全二叉樹的結點總數);又因為一個度為2的結點會有2個子結點,一個度為1的結點會有1個子結點,除根結點外其他結點都有父結點,
2n= 1+n1+2*n2 ;由1、2兩式把n2消去得:n= 2*n0+n1-1,由於完全二叉樹中度為1的結點數只有兩種可能0或1,由此得到n0=n/2 或 n0=(n+1)/2。
簡便來算,就是 n0=n/2,其中n為奇數時(n1=0)向上取整;n為偶數時(n1=1)。可根據完全二叉樹的結點總數計算出葉子結點數。
4樓:匿名使用者
看圖~ 6-12的那個結點就是度為一的結點~ 只有一個~ 所謂度就是結點的後面有幾個分叉~ 即直接後驅~完全二叉樹的定義:二叉樹的高度為h,除第 h 層外,其它各層 (1~h-1) 的結點數都達到最大個數,第 h 層所有的節點都連續集中在最左邊~ 圖中的8、9、10、11、12就是第h層上的結點~即最後一層上的結點~二叉樹定義第 h 層所有的節點都連續集中在最左邊,圖中結點6與7就不能發生下面的情況:6結點只有一個左子樹,而7結點也有子樹,以為都要從左邊排~ 必須排在6結點的右子樹上,也就是說最後一層的結點的最後一個要麼是度為1,要麼度為2。
自己理解吧~ 希望能幫到忙~
5樓:匿名使用者
完全二叉樹,可以看做是滿二叉樹在最後一層從右往左砍掉一些節點。注意,滿二叉樹的所有節點的度都是2或者0,沒有度為1的節點。
如果從滿二叉樹中在最後一層自左向右砍掉的節點數是偶數,那麼該完全二叉樹中度為1的節點數就是0。如果砍掉的節點數是奇數,那麼該完全二叉樹中就有且僅有一個節點的度為1.
一棵完全二叉樹共有360個結點,該二叉樹中度為1的結點數為多少?
6樓:啊紅啊
總結點數=葉子結點數+度為1的結點數+度為2的結點數。
葉子結點數=度為2的結點數+1。
:對於一個完全二叉樹來說,度為一的結點樹,只有0,或者1,兩種可能。
公式一:葉子結點樹=度為2的結點樹+1.=總結點數/2公式二:
總結點樹=度為1的結點樹+度為2的結點樹+葉子結點樹由題我們可以知道:完全二叉樹的總結點數為:360所以由公式一可知:
葉子結點數=總結點數/2=360/2=180又因為公式一中:葉子結點樹=度為2的結點樹+1——我們可以推出:度為2的結點樹=葉子結點樹-1=180-1=179
由公式二我們可以推出:度為1的結點樹=總結點樹-度為2的結點樹-葉子結點樹=360-179-180=1
一棵完全二叉樹共有360個結點,該二叉樹中度為1的結點數為
7樓:啊紅啊
總結點數=葉子結點數+度為
1的結點數+度為2的結點數。
葉子結點數=度為2的結點數+1。
:對於一個完全二叉樹來說,度為一的結點樹,只有0,或者1,兩種可能。
公式一:葉子結點樹=度為2的結點樹+1.=總結點數/2公式二:
總結點樹=度為1的結點樹+度為2的結點樹+葉子結點樹由題我們可以知道:完全二叉樹的總結點數為:360所以由公式一可知:
葉子結點數=總結點數/2=360/2=180又因為公式一中:葉子結點樹=度為2的結點樹+1——我們可以推出:度為2的結點樹=葉子結點樹-1=180-1=179
由公式二我們可以推出:度為1的結點樹=總結點樹-度為2的結點樹-葉子結點樹=360-179-180=1
8樓:烏石
完全二叉樹度為1的結點數為要麼為1,要麼為0;由於度為2的結點數和度為0結點數相差為1;所以兩者之和必為奇數,現在總結點數為偶數,所以度為1的結點數應為奇數,所以有一個度為1的結點。
一顆完全二叉樹共有360個節點,則在該二叉樹中度為1的結點個數怎麼算? 希望指點迷津~謝
9樓:匿名使用者
設二叉樹中度為
0,1,2結點數分別為n0, n1, n2根據二叉樹的性質,度為0葉子結點數n0 = n2 + 1,其中n2為度為2的結點數
於是n0 + n1 + n2 = 360,也就是2n2 + 1 + n1 = 360
因此n1必定是奇數
按照完全二叉樹的特徵,其中度為1的結點個數最多1個因此該完全二叉樹中度為1結點個數就是1 了
一棵完全二叉樹有n個結點,求完全二叉樹中度為0,1,2的結點各有多少
10樓:匿名使用者
根據來二叉樹的性質n0 = n2 + 1以及完全二自叉樹中bai度為1的結點個數du最多為1,可以推出如下
zhi結論
如果完全二dao叉樹中結點個數n是偶數:
度為0的結點個數n0 = n / 2,度為1的結點個數n1 = 1,度為2結點個數為n / 2 - 1
如果完全二叉樹中結點個數n是奇數:
度為0的結點個數n0 = (n + 1)/ 2,度為1的結點個數n1 = 1,度為2結點個數為(n - 1) / 2
11樓:芭緹
n為奇數時,n1=0
急求大神 1.求二叉樹度為0的結點數 2.求二叉樹度為1的結點數 30
12樓:
根據二叉樹性質3: 在任意-棵二叉樹中,若終端結點的個數為n0,度為2的結點數為n2,則no=n2+1。
證明:因為二叉樹中所有結點的度數均不大於2,所以結點總數(記為n)應等於0度結點數、1度結點(記為n1)和2度結點數之和:
n=no+n1+n2 (式子1)
另一方面,1度結點有一個孩子,2度結點有兩個孩子,故二叉樹中孩子結點總數是:
nl+2n2
樹中只有根結點不是任何結點的孩子,故二叉樹中的結點總數又可表示為:
n=n1+2n2+1 (式子2)
由式子1和式子2得到:
no=n2+1
注:上述公式字母n代表二叉樹結點總數,n0代表度為0的結點個數,n1代表度為1的結點個數,n2代表度為2的結點個數。
深度為7的完全二叉樹中共有結點該完全二叉樹中的葉子結點有多少
這題答bai題方法有兩個公du式可用，深度為zhik的完全二叉樹最dao多有2的k次 1個結點，第k層最多內有容2的 k 1 次結點。前6層總共結點數 2 6 1 63，這裡總共有125個，所以第7層有125 63 62個。另外，第7層最多有64個，第6層32個。所以葉子結點數 第6層葉子結點 第7...
若一棵二叉樹有葉子結點,則該二叉樹中度為2的結點個數是
節點個數是10。1 總結點數n n0 n1 n2，總結點數等於葉子結點數 度為內1的結點數 度為2的結點數。另外容，考慮一下二叉樹中的線，度為1的結點出去的線為1，度為2的結點線出去的為2。每個結點除根結點外都有一條線進入，所以n 1 2n2 n1。2 在電腦科學中，二叉樹是每個節點最多有兩個子樹的...
設一棵完全二叉樹共有結點，則在該二叉樹中有多少葉子結
根據完全二叉樹的性質，葉結點的個數應該為 結點總數 2 取上整，本題則為700 2 350，取上整還是350，所以有350個葉子節點 有350個節點,演算法是這樣的,你建個excel 二叉樹,第一層是1第二層是2,第三層是4,每一層是上一層數乘內2.1248163264128256512弄成這樣,求...