第六章樹和二叉樹
從對線性結構的研究過渡到對樹形結構的研究，是資料結構課程學習的一次躍變。
6.1 樹的定義和基本術語
1. 樹的定義
樹是由n (n 0)個結點組成的有限集合。
如果n = 0，稱為空樹；
如果n > 0，則:
有乙個特定的稱之為根(root)的結點，它只有後繼，但沒有前驅；
其餘結點有且僅有乙個直接前驅，但可以有0個或多個後繼。
判斷上述圖形是不是一棵樹？看它滿足不滿足定義中的兩個條件？
有乙個特定的稱之為根(root)的結點a，它只有後繼，但沒有前驅；
其餘結點bcdefghijklm都滿足有且僅有乙個直接前驅，但可以有0個或多個後繼條件。
2、樹的基本術語
結點：乙個圓圈就是乙個結點。
結點的子樹：結點射出幾個分支結點就有幾棵子樹。結點ａ有三棵子樹，粉色的方框所劃。
結點ｂ有幾棵子樹？兩棵。綠色的方框所劃。
結點的度: 結點射出的分支數。
結點a的度是3。b 的度是2。c的度是1。……
m的度是0。
樹的度：樹內各結點度的最大值。圖示樹的度是3。
葉子結點（終端）: 度為0的結點。
f、g、i、j、k、l、m．
非終端結點: 度不為0的結點。a、b、c、d、e、h.
結點的層次: 樹中根結點的層次為1，下一層結點的層次是2，以此類推。
a的層次是1
b、c、d的層次是2。
e、f、g、h、i、j的層次是3。
k、l、m的層次是4
樹的深度: 樹中所有結點層次的最大值。圖示樹的深度是4
父結點：結點的前驅稱為該結點的父親。
b、c、d的父親都是a。
孩子結點：結點的後繼稱為該結點的孩子。
a有三個孩子：分別是b、c、d。
兄弟：同乙個父親的孩子之間互稱兄弟。
b、c、d互為兄弟。
堂兄弟：兄弟的孩子之間互稱堂兄弟。
f和g互稱堂兄弟。
有序樹、無序樹: 如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。
如果a的三棵子樹不能互換，a稱為有序樹。
如果a的三棵子樹的排列順序是無關緊要的，可以互換，a稱為無序樹。
填空：對於一棵具有n個結點的樹，該樹中所有結點的度數之和為ｎ－１。
6.2 二叉樹 (binary tree)
6.2.1二叉樹的定義
一、特點：
1、每個結點至多有兩棵子樹。（即二叉樹中不存在度大於2的結點）
2、二叉樹的子樹有左右之分，其次序不能任意顛倒。
下面的樹是不是二叉樹？
判斷題二叉樹是度為2的有序樹.（ ）
二、二叉樹的五種形態
（a）空二叉樹
（b）僅有根結點的二叉樹
（c）只有左子樹，右子樹為空的二叉樹
（d）只有右子樹，左子樹為空的二叉樹
（e）左右子樹均非空的二叉樹
6.2.2二叉樹的性質
二叉樹具有下列5個重要的性質。
【性質1】 在二叉樹的第i層上最多有個結點（i≥1）。
證明：數學歸納法。
當i=1時， 2i-1=1; 二叉樹的第1層上也只有乙個根結點，第一層的結點數1<=2i-1，所以命題成立。
假設i=k時命題成立，即第k層上結點數目最多為2k-1，
則i = k +1時，第k+1層上結點數目最多為第k層上的兩倍，即2*2k-1=2k+1-1；命題也成立。
綜上所述：命題成立。
選擇題:
在二叉樹的第三層上最多有幾個結點()（）
a.3 b.4 c.5 d.6
性質背過，到時候直接用。
【性質2】 深度為k的二叉樹最多有個結點（k≥1）。
利用性質1的結論每一層上具有的最大結點數如下表所示：
二叉樹所具有的最大結點數=
選擇題：
二叉樹的深度為4，則二叉樹最多有（ c ）個結點。
a．13b．14
c．15d．16
【性質3】 對於任意一棵二叉樹bt，如果度為0的結點（即葉子結點）個數為，度為2的結點個數為，則。
證明：設度為1的結點有n1個，總結點個數為n，分支數為e，
因為二叉樹中所有結點的度都小於等於2 ，所以有下式成立：
n = n0 + n1 + n2
（總結點數 = 度為1的結點數 + 度為2的結點數 + 度為3的結點數）
除了根結點外，其餘結點都有乙個分支進入，所以有下式成立：
n = e + 1(總結點數 =總分支數+1)
又因為這些分支都是由度為1或度為2的結點射出的，所以有下式成立：
e = 2n2 + n1
綜合上面三式：n0 + n1 + n2 = 2n2 + n1 +1
即 n0 = n2 + 1
選擇題假定一棵二叉樹中，度為２的結點數為15，度為１的結點數為30，則葉子結點數為（ b ）。
a．15b．16c．17d．47
定義1：滿二叉樹(full binary tree)
一棵深度為k且有2k -1個結點的二叉樹稱為滿二叉樹。
下面兩棵樹是否是滿二叉樹？
深度是3，但結點數為6，不等於23-1，所以不是滿二叉樹
深度是4，結點數是15=24-1，所以是滿二叉樹。
可以對滿二叉樹的結點進行連續編號，約定編號從根結點起，自上而下，自左至右。上述滿二叉樹結點的編號如下圖所示：
由滿二叉樹引出完全二叉樹的定義。
定義2：完全二叉樹：(complete binary tree)
深度為k，有n個結點的二叉樹，當且僅當其每乙個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱之為完全二叉樹。
判斷一棵二叉樹是不是完全二叉樹：
1）對二叉樹從上到下、自左至右進行編號。
2）對比二叉樹結點與同編號滿二叉樹結點位置是否一一對應；若一一對應，則是完全二叉樹；如不一一對應，則不是完全二叉樹。
習題：判斷下列二叉樹是否是完全二叉樹（對二叉樹已經編好號了）
二叉樹a
每乙個結點都與同編號的滿二叉樹結點一一對應，故是完全二叉樹。
二叉樹b
從結點6開始與同編號的滿二叉樹結點不對應，故不是完全二叉樹。
二叉樹c
也是從結點6開始與同編號的滿二叉樹結點不對應，故不是完全二叉樹。
完全二叉樹的另一種定義：若設二叉樹的深度為h，則共有h層。除第h層外，其它各層(0h-1)的結點數都必須達到最大個數，第h層可以從右向左連續缺若干結點。
（言外之意，第h層也可以為滿。）
判斷二叉樹是否是完全二叉樹，直接根據定義判斷就是。
1、2、3層結點數都達到了最大個數，第4層滿足從右向左連續缺３個結點。故是完全二叉樹。
第3層結點數都沒達到最大個數，故不是完全二叉樹。
第１、２層結點數都達到了最大數，但第三層不滿足從右往左缺結點。故不是完全二叉樹。
完全二叉樹的特點是：
１）只允許最後一層有空缺結點且空缺在右邊，即葉子結點只能在層次最大的兩層上出現；
2）對任一結點，如果其右子樹的深度為j，則其左子樹的深度必為j或j+1。
１）顯然成立。３結點右子樹的深度是１，左子樹的深度是２。２結點右子樹的深度是２，左子樹的深度是１。
【性質4】 具有n個結點的完全二叉樹的深度為 log2n+1。其中，log2n 的結果是不大於log2n的最大整數
證明：設完全二叉樹深度為k，根據二叉樹定義，完全二叉樹的k-1層上的結點數必須達到最大值，根據性質1，各層結點數最大值如下圖所示：
k-1層的結點總數為2k-1-1，第k層最少有1個結點，最多有2k-1個結點，所以結點數n滿足：
2k-1 n <= 2k-1即2k-1 n < 2k
兩邊取以2為底的對數：
k-1≤log2n ＜k
log2n＜k≤log2n +1 ；
因為k是整數，所以k=
選擇題一棵完全二叉樹有18個結點，則完全二叉樹的深度為c．
a．3b．4c．5d．6
一棵具有 n個結點的完全二叉樹的樹高度（深度）是（a）【南京理工大學 1996一、8 （2分）】
a．log2n+1 b．log2n+1 c．log2n d．log2n-1
一棵完全二叉樹上有1001個結點，其中葉子結點的個數是（ b ）【西安交通大學 1996 三、2 (3分)】
a． 250 b． 501 c．254 d．505
解：在完全二叉樹中，度為1的結點數n1或為0或為1。
由性質3可知
又因為n = n0 + n1 + n2
所以n = 2n0 + n1 -1
將n=1001代入得：2n0 + n1 =1002
又因為n0必須為整數，所以n1 的值必為0。
所以n0 =501
【性質5】如果將一棵有n個結點的完全二叉樹的結點按層序(自頂向下，同一層自左向右）連續編號1, 2, …, n，對結點i (1 i n) 有以下關係：
若i == 1, 則 i 是二叉樹的根，無雙親
若i > 1, 則 i 的雙親為i /2
若2*i ≤ n, 則 i 的左孩子為2*i，否則無左孩子
若2*i+1 ≤ n, 則 i 的右孩子為2*i+1，否則無右孩子
證明不做討論，背過，到時候直接用。
可以這樣記：對於結點i，雙親為i /2，i 的左孩子為2*i，i 的右孩子為2*i+1。
在上圖所示二叉樹中，4的父親是2，左孩子是8，右孩子是9。
6.2.3二叉樹的儲存結構
1、完全二叉樹的順序儲存：c語言中認為：將完全二叉樹中的結點按照從上至下、自左往右的順序儲存到一維陣列中。
31儲存到下標為0的陣列分量中，23儲存到下標為1的陣列分量中…依次類推。
普通二叉樹的順序儲存：也是將普通二叉樹中的結點按照從上至下、自左往右的順序儲存到一維陣列中。 （中間的空缺結點也留出相應的位置）
練習：畫出下圖所示二叉樹的順序儲存結構
1） 把空缺結點補齊
按照從上到下、從左至右的順序儲存到一維陣列中，給空缺結點留出相應的位置。
圖示二叉樹儘管只有3個結點，也要儲存到乙個長度為7的陣列中，浪費儲存空間。
第六章第六章財務計畫
6.1 資金 投資比例餅圖 希吉雅食品責任 成立初期，準備籌集資金100萬元。發起人自投60萬元，申請大學生創業貸款30萬元,10萬元尋求投資，企業固定資產作投資160萬元，向銀行貸款100萬元。共計註冊資本360萬元。投資比例如圖所示 圖8 1 投資比例 創業自籌資金由創業者個人以其個人名義籌集的...
第六章樹和二叉樹
一 選擇題 1 已知一算術表示式的中綴形式為 a b c d e，字尾形式為abc de 其字首形式為 a a b c de b.a b cd e c abc ded.a bc de 北京航空航天大學 1999 一 3 2分 2 算術表示式a b c d e 轉為字尾表示式後為 中山大學 1999 ...
第六章樹和二叉樹
樹是一類重要的非線性資料結構，是以分支關係定義的層次結構 6.1樹的定義 定義定義 樹 tree 是n n 0 個結點的有限集t，其中 有且僅有乙個特定的結點，稱為樹的根 root 當n 1時，其餘結點可分為m m 0 個互不相交的有限集t1,t2,tm，其中每乙個集合本身又是一棵樹，稱為根的子樹 ...