第06章_樹與二叉樹A

1、目 錄1 教教 學(xué)學(xué) 內(nèi)內(nèi) 容容 1 1、樹的基本概念、樹的基本概念2 2、二叉樹的定義、性質(zhì)及運算；、二叉樹的定義、性質(zhì)及運算； 3 3、二叉樹的存儲結(jié)構(gòu)、二叉樹的存儲結(jié)構(gòu) 4 4、遍歷二叉樹、遍歷二叉樹5 5、線索二叉樹、線索二叉樹6 6、樹、森林、森林與二叉樹的轉(zhuǎn)換、樹、森林、森林與二叉樹的轉(zhuǎn)換7 7、哈夫曼樹、哈夫曼編碼、哈夫曼樹、哈夫曼編碼 2樹型結(jié)構(gòu)（非線性結(jié)構(gòu)）樹型結(jié)構(gòu)（非線性結(jié)構(gòu)） 結(jié)點之間有分支結(jié)點之間有分支 具有層次關(guān)系具有層次關(guān)系 生活中的哪些實例是樹型結(jié)構(gòu)呢？例例 自然界自然界: :樹樹 人類社會人類社會 家譜家譜 院系組院系組織機構(gòu)織機構(gòu) 36.1 樹的基本概念樹的基

2、本概念 樹的定義樹的定義 樹是樹是 n (n 0) 個結(jié)點的有限集。若個結(jié)點的有限集。若n = 0，稱，稱為空樹；若為空樹；若 n 0，則它滿足如下兩個條件：，則它滿足如下兩個條件：有且僅有一個稱之為根有且僅有一個稱之為根(Root)的結(jié)點。的結(jié)點。當(dāng)當(dāng)n 1，除根以外的其它結(jié)點分為，除根以外的其它結(jié)點分為 m (m 0) 個互不相交的有限集個互不相交的有限集 T1, T2 , Tm，其中每，其中每個集合又是一棵符合本定義的樹，并且稱為個集合又是一棵符合本定義的樹，并且稱為根的子樹根的子樹。4ACGBDEFKLHMIJ例如例如A只有根結(jié)點的樹只有根結(jié)點的樹有有13個結(jié)點的樹個結(jié)點的樹A是根；其

3、余數(shù)據(jù)元素分成三個互不相交的子集，是根；其余數(shù)據(jù)元素分成三個互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根都是根A的子樹，且本身也是一棵樹。的子樹，且本身也是一棵樹。根結(jié)點根結(jié)點T15T2T3R=,ACGBDEFKLHMIJ6線性結(jié)構(gòu)線性結(jié)構(gòu)樹結(jié)構(gòu)樹結(jié)構(gòu)存在唯一的沒有前驅(qū)的存在唯一的沒有前驅(qū)的“首元素首元素”存在唯一的沒有前驅(qū)的存在唯一的沒有前驅(qū)的“根結(jié)點根結(jié)點”存在唯一的沒有后繼的存在唯一的沒有后繼的“尾元素尾元素”存在多個沒有后繼的存在多個沒有后繼的“葉子葉子”其余元素均存在唯一的其余元素均存在唯一的“前驅(qū)元素前驅(qū)元素”和唯一的

4、和唯一的“后繼元素后繼元素”其余結(jié)點均存在唯一的其余結(jié)點均存在唯一的“前驅(qū)（雙親）結(jié)點前驅(qū)（雙親）結(jié)點”和和多個多個“后繼（孩子）結(jié)點后繼（孩子）結(jié)點”樹結(jié)構(gòu)和線性結(jié)構(gòu)作如下對照：樹結(jié)構(gòu)和線性結(jié)構(gòu)作如下對照：7樹的基本術(shù)語樹的基本術(shù)語1層2層4層3層height= 4ACGBDEFKLHMIJ89即上層的那個結(jié)點即上層的那個結(jié)點(直接前驅(qū)直接前驅(qū))即下層結(jié)點的子樹的根即下層結(jié)點的子樹的根(直接后繼直接后繼)同一雙親下的同層結(jié)點（孩子之間互稱兄弟）同一雙親下的同層結(jié)點（孩子之間互稱兄弟）即雙親位于同一層的結(jié)點（但并非同一雙親）即雙親位于同一層的結(jié)點（但并非同一雙親）即從根到該結(jié)點所經(jīng)分支的所有結(jié)

5、點即從根到該結(jié)點所經(jīng)分支的所有結(jié)點即該結(jié)點下層子樹中的任一結(jié)點即該結(jié)點下層子樹中的任一結(jié)點ABCGEIDHFJMLK 根根 葉子葉子 森林森林有序樹有序樹無序樹無序樹即根結(jié)點即根結(jié)點(沒有前驅(qū)沒有前驅(qū))即終端結(jié)點即終端結(jié)點(沒有后繼沒有后繼)指指m棵不相交的樹的集棵不相交的樹的集合合(例如刪除例如刪除A后的子樹個數(shù)后的子樹個數(shù))雙親雙親孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孫子孫結(jié)點各子樹從左至右有序，不能互換（左為第一）結(jié)點各子樹從左至右有序，不能互換（左為第一）結(jié)點各子樹可互換位置。結(jié)點各子樹可互換位置。即樹的數(shù)據(jù)元素即樹的數(shù)據(jù)元素結(jié)點掛接的子樹數(shù)結(jié)點掛接的子樹數(shù)結(jié)點結(jié)點結(jié)點的度結(jié)點的度結(jié)

6、點的層次結(jié)點的層次終端結(jié)點終端結(jié)點分支結(jié)點分支結(jié)點樹的度樹的度樹的深度樹的深度(或高度或高度)ABCGEIDHFJMLK從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）即度為即度為0的結(jié)點，即葉子的結(jié)點，即葉子即度不為即度不為0的結(jié)點（也稱為內(nèi)部結(jié)點）的結(jié)點（也稱為內(nèi)部結(jié)點）所有結(jié)點度中的最大值（所有結(jié)點度中的最大值（Max各結(jié)點的度各結(jié)點的度）指所有結(jié)點中最大的層數(shù)（指所有結(jié)點中最大的層數(shù)（Max各結(jié)點的層次各結(jié)點的層次）問：問：右上圖中的結(jié)點數(shù)右上圖中的結(jié)點數(shù) ；樹的度；樹的度 ；樹的深度；樹的深度13133 34 4（有幾個直接后繼就是幾度，亦稱“次數(shù)”）10AB

7、CDEFGHIJKLM結(jié)點A的度：3結(jié)點B的度：2結(jié)點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點A的孩子：B，C，D結(jié)點B的孩子：E，F(xiàn)結(jié)點I的雙親：D結(jié)點L的雙親：E結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟樹的度：3結(jié)點A的層次：1結(jié)點M的層次：4樹的深度：4結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先1112性質(zhì)1：樹中的節(jié)點數(shù)n等于所有節(jié)點的度數(shù)加1（在一顆樹中，度之和=分支數(shù)，而分支數(shù)=n-1）性質(zhì)2：度為m 的樹中第i層上至多有mi-1個節(jié)點(i 1)性質(zhì)3：高度為h的度為m的樹至多有 個節(jié)點。性質(zhì)4：具有n個節(jié)點的度為m的樹的最小高度為 。13題目：題目：一顆度為4的樹中，若有20個

8、度為4的節(jié)點，10個度為3的節(jié)點，1個度為2的節(jié)點，10個度為1的節(jié)點，則該樹的葉子節(jié)點為 （ ）A. 41B. 81C. 113D.122解答：解答：樹中只能有度為0,1,2,3,4的節(jié)點。所有節(jié)點和為n=n0+n1+n2+n3+n4。而度之和=n-1，并且度之和=1n1 + 2 n2+3 n3+4 n4 = 1 10 + 2 1 + 3 10 + 4 20 = 122。則 n=122+1 = 123 n0 = n-n1-n2-n3-n4=122-41 = 81。本題答案為14對于度為m的樹，在n,n0,n1,n2,nm中只有兩個參數(shù)未知時，一般可以求出這兩個值。求解過程如下：n = n0

9、+ n1 + n2 + + nm度之和=n-1度之和=n1+2n2+mnm所以有 n = n1+2n2+mnm + 1 = n0 + n1 + n2 + + nm 例如：若一顆有n個節(jié)點的樹，其中所有分支節(jié)點的度均為k，求該樹中葉子節(jié)點的個數(shù)。顯然，m=k, n2=n3=nm-1 = 0, 則 n=n0+nk, 度之和=n-1=knk, nk=(n-1)/k, 所以n0=n-nk = n (n-1)/k.有序樹有序樹子樹之間存在確定的次序關(guān)系子樹之間存在確定的次序關(guān)系無序樹無序樹子樹之間不存在確定的次序關(guān)系子樹之間不存在確定的次序關(guān)系家族樹就屬家族樹就屬于有序樹。于有序樹。15是是m(m0)棵

10、互不相交的樹的集合棵互不相交的樹的集合給森林中的各子樹加上一個父親結(jié)點給森林中的各子樹加上一個父親結(jié)點,森森林就變成了樹。林就變成了樹。 T3 T2 T1 ABEFKLDHMIJCGCG16 二叉樹二叉樹或為或為空樹空樹，或是由一個，或是由一個根結(jié)點根結(jié)點加上加上兩棵分別稱為兩棵分別稱為左子樹左子樹和和右子樹右子樹的、的、互不交叉互不交叉的的二叉樹組成。二叉樹組成。 6.2 二叉樹二叉樹BDEGHCILFA根結(jié)點根結(jié)點右子樹右子樹左子樹左子樹17為何要重點研究每結(jié)點最多只有兩個為何要重點研究每結(jié)點最多只有兩個 “叉叉” 的樹？的樹？ 二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最

11、強； 可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。不失一般性。 (a)空二叉樹空二叉樹 (b) 根和空的根和空的 左右子樹左右子樹 (c) 根和左子樹根和左子樹 (d) 根和右子樹根和右子樹 (e) 根和左右子樹根和左右子樹 注：雖然二叉樹與樹概念不同，注：雖然二叉樹與樹概念不同， 但有關(guān)樹的基本術(shù)語對二叉樹都適用。但有關(guān)樹的基本術(shù)語對二叉樹都適用。 二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài) 18由n個節(jié)點構(gòu)成的二叉樹的形態(tài)總數(shù)為方法：加線抹線旋轉(zhuǎn) abeidfhgc樹轉(zhuǎn)二叉樹舉例：樹轉(zhuǎn)二叉樹舉例：abeidfhgc兄弟相連長兄為父孩子靠左1

12、9討論：討論：二叉樹怎樣還原為樹？二叉樹怎樣還原為樹？abeidfhgc要點：逆操作，把所有右孩子變?yōu)樾值埽?abdefhgic20 性質(zhì)性質(zhì)1 在二叉樹的第在二叉樹的第 i 層上至多有層上至多有 2i 1個結(jié)點。個結(jié)點。(i 1)證明：當(dāng)證明：當(dāng)i=1時，只有根結(jié)點，時，只有根結(jié)點，2i-1=20=1。假設(shè)對所有假設(shè)對所有j，ij 1，命題成立，即第，命題成立，即第j層上至多層上至多有有2j-1 個結(jié)點。個結(jié)點。由歸納假設(shè)第由歸納假設(shè)第i-1 層上至多有層上至多有 2i2個結(jié)點。個結(jié)點。二叉樹的每個結(jié)點的度至多為二叉樹的每個結(jié)點的度至多為2，故在第，故在第i層上的層上的最大結(jié)點數(shù)為第最大結(jié)點

13、數(shù)為第i-1層上的最大結(jié)點數(shù)的層上的最大結(jié)點數(shù)的2倍，即倍，即2*2i2= 2i-1。二叉樹的重要特性二叉樹的重要特性21 性質(zhì)性質(zhì)2 深度為深度為 k 的二叉樹至多有的二叉樹至多有 2k-1個結(jié)點，個結(jié)點，其中其中k 1。 證明：由性質(zhì)證明：由性質(zhì)1可見，深度為可見，深度為k的二叉樹的二叉樹的最大結(jié)點數(shù)為的最大結(jié)點數(shù)為20 + 21 + + 2k-1 = 2k - -1kii11222 性質(zhì)性質(zhì)3 對任何一棵二叉樹對任何一棵二叉樹T, 如果其葉子結(jié)點數(shù)為如果其葉子結(jié)點數(shù)為 n0, 度為度為2的的結(jié)點數(shù)為結(jié)點數(shù)為 n2,則則n0n21。證明證明： n = nn = n0 0 + n + n1

14、1 + n + n2 2 e = n e = n 1 = 2n 1 = 2n2 2 + n + n1 1 因此因此，2 2n n2 2 + n + n1 1 = n = n0 0 + n + n1 1 + n + n2 2 - 1 - 1 n n0 0 = n = n2 2 + 1 + 1 23設(shè)e為樹的分支總數(shù)，則e = n-1。這些分支由度為1或2的節(jié)點射出，所以：滿二叉樹滿二叉樹 (Full Binary Tree) 定義定義1 1 : : 一棵深度為一棵深度為k且有且有2 k-1個結(jié)點的二叉?zhèn)€結(jié)點的二叉樹稱為滿二叉樹。樹稱為滿二叉樹。兩種特殊形態(tài)的二叉樹兩種特殊形態(tài)的二叉樹754389

15、101113 14 1512126特點特點: :每一每一層上的結(jié)點層上的結(jié)點數(shù)都達(dá)到最數(shù)都達(dá)到最大大, ,葉子全葉子全部在最底層部在最底層24非完全二叉樹非完全二叉樹完全二叉樹完全二叉樹 (Complete Binary Tree) 若設(shè)二叉樹的深度為若設(shè)二叉樹的深度為h，除第，除第 h 層外，層外，其它各層其它各層 (0 h- -1) 的結(jié)點數(shù)都達(dá)到最大值，的結(jié)點數(shù)都達(dá)到最大值，第第 h 層層從右向左從右向左連續(xù)缺若干結(jié)點。連續(xù)缺若干結(jié)點。完全二叉樹完全二叉樹621543BACDEGF25 性質(zhì)性質(zhì)4 具有具有 n (n 0) 個結(jié)點的完全二叉樹的個結(jié)點的完全二叉樹的深度為深度為 log2(

16、n) 1 。證明：設(shè)完全二叉樹的深度為證明：設(shè)完全二叉樹的深度為 h h，則根據(jù)性質(zhì)，則根據(jù)性質(zhì)2 2和完全二叉樹的定義有和完全二叉樹的定義有2 2h-1h-1-1-1 n n 2 2h h - 1,- 1,即即2 2h-1h-1 n 2n 2h h，取對數(shù)，取對數(shù) h h1 1 log log2 2n hn n，則該結(jié)點無左孩子，否則，則該結(jié)點無左孩子，否則， 編號為編號為2i的結(jié)點為其的結(jié)點為其左孩子左孩子結(jié)點。結(jié)點。(3)若若2i+1n，則該結(jié)點無右孩子結(jié)點，則該結(jié)點無右孩子結(jié)點， 否則，編號為否則，編號為2i+1的結(jié)點為其的結(jié)點為其右孩子右孩子 結(jié)點。結(jié)點。2829節(jié)點節(jié)點i和和i+1

17、在同一層上在同一層上i+12i+22i+3i2i+12ii2i2i+1i+12i+3 i/2 2i+2節(jié)點節(jié)點i和和i+1不不在同一層上在同一層上二、二叉樹的鏈?zhǔn)酱鎯Ρ硎径?、二叉樹的鏈?zhǔn)酱鎯Ρ硎疽?、二叉樹的順序存儲表示一、二叉樹的順序存儲表?.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)30順序存儲表示順序存儲表示用用一組地址連續(xù)的存儲單元一組地址連續(xù)的存儲單元存儲二叉樹中的數(shù)存儲二叉樹中的數(shù)據(jù)元素。將據(jù)元素。將完全二叉樹完全二叉樹上編號為上編號為i i的結(jié)點元素的結(jié)點元素存儲在一維數(shù)組中下標(biāo)為存儲在一維數(shù)組中下標(biāo)為i-1i-1的分量中的分量中 BACEDFGHIJKLMNO31BACEDFGHIJ

18、12345671089練習(xí)練習(xí)32 A B D C E F 0 1 2 3 4 5 ABCDEF241635對于一般的非完全對于一般的非完全二叉樹二叉樹不能直接使不能直接使用二叉樹的順序存用二叉樹的順序存儲結(jié)構(gòu)。儲結(jié)構(gòu)。33可以首先在非完全二叉樹中增添一些并不存可以首先在非完全二叉樹中增添一些并不存在的空結(jié)點使之變成完全二叉樹的形態(tài)，然在的空結(jié)點使之變成完全二叉樹的形態(tài)，然后再用順序存儲結(jié)構(gòu)存儲。后再用順序存儲結(jié)構(gòu)存儲。 BACDEGFBACDEGF(a)一般二叉樹一般二叉樹 (b)完全二叉樹形態(tài)完全二叉樹形態(tài)34 單支樹單支樹35鏈表存儲表示鏈表存儲表示36ADEBCF rootlchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)二