答案
設葉子節點數為n0, 度為1的節點數為n1, 度為2的節點數為n2, 總節點為n
- 當n為奇數時 n0= (n+1)/2
- 當n為偶數 n0= n/2
資料結構重修, 快要結課了, 在家苦X的複習ing......
首先得知道什麼是完全二叉樹
emmm先看看滿二叉樹(完全二叉樹是由滿二叉樹而引出來的)
滿二叉樹高度為h, 由2^(h)-1個節點構成的二叉樹稱為滿二叉樹
(圖檔來源網絡-侵删)
完全二叉樹若設二叉樹的深度為h 除第 h 層外 其它各層 1～(h-1) 的結點數都達到最大個數(即1~(h-1)層為一個滿二叉樹) 第 h 層所有的結點都連續集中在最左邊 就是完全二叉樹
(圖檔來源網絡-侵删)
正題對于一棵二叉樹, 設葉子節點數為n0, 度為1的節點數為n1, 度為2的節點數為n2
度為2的節點有2個分支, 度為1結點有1個分支, 度為0的節點有0個分支
則
n0 = n2 + 1(公式1)
證明:
(度為2的節點有2個分支, 度為1結點有1個分支, 度為0的節點有0個分支)
總分支數=2*n2 + n1
另外分支數 = n0 + n1 + n2 - 1 (每個結點上面對應一個分支，除了根節點上面沒有分支)
是以 2*n2 + n1 = n0 + n1 + n2 - 1 得 n0 = n2 + 1
假設n為完全二叉樹的結點總數, 則有
n=n0+n1+n2(公式2)
結合公式 1和2 有
n0=(n-n1+1)/2 又因為 n1 = 0 或者 n1 = 1隻有這兩種情況(
完全二叉樹的性質呀--隻有一個分支的節點要麼有, 要麼沒有, 剩下的全是兩個分支的節點和0分支的葉子節點)
- 當n為奇數時(即度為1的節點為0個) n0= (n+1)/2
- 當n為偶數(即度為1的節點為1個) n0= n/2
- n1,n2,都可以求了吧
是以一般我們的做題思路就是,
先看總節點個數, 是奇還是偶,
奇數,可知 n1 = 0; 再計算n0,
此時n0, n1都知道了, n2 = n-n1-n0;
偶數同上