數(shù)據(jù)結(jié)構(gòu)與算法——樹

1、1 第六章 樹和二叉樹6.1 樹的有關(guān)概念樹的有關(guān)概念6.2 二叉樹二叉樹6.3 二叉樹的遍歷二叉樹的遍歷6.4 遍歷的應(yīng)用遍歷的應(yīng)用6.5 線索二叉樹線索二叉樹6.6 樹和森林樹和森林6.7 Huffman樹及其應(yīng)用樹及其應(yīng)用2 第六章 樹和二叉樹樹樹和和二二叉叉樹樹樹的樹的ADTADT邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)樹樹 樹的應(yīng)用樹的應(yīng)用HuffmanHuffman樹樹判定過程判定過程二叉樹二叉樹邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)基本性質(zhì)基本性質(zhì)遍歷二叉樹遍歷二叉樹線索二叉樹線索二叉樹樹和森林樹和森林【本章學(xué)習(xí)要點(diǎn)本章學(xué)習(xí)要點(diǎn)】樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)樹的遍歷樹的遍歷3 第六章 樹和二叉樹6

2、.1 樹的有關(guān)概念樹的有關(guān)概念6.2 二叉樹二叉樹6.3 二叉樹的遍歷二叉樹的遍歷6.4 遍歷的應(yīng)用遍歷的應(yīng)用6.5 線索二叉樹線索二叉樹6.6 樹和森林樹和森林6.7 Huffman樹及其應(yīng)用樹及其應(yīng)用4 第六章 樹和二叉樹本章學(xué)習(xí)重點(diǎn)和難點(diǎn)重點(diǎn)重點(diǎn)：(1)二叉樹的定義、存儲(chǔ)結(jié)構(gòu)、遍歷及應(yīng)用；二叉樹的定義、存儲(chǔ)結(jié)構(gòu)、遍歷及應(yīng)用； (2)線索二叉樹的定義、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的操作；線索二叉樹的定義、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的操作； (3)樹和森林與二叉樹之間的相互轉(zhuǎn)化方法；樹和森林與二叉樹之間的相互轉(zhuǎn)化方法； (4)哈夫曼樹的建立方法和哈夫曼編碼。哈夫曼樹的建立方法和哈夫曼編碼。難點(diǎn)難點(diǎn)： （1）二叉樹的構(gòu)

3、造）二叉樹的構(gòu)造 、應(yīng)用；、應(yīng)用； （2）線索二叉樹的遍歷和相應(yīng)的操作。）線索二叉樹的遍歷和相應(yīng)的操作。 5 第六章 樹和二叉樹樹形結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。樹是樹形結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。樹是n個(gè)結(jié)點(diǎn)的有限集合，個(gè)結(jié)點(diǎn)的有限集合，在任一棵非空樹中：在任一棵非空樹中：（1）有且僅有一個(gè)稱為根的結(jié)點(diǎn)。）有且僅有一個(gè)稱為根的結(jié)點(diǎn)。（2）其余結(jié)點(diǎn)可分為）其余結(jié)點(diǎn)可分為m個(gè)互不相交的集合，而且這些集合中的每個(gè)互不相交的集合，而且這些集合中的每一集合都本身又是一棵樹，稱為根的子樹。一集合都本身又是一棵樹，稱為根的子樹。說明：說明：樹是遞歸結(jié)構(gòu)，在樹的定義中又用到了樹的概念樹是遞歸結(jié)構(gòu)，在樹的定義中

4、又用到了樹的概念 J JI IA AC CB BD DH HG GF FE EK KL LM Mp 樹的概念樹的概念 6.1 樹的有關(guān)概念樹的有關(guān)概念6 第六章 樹和二叉樹p 樹的概念樹的概念 6.1 樹的有關(guān)概念樹的有關(guān)概念數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D：D是具有是具有相同特性相同特性的數(shù)據(jù)元素的集合。的數(shù)據(jù)元素的集合。 若若D D為空集，則稱為空樹為空集，則稱為空樹 。 否則否則: : (1) (1) 在在D D中存在中存在唯一唯一的稱為根的數(shù)據(jù)元素的稱為根的數(shù)據(jù)元素rootroot； (2) (2) 當(dāng)當(dāng)n1n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m (m0)m (m0)個(gè)個(gè)互互 不相交不相交的有

5、限集的有限集T T1 1, T, T2 2, , T, , Tm m，其中每一，其中每一 棵子集本身又是一棵符合本定義的樹，棵子集本身又是一棵符合本定義的樹， 稱為根稱為根rootroot的子樹。的子樹。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R：ADT TreeADT Tree7 第六章 樹和二叉樹p 樹的概念樹的概念 6.1 樹的有關(guān)概念樹的有關(guān)概念基本操作基本操作 P P：ADT TreeADT Tree查查 找找 類類 插插 入入 類類刪刪 除除 類類 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D： 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R：8 第六章 樹和二叉樹p 樹的基本操作樹的基本操作P 6.1 樹的有關(guān)概念樹的有關(guān)概念 Root(T) Ro

6、ot(T) / / 求樹的根結(jié)點(diǎn)求樹的根結(jié)點(diǎn) 查找類：查找類：Value(T, cur_e) Value(T, cur_e) / / 求當(dāng)前結(jié)點(diǎn)的元素值求當(dāng)前結(jié)點(diǎn)的元素值 Parent(T, cur_e) Parent(T, cur_e) / / 求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T, cur_e) LeftChild(T, cur_e) / / 求當(dāng)前結(jié)點(diǎn)的最左孩子求當(dāng)前結(jié)點(diǎn)的最左孩子 RightSibling(T, cur_e) RightSibling(T, cur_e) / / 求當(dāng)前結(jié)點(diǎn)的右兄弟求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T) TreeEmpty(

7、T) / / 判定樹是否為空樹判定樹是否為空樹 TreeDepth(T) TreeDepth(T) / / 求樹的深度求樹的深度TraverseTree( T, Visit() ) TraverseTree( T, Visit() ) / / 遍歷遍歷9 第六章 樹和二叉樹p 樹的基本操作樹的基本操作P 6.1 樹的有關(guān)概念樹的有關(guān)概念插入類：插入類：InitTree(&T) InitTree(&T) / / 初始化置空樹初始化置空樹 CreateTree(&T, definition) CreateTree(&T, definition) / / 按定義構(gòu)造樹按定義構(gòu)造樹Assign(T,

8、cur_e, value) Assign(T, cur_e, value) / / 給當(dāng)前結(jié)點(diǎn)賦值給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T, &p, i, c) InsertChild(&T, &p, i, c) / / 將以將以c c為根的樹插入為結(jié)點(diǎn)為根的樹插入為結(jié)點(diǎn)p p的第的第i i棵子樹棵子樹10 第六章 樹和二叉樹p 樹的基本操作樹的基本操作P 6.1 樹的有關(guān)概念樹的有關(guān)概念刪除類：刪除類： ClearTree(&T) ClearTree(&T) / / 將樹清空將樹清空 DestroyTree(&T) DestroyTree(&T) / / 銷毀樹的結(jié)構(gòu)銷毀樹的結(jié)構(gòu)Delet

9、eChild(&T, &p, i) DeleteChild(&T, &p, i) / / 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)p p的第的第i i棵子樹棵子樹11 第六章 樹和二叉樹例如：集合例如：集合 T=A, B, C, D, E, F, G, H, I, JT=A, B, C, D, E, F, G, H, I, J，K K，L L，MMA A是根，其余結(jié)點(diǎn)可以劃分為是根，其余結(jié)點(diǎn)可以劃分為3 3個(gè)個(gè)互不相交的集合互不相交的集合： T1=B, E, FT1=B, E, F，K K，L , T2=C, G , T3=D, H, I, JL , T2=C, G , T3=D, H, I, J，MM這些集合中的每

10、一集合都本身又是一棵樹，它們是這些集合中的每一集合都本身又是一棵樹，它們是A的子樹。的子樹。J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 樹的有關(guān)概念樹的有關(guān)概念p 樹的概念樹的概念 12 第六章 樹和二叉樹 從邏輯結(jié)構(gòu)看：從邏輯結(jié)構(gòu)看：樹是一種分枝結(jié)構(gòu)，樹中只有根結(jié)點(diǎn)沒有前趨；其余結(jié)點(diǎn)有零樹是一種分枝結(jié)構(gòu)，樹中只有根結(jié)點(diǎn)沒有前趨；其余結(jié)點(diǎn)有零個(gè)或多個(gè)后繼；個(gè)或多個(gè)后繼；除根外，其余結(jié)點(diǎn)都除根外，其余結(jié)點(diǎn)都有且僅一個(gè)有且僅一個(gè)前趨；都存在前趨；都存在唯一唯一一條從根到一條從根到該結(jié)點(diǎn)的路徑該結(jié)點(diǎn)的路徑。J JI IA AC CB BD DH HG GF

11、FE EK KL LM M6.1 樹的有關(guān)概念樹的有關(guān)概念p 樹的概念樹的概念 13 第六章 樹和二叉樹6.1 樹的有關(guān)概念樹的有關(guān)概念p 樹的概念樹的概念 線性結(jié)構(gòu)線性結(jié)構(gòu)非線形結(jié)構(gòu)非線形結(jié)構(gòu)樹樹第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn)( (無前驅(qū)無前驅(qū)) )最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素 ( (無后繼無后繼) )多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) ( (無后繼無后繼) ) 其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)后繼一個(gè)前驅(qū)、一個(gè)后繼) ) 其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、多個(gè)后繼一個(gè)前驅(qū)、多個(gè)后繼) )14 第六章 樹和二叉樹 單位行政機(jī)構(gòu)的組織關(guān)系單位行

12、政機(jī)構(gòu)的組織關(guān)系1）樹可表示具有分枝結(jié)構(gòu)關(guān)系的對(duì)象）樹可表示具有分枝結(jié)構(gòu)關(guān)系的對(duì)象J JI IA AC CB BD DH HG GF FE EK KL LM M例例6.1 樹的有關(guān)概念樹的有關(guān)概念p 樹的應(yīng)用樹的應(yīng)用 15 第六章 樹和二叉樹 2）樹是常用的數(shù)據(jù)組織形式）樹是常用的數(shù)據(jù)組織形式 有些應(yīng)用中數(shù)據(jù)元素之間并不存在分支結(jié)構(gòu)關(guān)系，但是為了便有些應(yīng)用中數(shù)據(jù)元素之間并不存在分支結(jié)構(gòu)關(guān)系，但是為了便于管理和使用數(shù)據(jù)，將它們用樹的形式來組織。于管理和使用數(shù)據(jù)，將它們用樹的形式來組織。C C文件夾文件夾1 1 文件夾文件夾n n 文件文件1 1 文件文件2 2文件夾文件夾11 11 文件夾文件夾

13、12 12 文件文件11 11 文件文件1212 計(jì)算機(jī)的文件系統(tǒng)計(jì)算機(jī)的文件系統(tǒng) 不論是不論是DOS文件系統(tǒng)還是文件系統(tǒng)還是window文件系統(tǒng)，所有的文件是用樹文件系統(tǒng)，所有的文件是用樹的形式來組織的。的形式來組織的。例例6.1 樹的有關(guān)概念樹的有關(guān)概念p 樹的應(yīng)用樹的應(yīng)用 16 第六章 樹和二叉樹（1 1）樹形表示法）樹形表示法ABEKLFCGDHMJI（2 2）凹入表示法）凹入表示法J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 樹的有關(guān)概念樹的有關(guān)概念p 樹的表示樹的表示 17 第六章 樹和二叉樹（3 3）嵌套集合表示法）嵌套集合表示法 （文氏圖

14、）（文氏圖）AEDHJIKLMFGCBJ JI IA AC CB BD DH HG GF FE EK KL LM M6.1 樹的有關(guān)概念樹的有關(guān)概念p 樹的表示樹的表示 18 第六章 樹和二叉樹（4 4）廣義表表示法）廣義表表示法(A(A）第一層）第一層( (A(A(B, C, DB, C, D) ) 第二層第二層(A(A(B B( (E,FE,F), ), C C( (G G), ), D D( (H,I,JH,I,J) ) 第三層第三層(A(A(B B( (E(E(K,LK,L),F),F), ), C C( (G G), ), D D( (H(H(M M),I,J),I,J) ) 第四層

15、第四層J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 樹的有關(guān)概念樹的有關(guān)概念p 樹的表示樹的表示 19 第六章 樹和二叉樹結(jié)點(diǎn)層結(jié)點(diǎn)層：根結(jié)點(diǎn)的層定義為：根結(jié)點(diǎn)的層定義為1，其它依此類推；，其它依此類推；樹的深度樹的深度：樹中最大的結(jié)點(diǎn)層；：樹中最大的結(jié)點(diǎn)層；結(jié)點(diǎn)的度結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹的個(gè)數(shù)；：結(jié)點(diǎn)子樹的個(gè)數(shù)；樹的度樹的度： 樹中最大的結(jié)點(diǎn)度；樹中最大的結(jié)點(diǎn)度；葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為：也叫終端結(jié)點(diǎn)，是度為 0 的結(jié)點(diǎn)；的結(jié)點(diǎn)；樹的度為樹的度為3樹的深度為樹的深度為4第第1層層第第3層層第第2層層第第4層層J JI IA AC CB BD

16、DH HG GF FE EK KL LM M6.1 樹的有關(guān)概念樹的有關(guān)概念p 樹的有關(guān)術(shù)語樹的有關(guān)術(shù)語 20 第六章 樹和二叉樹分枝結(jié)點(diǎn)：分枝結(jié)點(diǎn)：度不為度不為0的結(jié)點(diǎn)；的結(jié)點(diǎn)；有序樹：有序樹：子樹有序的樹，如：家族樹；子樹有序的樹，如：家族樹；無序樹：無序樹：不考慮子樹的順序；不考慮子樹的順序；森林：森林：互不相交的樹集合；互不相交的樹集合；6.1 樹的有關(guān)概念樹的有關(guān)概念p 樹的有關(guān)術(shù)語樹的有關(guān)術(shù)語 樹和森林的關(guān)系：樹和森林的關(guān)系：（1）一棵樹去掉根）一棵樹去掉根 ，其子樹構(gòu)成一個(gè)森林；，其子樹構(gòu)成一個(gè)森林；（2）一個(gè)森林增加一個(gè)根結(jié)點(diǎn)成為樹。）一個(gè)森林增加一個(gè)根結(jié)點(diǎn)成為樹。21 第六章

17、 樹和二叉樹6.1 樹的有關(guān)概念樹的有關(guān)概念6.2 二叉樹二叉樹6.3 二叉樹的遍歷二叉樹的遍歷6.4 遍歷的應(yīng)用遍歷的應(yīng)用6.5 線索二叉樹線索二叉樹6.6 樹和森林樹和森林6.7 Huffman樹及其應(yīng)用樹及其應(yīng)用22 第六章 樹和二叉樹 樹是一種分枝結(jié)構(gòu)的對(duì)象，在樹的概念中，對(duì)每一樹是一種分枝結(jié)構(gòu)的對(duì)象，在樹的概念中，對(duì)每一個(gè)結(jié)點(diǎn)孩子的個(gè)數(shù)沒有限制，因此樹的形態(tài)多種多樣，個(gè)結(jié)點(diǎn)孩子的個(gè)數(shù)沒有限制，因此樹的形態(tài)多種多樣，本節(jié)我們主要討論另一種樹型結(jié)構(gòu)本節(jié)我們主要討論另一種樹型結(jié)構(gòu)二叉樹。二叉樹。6.2 二叉樹二叉樹 A A F F G G E E D D C C B B23 第六章 樹和二

18、叉樹 6.2.1 6.2.1 二叉樹的概念二叉樹的概念 6.2.2 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì) 6.2.3 6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)6.2 二叉樹二叉樹24 第六章 樹和二叉樹6.2.1 二叉樹的概念二叉樹的概念特點(diǎn)：特點(diǎn)：二叉樹中每個(gè)結(jié)點(diǎn)最多有兩棵子樹；即二叉樹二叉樹中每個(gè)結(jié)點(diǎn)最多有兩棵子樹；即二叉樹每個(gè)結(jié)每個(gè)結(jié)點(diǎn)度小于等于點(diǎn)度小于等于2 2; ;左、右子樹不能顛倒左、右子樹不能顛倒有序樹有序樹; ;二叉樹是二叉樹是遞歸結(jié)構(gòu)遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉，在二叉樹的定義中又用到了二叉樹的概念樹的概念; ; A A F F G G E E D D C C

19、B B概念：二叉樹概念：二叉樹或?yàn)榭諛洌蛴筛盎驗(yàn)榭諛?，或由根及兩顆不相交的兩顆不相交的左、右左、右子樹構(gòu)成，并且子樹構(gòu)成，并且左、右子樹本身也是二叉樹左、右子樹本身也是二叉樹。25 第六章 樹和二叉樹 A A F F G G E E D D C C B B(a) F F A A G G E E D D B B C C(b)二叉樹是有左右之分的6.2.1 二叉樹的概念二叉樹的概念26 第六章 樹和二叉樹p 二叉樹的基本形態(tài)二叉樹的基本形態(tài)(a)空樹(b)僅有根(c) 右子樹空(d) 左子樹空(e) 左、右子樹均在6.2.1 二叉樹的概念二叉樹的概念27 第六章 樹和二叉樹 6.2.1 6.2

20、.1 二叉樹的概念二叉樹的概念 6.2.2 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì) 6.2.3 6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)6.2 二叉樹二叉樹28 第六章 樹和二叉樹證明：最多結(jié)點(diǎn)數(shù)為各層結(jié)點(diǎn)個(gè)數(shù)相加，即證明：最多結(jié)點(diǎn)數(shù)為各層結(jié)點(diǎn)個(gè)數(shù)相加，即 1+2+4+21+2+4+2k-1k-1=2=2k k-1-1性質(zhì)性質(zhì)2 2 深度為深度為k k的二叉樹的二叉樹有有個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。性質(zhì)性質(zhì)1 1 在二叉樹的第在二叉樹的第i(i1)i(i1)層上層上有有個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 證明：用數(shù)學(xué)歸納法就可以證明。證明：用數(shù)學(xué)歸納法就可以證明。ABCDEFGIHJ k k層二叉樹層二叉樹6.2.2 二

21、叉樹的性質(zhì)二叉樹的性質(zhì)29 第六章 樹和二叉樹p 兩種特殊的二叉樹兩種特殊的二叉樹 A A G G F F E E D D C C B B(a)(a)K=3K=3的滿二叉樹的滿二叉樹滿二叉樹：滿二叉樹：如果深度為如果深度為k k的二叉樹，有的二叉樹，有2 2k k-1-1個(gè)結(jié)點(diǎn)則稱為滿二叉樹；個(gè)結(jié)點(diǎn)則稱為滿二叉樹；完全二叉樹：二叉樹中所含的二叉樹中所含的 n n 個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1 1至至n n的的 結(jié)點(diǎn)結(jié)點(diǎn)一一對(duì)應(yīng)一一對(duì)應(yīng)。 A A E E D D C C B B(b)(b)(b)(b)完全二叉樹 G G A A E E D D C C B B(c)(c)(c

22、) (c) 不是不是完全二叉樹完全二叉樹結(jié)論：滿二叉樹一定是完全二叉樹，反之不一定6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)30 第六章 樹和二叉樹證明：設(shè)所求完全二叉樹的深度為證明：設(shè)所求完全二叉樹的深度為k 由性質(zhì)由性質(zhì)2 2和完全二叉樹的定義知：和完全二叉樹的定義知： 2k-1 1-1 1n2k-1 1 性質(zhì)性質(zhì)3 3 具有具有n n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的完全二叉樹的深度完全二叉樹的深度為為 loglog2 2n n +1 +1 由此可以推出：由此可以推出：2k-1 1 n2k取對(duì)數(shù)得：取對(duì)數(shù)得： k-1 1log2nk由于由于k為整數(shù)，故有為整數(shù)，故有k-1 1= log2n 即：即： k= lo

23、g2n +1 1 性質(zhì)性質(zhì)2:2:深度為深度為k k的二叉樹最多有的二叉樹最多有2 2k k-1-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) A A E E D D C C B B E E D D D Dk層的最多結(jié)點(diǎn)數(shù)層的最多結(jié)點(diǎn)數(shù)k-1-1層的最多結(jié)點(diǎn)數(shù)層的最多結(jié)點(diǎn)數(shù)6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)31 第六章 樹和二叉樹性質(zhì)性質(zhì)4 4 對(duì)任意二叉樹對(duì)任意二叉樹T T，如果度數(shù)為，如果度數(shù)為0 0結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為n n0 0, ,度數(shù)為度數(shù)為1 1結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為n n1 1, ,度數(shù)為度數(shù)為2 2結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為n n2 2，則，則n n0 0=n=n2 2+1+1。 證明：二叉樹證明：二叉樹T T的的結(jié)點(diǎn)總數(shù)

24、結(jié)點(diǎn)總數(shù) n=nn=n0 0+n+n1 1+n+n2 2 （1 1） 注意：注意：n1 1生成生成n1 1*1個(gè)節(jié)點(diǎn)，個(gè)節(jié)點(diǎn)，n2 2生成生成n2 2*2個(gè)節(jié)點(diǎn)，個(gè)節(jié)點(diǎn)， 根結(jié)點(diǎn)不由任何結(jié)點(diǎn)產(chǎn)生根結(jié)點(diǎn)不由任何結(jié)點(diǎn)產(chǎn)生由于分支結(jié)點(diǎn)是由度為由于分支結(jié)點(diǎn)是由度為1 1和度為和度為2 2的結(jié)點(diǎn)生成的的結(jié)點(diǎn)生成的 即即分支結(jié)點(diǎn)總數(shù)分支結(jié)點(diǎn)總數(shù)b=b=n1+2*n2 （3 3）二叉樹的二叉樹的分支結(jié)點(diǎn)總數(shù)分支結(jié)點(diǎn)總數(shù) b=n-1 b=n-1 （2 2） 由由(1)(2)(3)(1)(2)(3)得得 求得：求得：n n0 0=n=n2 2+1+1ABCDEFGIHJ6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)32

25、第六章 樹和二叉樹性質(zhì)性質(zhì)5:5:若對(duì)含若對(duì)含 n n 個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行至右進(jìn)行 1 1 至至 n n 的編號(hào)，則對(duì)完全二叉樹中任意一個(gè)的編號(hào)，則對(duì)完全二叉樹中任意一個(gè)編號(hào)為編號(hào)為 i i 的結(jié)點(diǎn)的結(jié)點(diǎn): :(1) (1) 若若 i=1i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親，否則，則該結(jié)點(diǎn)是二叉樹的根，無雙親，否則， 編號(hào)為編號(hào)為 i/2i/2 的結(jié)點(diǎn)為其的結(jié)點(diǎn)為其雙親雙親結(jié)點(diǎn)；結(jié)點(diǎn)；(3) (3) 若若 2i+1n2i+1n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，否則，編號(hào)為，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，否則，編號(hào)為 2i+1 2i+1 的結(jié)點(diǎn)為其的結(jié)點(diǎn)為其右

26、孩子右孩子結(jié)點(diǎn)。結(jié)點(diǎn)。(2) (2) 若若 2in2in，則該結(jié)點(diǎn)無左孩子，否則，編號(hào)為，則該結(jié)點(diǎn)無左孩子，否則，編號(hào)為 2i2i的的 結(jié)點(diǎn)為其結(jié)點(diǎn)為其左孩子左孩子結(jié)點(diǎn)；結(jié)點(diǎn)； 2i+2 2i+2 i/2 2i+12i+1 2i2i i+1i+1 i i6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)33 第六章 樹和二叉樹編號(hào)編號(hào)i=4i=4雙親為雙親為 i/2i/2 =2 =2左子樹為左子樹為2i=82i=8右子樹為右子樹為2i+1=92i+1=9i=1 只有根結(jié)點(diǎn)只有根結(jié)點(diǎn)編號(hào)編號(hào)i=5i=5雙親為雙親為 i/2i/2 =2 =2左子樹為左子樹為2i=10 2i=10 右子樹為右子樹為2i+1=11

27、2i+1=11i=8,i=8,2in2in無左子樹無左子10 11 12 13 146.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì)通過性質(zhì)5把非線性結(jié)構(gòu)輕易轉(zhuǎn)化成了線性結(jié)構(gòu)。34 第六章 樹和二叉樹 6.2.1 二叉樹的概念二叉樹的概念 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì) 6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)6.2 二叉樹二叉樹35 第六章 樹和二叉樹p二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二叉樹的鏈?zhǔn)酱鎯?chǔ)表示p 二叉樹的順序存儲(chǔ)表示二叉樹的順序存儲(chǔ)表示6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)36 第六章 樹和二叉樹 (1)(1)完全（或滿）二叉樹完全（或滿）二叉樹ABCDEFGI

28、HJ采用采用一維數(shù)組一維數(shù)組，按，按層序順序?qū)有蝽樞蛞酪来未鎯?chǔ)二叉樹的每一個(gè)結(jié)點(diǎn)。次存儲(chǔ)二叉樹的每一個(gè)結(jié)點(diǎn)。如下圖所示：如下圖所示：p 二叉樹的順序存儲(chǔ)表示二叉樹的順序存儲(chǔ)表示利用性質(zhì)利用性質(zhì)5 5實(shí)現(xiàn)實(shí)現(xiàn)線性結(jié)構(gòu)線性結(jié)構(gòu)和和非線性結(jié)構(gòu)非線性結(jié)構(gòu)的靈活轉(zhuǎn)換。的靈活轉(zhuǎn)換。 2i+2 2i+2 i/2 2i+12i+1 2i2i i+1i+1 i iA B C D E F G1 2 3 4 5 6 7 8 9 10H IJ6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)37 第六章 樹和二叉樹(2)(2)一般二叉樹一般二叉樹A B C 0E 0G1 2 3 4 5 6 7 8 9 1000J通過通過虛

29、設(shè)虛設(shè)部分結(jié)點(diǎn)，使其變成相應(yīng)的部分結(jié)點(diǎn)，使其變成相應(yīng)的完全二叉樹完全二叉樹。ABCEGJABC0E0G00Jp 二叉樹的順序存儲(chǔ)表示二叉樹的順序存儲(chǔ)表示6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)38 第六章 樹和二叉樹(3)(3)特殊的二叉樹特殊的二叉樹說明：說明：順序存儲(chǔ)方式對(duì)于畸形二叉樹，浪費(fèi)較大空間順序存儲(chǔ)方式對(duì)于畸形二叉樹，浪費(fèi)較大空間p 二叉樹的順序存儲(chǔ)表示二叉樹的順序存儲(chǔ)表示6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)ABCJ39 第六章 樹和二叉樹二叉鏈表存儲(chǔ)：二叉鏈表存儲(chǔ)：二叉鏈表中每個(gè)結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域、左指針域、右指針域二叉鏈表中每個(gè)結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域、左指針域、

30、右指針域 typedef typedef Struct nodeStruct node DataType data; DataType data; Struct nodeStruct node * *lch,lch,* *rch;rch; BinTNode; BinTNode;lchrchdataC 語言的類型描述如下語言的類型描述如下: :p 二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二叉樹的鏈?zhǔn)酱鎯?chǔ)表示6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)40 第六章 樹和二叉樹二叉鏈表圖示二叉鏈表圖示 D D A A C C E E F F B B root A A F F E E D D C C B B二叉樹二叉樹n

31、 個(gè)結(jié)點(diǎn)的二叉樹中，有多少個(gè)空鏈接域？p 二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二叉樹的鏈?zhǔn)酱鎯?chǔ)表示6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)41 第六章 樹和二叉樹性質(zhì)性質(zhì)6 6：n n 個(gè)結(jié)點(diǎn)的二叉樹中，共有個(gè)結(jié)點(diǎn)的二叉樹中，共有 n+1n+1 個(gè)空指針域。個(gè)空指針域。證：證：n n個(gè)結(jié)點(diǎn)總的指針域數(shù)個(gè)結(jié)點(diǎn)總的指針域數(shù)2n 2n 除了根結(jié)點(diǎn)外，其余除了根結(jié)點(diǎn)外，其余n-1n-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)都是由指針域指出的結(jié)點(diǎn)；都是由指針域指出的結(jié)點(diǎn)； 所以，剩余的結(jié)點(diǎn)數(shù)即所以，剩余的結(jié)點(diǎn)數(shù)即空指針域個(gè)數(shù)空指針域個(gè)數(shù)為：為：2n-2n-（n-1n-1）=n+1 =n+1 二叉鏈表的缺點(diǎn)二叉鏈表的缺點(diǎn)是很難找到結(jié)點(diǎn)的雙親是

32、很難找到結(jié)點(diǎn)的雙親二叉鏈表圖示二叉鏈表圖示 D D A A C C E E F F B B rootp 二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二叉樹的鏈?zhǔn)酱鎯?chǔ)表示6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)42 第六章 樹和二叉樹三叉鏈表（三叉鏈表（帶雙親指針的二叉鏈表帶雙親指針的二叉鏈表）: :三叉鏈表中每個(gè)結(jié)點(diǎn)三叉鏈表中每個(gè)結(jié)點(diǎn)包含四個(gè)域：數(shù)據(jù)域、左指針域、右指針域、包含四個(gè)域：數(shù)據(jù)域、左指針域、右指針域、雙親指針域雙親指針域typedef typedef Struct nodeStruct node DataType data; DataType data; Struct nodeStruct node

33、* *lch,lch,* *rch,rch,* *parent;parent;lch data rch parent結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):C 語言的類型描述如下語言的類型描述如下: :p 二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二叉樹的鏈?zhǔn)酱鎯?chǔ)表示6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)43 第六章 樹和二叉樹 A A F F E E D D C C B BA AB BD DF FE EC Crootlch data rch parentp 二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二叉樹的鏈?zhǔn)酱鎯?chǔ)表示-三叉鏈表三叉鏈表6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)44 第六章 樹和二叉樹6.1 樹的有關(guān)概念樹的有關(guān)概念6.2 二叉樹二

34、叉樹6.3 二叉樹的遍歷二叉樹的遍歷6.4 遍歷的應(yīng)用遍歷的應(yīng)用6.5 線索二叉樹線索二叉樹6.6 樹和森林樹和森林6.7 Huffman樹及其應(yīng)用樹及其應(yīng)用45 第六章 樹和二叉樹 6.3.1 二叉樹的遍歷方法二叉樹的遍歷方法 6.3.2 二叉樹的遍歷算法二叉樹的遍歷算法 6.3 二叉樹的遍歷二叉樹的遍歷46 第六章 樹和二叉樹 遍歷遍歷：按某種搜索路徑：按某種搜索路徑訪問訪問二叉樹的每個(gè)結(jié)點(diǎn)，而二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次。且每個(gè)結(jié)點(diǎn)僅被訪問一次。訪問訪問：訪問是指對(duì)結(jié)點(diǎn)進(jìn)行各種操作的簡稱，包括：訪問是指對(duì)結(jié)點(diǎn)進(jìn)行各種操作的簡稱，包括輸出、查找、修改等等操作。輸出、查找、修改

35、等等操作。遍歷遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其它的操是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其它的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。 6.3 .1 二叉樹的遍歷方法二叉樹的遍歷方法47 第六章 樹和二叉樹 “ “遍歷遍歷”是任何類型均有的操作：是任何類型均有的操作：線性結(jié)構(gòu)的遍歷：只有一條搜索路徑線性結(jié)構(gòu)的遍歷：只有一條搜索路徑( (因?yàn)槊總€(gè)結(jié)點(diǎn)均只因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼有一個(gè)后繼) )；非線性結(jié)構(gòu)的遍歷：二叉樹是非線性結(jié)構(gòu)，則非線性結(jié)構(gòu)的遍歷：二叉樹是非線性結(jié)構(gòu)，則存在如何遍存在如何遍歷歷即按什么樣的即按什么樣的搜索路徑搜索路徑遍歷的問題。遍歷的問題。 如何訪問二叉樹的每個(gè)

36、結(jié)點(diǎn)，如何訪問二叉樹的每個(gè)結(jié)點(diǎn)， 而且每個(gè)結(jié)點(diǎn)僅被訪問一次？而且每個(gè)結(jié)點(diǎn)僅被訪問一次？6.3 .1 二叉樹的遍歷方法二叉樹的遍歷方法48 第六章 樹和二叉樹 對(duì)對(duì)“二叉樹二叉樹”而言，可以有三條搜索路徑：而言，可以有三條搜索路徑：先上后下先上后下的按層次遍歷；的按層次遍歷；先左先左（子樹）（子樹）后右后右（子樹）的遍歷；（子樹）的遍歷；先右先右（子樹）（子樹）后左后左（子樹）的遍歷（子樹）的遍歷。6.3 .1 二叉樹的遍歷方法二叉樹的遍歷方法49 第六章 樹和二叉樹 二叉樹由根、左子樹、右子樹三部分組成二叉樹由根、左子樹、右子樹三部分組成 二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹

37、二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹令：令：L L：遍歷左子樹遍歷左子樹 T T：訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) R R：遍歷右子樹遍歷右子樹 有六種遍歷方法：有六種遍歷方法： T T L L R R，L L T T R R，L L R R T T， T T R R L L，R R T T L L，R R L L T T 約定先左后右約定先左后右, ,有三種遍歷方法：有三種遍歷方法： T T L L R R、L L T T R R、L L R R T T ，分別稱分別稱為為 先序遍歷、中序遍歷、后序遍歷先序遍歷、中序遍歷、后序遍歷 A A F F G G E E D D C C B B

38、6.3 .1 二叉樹的遍歷方法二叉樹的遍歷方法50 第六章 樹和二叉樹若二叉樹非空若二叉樹非空（1 1）中序遍歷左子樹）中序遍歷左子樹（2 2）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)（3 3）中序遍歷右子樹）中序遍歷右子樹 中序遍歷序列：中序遍歷序列：中序遍歷右圖所示的二叉樹中序遍歷右圖所示的二叉樹 p中序遍歷中序遍歷（ L T RL T R ） A A F F G G E E D D C C B B,F例例D,G,B,A,E,C圖示圖示6.3 .1 二叉樹的遍歷方法二叉樹的遍歷方法51 第六章 樹和二叉樹 d d e e c c b b f f a a + + * * / / - - - - 中序遍歷下圖所

39、示的二叉樹中序遍歷下圖所示的二叉樹 中序中序 a,+,b,a,+,b,* *,c,-,d,c,-,d, ,- -,e,/,f,e,/,f練習(xí)練習(xí)6.3 .1 二叉樹的遍歷方法二叉樹的遍歷方法52 第六章 樹和二叉樹 若二叉樹非空若二叉樹非空 （1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2 2）先序遍歷左子樹；）先序遍歷左子樹； （3 3）先序遍歷右子樹；）先序遍歷右子樹； 先序遍歷序列：先序遍歷序列：A A, ,B B, ,D D,E,E,G G,C,F,C,F A A F F G G E E D D C C B B 先先序遍歷右圖所示的二叉樹序遍歷右圖所示的二叉樹 （1 1）訪問根結(jié)點(diǎn)）訪問根結(jié)

40、點(diǎn)A A （2 2）先序遍歷左子樹：即按先序遍歷左子樹：即按 T T L L R R 的順序遍歷的順序遍歷左子樹左子樹 （3 3）先序遍歷右子樹：即按）先序遍歷右子樹：即按 T T L L R R 的順序遍歷的順序遍歷右子樹右子樹圖示圖示p先序遍歷先序遍歷（T L RT L R）例例6.3 .1 二叉樹的遍歷方法二叉樹的遍歷方法53 第六章 樹和二叉樹 d d e e c c b b f f a a + + * * / / - - - - 先序遍歷下圖所示的二叉樹先序遍歷下圖所示的二叉樹 先序先序 - -,+,+,a,a,* *,b,-,c,d,b,-,c,d,/,e,f,/,e,f練習(xí)練習(xí)6

41、.3 .1 二叉樹的遍歷方法二叉樹的遍歷方法54 第六章 樹和二叉樹若二叉樹非空若二叉樹非空（1 1）后序遍歷左子樹）后序遍歷左子樹（2 2）后序遍歷右子樹）后序遍歷右子樹（3 3）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) 后序遍歷序列：后序遍歷序列： D D, ,G G,E,E,B B,F,C,F,C,A A 后后序遍歷右圖所示的二叉樹序遍歷右圖所示的二叉樹 （1 1）后序遍歷左子樹：即按）后序遍歷左子樹：即按 L L R R T T 的順序遍歷的順序遍歷左子樹左子樹 （2 2）后序遍歷右子樹：即按）后序遍歷右子樹：即按 L L R R T T 的順序遍歷的順序遍歷右子樹右子樹 （3 3）訪問根結(jié)點(diǎn)）訪問根結(jié)

42、點(diǎn)A A圖示圖示p后序遍歷后序遍歷（ L L T T R R ） A A F F G G E E D D C C B B例例6.3 .1 二叉樹的遍歷方法二叉樹的遍歷方法55 第六章 樹和二叉樹 d d e e c c b b f f a a + + * * / / - - - - 后序遍歷下圖所示的二叉樹后序遍歷下圖所示的二叉樹 后序后序 a,b,c,d,-,a,b,c,d,-,* *,+,+,e,f,/,e,f,/,- -練習(xí)練習(xí)6.3 .1 二叉樹的遍歷方法二叉樹的遍歷方法56 第六章 樹和二叉樹p按層遍歷按層遍歷 A A F F G G E E D D C C B B 層次遍歷序列：層

43、次遍歷序列： A,B,C,D,E,F,GA,B,C,D,E,F,G6.3 .1 二叉樹的遍歷方法二叉樹的遍歷方法57 第六章 樹和二叉樹p按層遍歷按層遍歷按層遍歷引入了按層遍歷引入了隊(duì)列隊(duì)列作為輔助工具。作為輔助工具。算法思想為：算法思想為：（1）將二叉樹根入隊(duì)列；）將二叉樹根入隊(duì)列；（2）將隊(duì)頭元素出隊(duì)列，并判斷此元素是否有左右孩）將隊(duì)頭元素出隊(duì)列，并判斷此元素是否有左右孩子，若有，則將它的左右孩子入列，否則轉(zhuǎn)（子，若有，則將它的左右孩子入列，否則轉(zhuǎn)（3）；）；（3）重復(fù)步驟（）重復(fù)步驟（2），直到隊(duì)列為空），直到隊(duì)列為空 。 A A F F G G E E D D C C B B課后思考：

44、按層遍歷算法課后思考：按層遍歷算法6.3 .1 二叉樹的遍歷方法二叉樹的遍歷方法58 第六章 樹和二叉樹6.3 二叉樹的遍歷二叉樹的遍歷 6.3.1 二叉樹的遍歷方法二叉樹的遍歷方法 6.3.2 二叉樹的遍歷算法二叉樹的遍歷算法 59 第六章 樹和二叉樹 若二叉樹非空若二叉樹非空 （1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2 2）先序遍歷左子樹）先序遍歷左子樹 （3 3）先序遍歷右子樹；）先序遍歷右子樹；上面先序遍歷的定義等價(jià)于：上面先序遍歷的定義等價(jià)于：若二叉樹為空，結(jié)束若二叉樹為空，結(jié)束 基本項(xiàng)基本項(xiàng)（也叫終止項(xiàng)）（也叫終止項(xiàng)）若二叉樹非空若二叉樹非空 遞歸項(xiàng)遞歸項(xiàng) （1 1）訪問根結(jié)點(diǎn)；）

45、訪問根結(jié)點(diǎn)； （2 2）先序遍歷左子樹；）先序遍歷左子樹； （3 3）先序遍歷右子樹；）先序遍歷右子樹；6.3.2 二叉樹的遍歷算法二叉樹的遍歷算法p先序遍歷先序遍歷（T T L L R R）的定義的定義60 第六章 樹和二叉樹 void prev (BinTree T) if (T) visit(T-data)； prev(T-lch); prev(T-rch); 先序序列為先序序列為 + * a b c / d e稱為稱為前綴表達(dá)式前綴表達(dá)式 e e a a + + * * / / / d d / - -T T b b c c a a* *(b-c)+d/e(b-c)+d/ep先序遍歷遞歸

46、算法先序遍歷遞歸算法6.3.2 二叉樹的遍歷算法二叉樹的遍歷算法61 第六章 樹和二叉樹void Mid (BinTree T) if (T) Mid(T-lch); visit( T-data)； Mid(T-rch); 中序序列為中序序列為 a * b c+ d / e稱為稱為中綴表達(dá)式中綴表達(dá)式a a* *(b-c)+d/e(b-c)+d/e e e a a + + * * / / / d d / - -T T b b c c p中序遍歷遞歸算法中序遍歷遞歸算法6.3.2 二叉樹的遍歷算法二叉樹的遍歷算法62 第六章 樹和二叉樹void Post(BinTree T) if (T) Po

47、st(T-lch); Post(T-rch); visti( T-data)； 后序序列為后序序列為 a b c * d e / + 稱為稱為后綴表達(dá)式后綴表達(dá)式a a* *(b-c)+d/e(b-c)+d/e e e a a + + * * / / / d d / - -T T b b c c p后序遍歷遞歸算法后序遍歷遞歸算法6.3.2 二叉樹的遍歷算法二叉樹的遍歷算法63 第六章 樹和二叉樹BiTNode *GoFarLeft(BiTree T, Stack *S)/找到左子樹的最左下的結(jié)點(diǎn)找到左子樹的最左下的結(jié)點(diǎn) if (!T ) return NULL; while (T-lch )

48、 Push(S, T); T = T-lch; return T; d d b b e e a a * * - - / / c c + +p 中序遍歷的非遞歸算法中序遍歷的非遞歸算法中序序列為：中序序列為： a * b c+ d / e6.3.2 二叉樹的遍歷算法二叉樹的遍歷算法64 第六章 樹和二叉樹p 中序遍歷的非遞歸算法中序遍歷的非遞歸算法void Inorder_I(BiTree T)void Inorder_I(BiTree T) Stack Stack * *S;S; t = t = GoFarLeftGoFarLeft(T, S);(T, S); / / 找到最左下的結(jié)點(diǎn)找到最左

49、下的結(jié)點(diǎn) while(t)while(t) visit(t-data);visit(t-data); if (t-rch) if (t-rch) t = t = GoFarLeft(t-rch, S); GoFarLeft(t-rch, S); else if ( !StackEmpty(S ) else if ( !StackEmpty(S ) / / 棧不空時(shí)退棧棧不空時(shí)退棧 t = Pop(S);t = Pop(S); else t = NULL; else t = NULL; / ?？毡砻鞅闅v結(jié)束?？毡砻鞅闅v結(jié)束 / while / while/ Inorder_I / Inorder

50、_I 6.3.2 二叉樹的遍歷算法二叉樹的遍歷算法65 第六章 樹和二叉樹6.4 遍歷的應(yīng)用遍歷的應(yīng)用遍歷是二叉樹各種操作的基礎(chǔ)，可以在遍歷過程中對(duì)結(jié)遍歷是二叉樹各種操作的基礎(chǔ)，可以在遍歷過程中對(duì)結(jié)點(diǎn)進(jìn)行各種操作：點(diǎn)進(jìn)行各種操作：（1 1）求結(jié)點(diǎn)的雙親、孩子結(jié)點(diǎn)、結(jié)點(diǎn)的層次；）求結(jié)點(diǎn)的雙親、孩子結(jié)點(diǎn)、結(jié)點(diǎn)的層次；（2 2）求孩子結(jié)點(diǎn)；）求孩子結(jié)點(diǎn)；（3 3）求結(jié)點(diǎn)的層次；）求結(jié)點(diǎn)的層次；（4 4）遍歷過程中生成結(jié)點(diǎn)，建立二叉樹；）遍歷過程中生成結(jié)點(diǎn)，建立二叉樹；遍歷二叉樹的過程實(shí)質(zhì)遍歷二叉樹的過程實(shí)質(zhì):是把二叉樹的結(jié)點(diǎn)進(jìn)行線性排列的過程。是把二叉樹的結(jié)點(diǎn)進(jìn)行線性排列的過程。66 第六章 樹和二

51、叉樹 6.4.1 遍歷的基本應(yīng)用遍歷的基本應(yīng)用 6.4.2 二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用 6.4.3 二叉樹的相似與等價(jià)二叉樹的相似與等價(jià)6.4 遍歷的應(yīng)用遍歷的應(yīng)用67 第六章 樹和二叉樹遞歸建立二叉樹遞歸建立二叉樹 我們按先序遞歸遍歷的思想來建立二叉樹。我們按先序遞歸遍歷的思想來建立二叉樹。其建立思想如下：其建立思想如下：（1）建立二叉樹的根結(jié)點(diǎn)；）建立二叉樹的根結(jié)點(diǎn)；（2）先序建立二叉樹的左子樹；）先序建立二叉樹的左子樹；（3）先序建立二叉樹的右子樹。）先序建立二叉樹的右子樹。p 二叉樹的生成二叉樹的生成6.4.1 遍歷的基本應(yīng)用遍歷的基本應(yīng)用68 第六章 樹

52、和二叉樹二叉樹的生成的遞歸算法二叉樹的生成的遞歸算法bitree *creat() bitree *t; t=(bitree*)malloc(sizeof(bitree); t-data=x; t-lch=creat(); t-rch=creat(); return t;p 二叉樹的生成二叉樹的生成6.4.1 遍歷的基本應(yīng)用遍歷的基本應(yīng)用69 第六章 樹和二叉樹p 求二叉樹的葉子數(shù)。求二叉樹的葉子數(shù)。算法思想：采用任何遍歷方法，遍歷時(shí)判斷訪問的結(jié)點(diǎn)是不是葉子，算法思想：采用任何遍歷方法，遍歷時(shí)判斷訪問的結(jié)點(diǎn)是不是葉子，若是則葉子數(shù)加若是則葉子數(shù)加1 1。int countleaf(bitree

53、 t ,int num) if(t!=NULL) if(t-lch=NULL) &(t- rch)=NULL) num+; num=countleaf(t-lch,num); num=countleaf(t-rch,num); return num;6.4.1 遍歷的基本應(yīng)用遍歷的基本應(yīng)用70 第六章 樹和二叉樹p 求二叉樹的深度求二叉樹的深度算法思想：從第一層的根結(jié)點(diǎn)開始往下遞推可得到。算法思想：從第一層的根結(jié)點(diǎn)開始往下遞推可得到。下面給出后序遍歷求二叉樹深度的遞歸算法下面給出后序遍歷求二叉樹深度的遞歸算法：Int treedepth(bitree *t) int h,lh,rh; if(t

54、=NULL) h=0; else lh=treedepth(t-lch); rh=treedepth(t-rch); if(lh=rh) h=lh+1; else h=rh+1; return h; 6.4.1 遍歷的基本應(yīng)用遍歷的基本應(yīng)用71 第六章 樹和二叉樹 6.4.1 遍歷的基本應(yīng)用遍歷的基本應(yīng)用 6.4.2 二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用 6.4.3 二叉樹的相似與等價(jià)二叉樹的相似與等價(jià)6.4. 遍歷的應(yīng)用遍歷的應(yīng)用72 第六章 樹和二叉樹問題：問題：給定一個(gè)遍歷序列，能否唯一確定一棵二叉樹？給定一個(gè)遍歷序列，能否唯一確定一棵二叉樹？例如：先序序列為例如：先

55、序序列為ABCD,ABCD,其二叉樹的結(jié)構(gòu)是什么？其二叉樹的結(jié)構(gòu)是什么？答案是不唯一6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用 A A C C B B D D A A D D C C B B A A C C D D B Bp二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)之間的轉(zhuǎn)化二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)之間的轉(zhuǎn)化73 第六章 樹和二叉樹p構(gòu)造二叉樹構(gòu)造二叉樹 給定某兩種遍歷序列能否唯一確定一棵二叉樹？給定某兩種遍歷序列能否唯一確定一棵二叉樹？ 給定中序和后序給定中序和后序 給定中序和前序給定中序和前序 給定先序和后序給定先序和后序不能不能唯一確定一棵二叉樹唯一確定一棵二叉樹唯一確定一棵二叉樹唯一

56、確定一棵二叉樹唯一確定一棵二叉樹唯一確定一棵二叉樹關(guān)鍵關(guān)鍵（1 1）確定二叉樹的根結(jié)點(diǎn)；）確定二叉樹的根結(jié)點(diǎn)； （2 2）結(jié)點(diǎn)的左右次序。）結(jié)點(diǎn)的左右次序。6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用74 第六章 樹和二叉樹 給定二叉樹先序和中序遍歷序列，如何構(gòu)造二叉樹？給定二叉樹先序和中序遍歷序列，如何構(gòu)造二叉樹？ 先序：先序：1 2 4 6 3 5 7 81 2 4 6 3 5 7 8 中序：中序：2 6 4 1 3 7 5 82 6 4 1 3 7 5 81前前 246中中264前前3578中中3758例例左左2前前 46中中64右右461前前3578中中37582

57、46p構(gòu)造二叉樹構(gòu)造二叉樹6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用75 第六章 樹和二叉樹根據(jù)給定的遍歷次序構(gòu)造二叉樹，并給出先根據(jù)給定的遍歷次序構(gòu)造二叉樹，并給出先序遍歷序列。序遍歷序列。中序遍歷序列：中序遍歷序列：a,+,b,a,+,b,* *,c,-,d,-,e,/,f,c,-,d,-,e,/,f后序遍歷序列：后序遍歷序列：a,b,c,d,-,a,b,c,d,-,* *,+,e,f,/,-,+,e,f,/,-作業(yè)作業(yè)p構(gòu)造二叉樹構(gòu)造二叉樹6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用76 第六章 樹和二叉樹 e e d d c c b b f

58、 f a a + + * * / / - - - -先序先序:-,+,a,:-,+,a,* *,b,-,c,d,b,-,c,d,/,e,f,/,e,fp構(gòu)造二叉樹構(gòu)造二叉樹6.4.2二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用77 第六章 樹和二叉樹6.4 遍歷的應(yīng)用遍歷的應(yīng)用 6.4.1 遍歷的基本應(yīng)用遍歷的基本應(yīng)用 6.4.2 二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用 6.4.3 二叉樹的相似與等價(jià)二叉樹的相似與等價(jià)78 第六章 樹和二叉樹p二叉樹的相似與等價(jià)的含義二叉樹的相似與等價(jià)的含義兩株二叉樹具有兩株二叉樹具有相同結(jié)構(gòu)相同結(jié)構(gòu)指：指： （1）它們都是空的）

59、它們都是空的 ； （2）它們都是非空的，且左右子樹分別具有相同結(jié)構(gòu)。）它們都是非空的，且左右子樹分別具有相同結(jié)構(gòu)。 “形狀形狀”相相同同6.4.3 二叉樹的相似與等價(jià)二叉樹的相似與等價(jià)79 第六章 樹和二叉樹p判斷兩株二叉樹是否等價(jià)判斷兩株二叉樹是否等價(jià)int EQUAL( t1 , t2 )BTREE t1 , t2 ; int x ; x = 0 ; if ( ISEMPTY(t1) & ISEMPTY(t2) )/二叉樹空二叉樹空 x = 1 ; else if ( !ISEMPTY( t1 ) & ! ISEMPTY( t2) ) /二叉樹不空二叉樹不空 if ( DATA( t1 )

60、 = DATA( t2 ) ) if ( EQUAL( LCHILD( t1 ) , LCHILD( t2 ) ) ) x= EQUAL( RCHILD( t1) , RCHILD( t2) ) return( x ) ; /* EQUAL */6.4.3 二叉樹的相似與等價(jià)二叉樹的相似與等價(jià)80 第六章 樹和二叉樹p二叉樹的復(fù)制二叉樹的復(fù)制BTREE COPY( BTREE oldtree ) BTREE temp ; if ( oldtree != NULL ) temp = new Node ; temp - lch = COPY( oldtree-lch ) ; temp - rch