第六章叉與二叉樹(shù)

1、1 6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念6.2 二叉樹(shù)二叉樹(shù)6.3 二叉樹(shù)的遍歷二叉樹(shù)的遍歷6.4 遍歷的應(yīng)用遍歷的應(yīng)用6.5 線索二叉樹(shù)線索二叉樹(shù)6.6 樹(shù)和森林樹(shù)和森林6.7 樹(shù)及應(yīng)用樹(shù)及應(yīng)用2 本章重點(diǎn)難點(diǎn)重點(diǎn)重點(diǎn)：(1)二叉樹(shù)的定義、結(jié)構(gòu)特點(diǎn)和性質(zhì)；二叉樹(shù)的定義、結(jié)構(gòu)特點(diǎn)和性質(zhì)；(2)ADT二二叉樹(shù)的設(shè)計(jì)和實(shí)現(xiàn)，二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，三種遍歷叉樹(shù)的設(shè)計(jì)和實(shí)現(xiàn)，二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，三種遍歷方式的遞歸和非遞歸算法。方式的遞歸和非遞歸算法。(3)二叉樹(shù)的線索化過(guò)程和二叉樹(shù)的線索化過(guò)程和算法；算法；(4)最優(yōu)二叉樹(shù)的特性及建立最優(yōu)二叉樹(shù)和哈夫最優(yōu)二叉樹(shù)的特性及建立最優(yōu)二叉樹(shù)和哈夫曼編碼的方法。曼

2、編碼的方法。難點(diǎn)難點(diǎn)：二叉樹(shù)的線索化算法；設(shè)計(jì)解決與樹(shù)或二叉樹(shù)：二叉樹(shù)的線索化算法；設(shè)計(jì)解決與樹(shù)或二叉樹(shù)相關(guān)的應(yīng)用問(wèn)題的有效算法。相關(guān)的應(yīng)用問(wèn)題的有效算法。 3 6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念6.2 二叉樹(shù)二叉樹(shù)6.3 二叉樹(shù)的遍歷二叉樹(shù)的遍歷6.4 遍歷的應(yīng)用遍歷的應(yīng)用6.5 線索二叉樹(shù)線索二叉樹(shù)6.6 樹(shù)和森林樹(shù)和森林6.7 樹(shù)及應(yīng)用樹(shù)及應(yīng)用4 6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念1. 樹(shù)的概念樹(shù)的概念2. 樹(shù)的應(yīng)用樹(shù)的應(yīng)用3. 樹(shù)的表示樹(shù)的表示4. 樹(shù)的有關(guān)術(shù)語(yǔ)樹(shù)的有關(guān)術(shù)語(yǔ)5 樹(shù)形結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。樹(shù)是樹(shù)形結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。樹(shù)是n個(gè)結(jié)點(diǎn)的有限集合，個(gè)結(jié)點(diǎn)的有限集合，在任

3、一棵非空樹(shù)中：在任一棵非空樹(shù)中：（1）有且僅有一個(gè)稱(chēng)為根的結(jié)點(diǎn)。）有且僅有一個(gè)稱(chēng)為根的結(jié)點(diǎn)。（2）其余結(jié)點(diǎn)可分為）其余結(jié)點(diǎn)可分為m個(gè)互不相交的集合，而且這些集合中的每個(gè)互不相交的集合，而且這些集合中的每一集合都本身又是一棵樹(shù)，稱(chēng)為根的子樹(shù)。一集合都本身又是一棵樹(shù)，稱(chēng)為根的子樹(shù)。說(shuō)明：說(shuō)明：樹(shù)是遞歸結(jié)構(gòu)，在樹(shù)的定義中又用到了樹(shù)的概念樹(shù)是遞歸結(jié)構(gòu)，在樹(shù)的定義中又用到了樹(shù)的概念 J JI IA AC CB BD DH HG GF FE EK KL LM Mp 樹(shù)的概念樹(shù)的概念 6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念6 p 樹(shù)的概念樹(shù)的概念 6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D：D是具有相同

4、特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集，則稱(chēng)為空樹(shù)為空集，則稱(chēng)為空樹(shù) 。 否則否則: (1) 在在D中存在唯一的稱(chēng)為根的數(shù)據(jù)元素中存在唯一的稱(chēng)為根的數(shù)據(jù)元素root； (2) 當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m (m0)個(gè)互個(gè)互 不相交的有限集不相交的有限集T1, T2, , Tm，其中每一，其中每一 棵子集本身又是一棵符合本定義的樹(shù)，棵子集本身又是一棵符合本定義的樹(shù)， 稱(chēng)為根稱(chēng)為根root的子樹(shù)。的子樹(shù)。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R：ADT Tree7 p 樹(shù)的概念樹(shù)的概念 6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念基本操作基本操作 P：ADT Tree查查 找找

5、類(lèi)類(lèi) 插插 入入 類(lèi)類(lèi)刪刪 除除 類(lèi)類(lèi) 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D： 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R：8 p 樹(shù)的基本操作樹(shù)的基本操作P 6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念 Root(T) / 求樹(shù)的根結(jié)點(diǎn)求樹(shù)的根結(jié)點(diǎn) 查找類(lèi)：查找類(lèi)：Value(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的元素值求當(dāng)前結(jié)點(diǎn)的元素值 Parent(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的最左孩子求當(dāng)前結(jié)點(diǎn)的最左孩子 RightSibling(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的右兄弟求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T) / 判定樹(shù)是否為空樹(shù)判定樹(shù)是否為

6、空樹(shù) TreeDepth(T) / 求樹(shù)的深度求樹(shù)的深度TraverseTree( T, Visit() ) / 遍歷遍歷9 p 樹(shù)的基本操作樹(shù)的基本操作P 6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念插入類(lèi)：插入類(lèi)：InitTree(&T) / 初始化置空樹(shù)初始化置空樹(shù) CreateTree(&T, definition) / 按定義構(gòu)造樹(shù)按定義構(gòu)造樹(shù)Assign(T, cur_e, value) / 給當(dāng)前結(jié)點(diǎn)賦值給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T, &p, i, c) / 將以將以c為根的樹(shù)插入為結(jié)點(diǎn)為根的樹(shù)插入為結(jié)點(diǎn)p的第的第i棵子樹(shù)棵子樹(shù)10 p 樹(shù)的基本

7、操作樹(shù)的基本操作P 6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念刪除類(lèi)：刪除類(lèi)： ClearTree(&T) / 將樹(shù)清空將樹(shù)清空 DestroyTree(&T) / 銷(xiāo)毀樹(shù)的結(jié)構(gòu)銷(xiāo)毀樹(shù)的結(jié)構(gòu)DeleteChild(&T, &p, i) / 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)p的第的第i棵子樹(shù)棵子樹(shù)11 T=A, B, C, D, E, F, G, H, I, J，K，L，MA是根，其余結(jié)點(diǎn)可以劃分為是根，其余結(jié)點(diǎn)可以劃分為3個(gè)個(gè)互不相交的集合互不相交的集合： T1=B, E, F，K，L , T2=C, G , T3=D, H, I, J，M這些集合中的每一集合都本身又是一棵樹(shù)，它們是這些

8、集合中的每一集合都本身又是一棵樹(shù)，它們是A的子樹(shù)。的子樹(shù)。J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念p 樹(shù)的概念樹(shù)的概念 12 從邏輯結(jié)構(gòu)看：從邏輯結(jié)構(gòu)看：樹(shù)中只有根結(jié)點(diǎn)沒(méi)有前趨；其余結(jié)點(diǎn)有零個(gè)或多個(gè)后繼；樹(shù)中只有根結(jié)點(diǎn)沒(méi)有前趨；其余結(jié)點(diǎn)有零個(gè)或多個(gè)后繼；除根外，其余結(jié)點(diǎn)都有且僅一個(gè)前趨；都存在唯一條從根到該除根外，其余結(jié)點(diǎn)都有且僅一個(gè)前趨；都存在唯一條從根到該結(jié)點(diǎn)的路徑；結(jié)點(diǎn)的路徑；樹(shù)是一種分枝結(jié)構(gòu)樹(shù)是一種分枝結(jié)構(gòu) （除了一個(gè)稱(chēng)為根的結(jié)點(diǎn)外）每個(gè)元素都有（除了一個(gè)稱(chēng)為根的結(jié)點(diǎn)外）每個(gè)元素都有且僅有一個(gè)直接前趨，有且僅有零個(gè)或

9、多個(gè)直接后繼。且僅有一個(gè)直接前趨，有且僅有零個(gè)或多個(gè)直接后繼。J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念p 樹(shù)的概念樹(shù)的概念 13 6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念p 樹(shù)的概念樹(shù)的概念 線性結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無(wú)前驅(qū)無(wú)前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn)( (無(wú)前驅(qū)無(wú)前驅(qū)) )最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素 ( (無(wú)后繼無(wú)后繼) )多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) ( (無(wú)后繼無(wú)后繼) ) 其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)后繼一個(gè)前驅(qū)、一個(gè)后繼) ) 其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)

10、、多個(gè)后繼一個(gè)前驅(qū)、多個(gè)后繼) )14 家族族譜：設(shè)某家庭有家族族譜：設(shè)某家庭有13個(gè)成員個(gè)成員A、B、C、D、E、F、G、H、I、J，K，L，M他們之間的關(guān)系可下圖所示的樹(shù)表示：他們之間的關(guān)系可下圖所示的樹(shù)表示： 單位行政機(jī)構(gòu)的組織關(guān)系單位行政機(jī)構(gòu)的組織關(guān)系1）樹(shù)可表示具有分枝結(jié)構(gòu)關(guān)系的對(duì)象）樹(shù)可表示具有分枝結(jié)構(gòu)關(guān)系的對(duì)象J JI IA AC CB BD DH HG GF FE EK KL LM M例例例例6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念p 樹(shù)的應(yīng)用樹(shù)的應(yīng)用 15 2）樹(shù)是常用的數(shù)據(jù)組織形式）樹(shù)是常用的數(shù)據(jù)組織形式 有些應(yīng)用中數(shù)據(jù)元素之間并不存在分支結(jié)構(gòu)關(guān)系，但是為了便有些應(yīng)用中數(shù)據(jù)元素之間

11、并不存在分支結(jié)構(gòu)關(guān)系，但是為了便于管理和使用數(shù)據(jù)，將它們用樹(shù)的形式來(lái)組織。于管理和使用數(shù)據(jù)，將它們用樹(shù)的形式來(lái)組織。C文件夾文件夾1 文件夾文件夾2 文件文件1 文件文件2文件夾文件夾11 文件夾文件夾12 文件文件11 文件文件12 計(jì)算機(jī)的文件系統(tǒng)計(jì)算機(jī)的文件系統(tǒng) 不論是不論是DOS文件系統(tǒng)還是文件系統(tǒng)還是window文件系統(tǒng)，所有的文件是用樹(shù)文件系統(tǒng)，所有的文件是用樹(shù)的形式來(lái)組織的。的形式來(lái)組織的。例例6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念p 樹(shù)的應(yīng)用樹(shù)的應(yīng)用 16 （1 1）樹(shù)形表示法）樹(shù)形表示法ABEKLFCGDHMJI（2 2）凹入表示法）凹入表示法J JI IA AC CB BD DH

12、 HG GF FE EK KL LM M6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念p 樹(shù)的表示樹(shù)的表示 17 （3 3）嵌套集合表示法）嵌套集合表示法 （文氏圖）（文氏圖）AEDHJIKLMFGCBJ JI IA AC CB BD DH HG GF FE EK KL LM M6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念p 樹(shù)的表示樹(shù)的表示 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

13、(E(K,LK,L),F),F), ), C C( (G G), ), D D( (H(H(M M),I,J),I,J) ) 第四層第四層J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念p 樹(shù)的表示樹(shù)的表示 19 結(jié)點(diǎn)層結(jié)點(diǎn)層：根結(jié)點(diǎn)的層定義為：根結(jié)點(diǎn)的層定義為1，其它依此類(lèi)推；，其它依此類(lèi)推；樹(shù)的深度樹(shù)的深度：樹(shù)中最大的結(jié)點(diǎn)層：樹(shù)中最大的結(jié)點(diǎn)層結(jié)點(diǎn)的度結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹(shù)的個(gè)數(shù)：結(jié)點(diǎn)子樹(shù)的個(gè)數(shù)樹(shù)的度樹(shù)的度： 樹(shù)中最大的結(jié)點(diǎn)度。樹(shù)中最大的結(jié)點(diǎn)度。葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為：也叫終端結(jié)點(diǎn)，是度為 0 的結(jié)點(diǎn)；的結(jié)點(diǎn)；樹(shù)的度為

14、樹(shù)的度為3樹(shù)的深度為樹(shù)的深度為4第第1層層第第3層層第第2層層第第4層層J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念p 樹(shù)的有關(guān)術(shù)語(yǔ)樹(shù)的有關(guān)術(shù)語(yǔ) 20 分枝結(jié)點(diǎn)：分枝結(jié)點(diǎn)：度不為度不為0的結(jié)點(diǎn)；的結(jié)點(diǎn)；有序樹(shù)：有序樹(shù)：子樹(shù)有序的樹(shù)，如：家族樹(shù)；子樹(shù)有序的樹(shù)，如：家族樹(shù)；無(wú)序樹(shù)：無(wú)序樹(shù)：不考慮子樹(shù)的順序；不考慮子樹(shù)的順序；森林：森林：互不相交的樹(shù)集合；森林和樹(shù)之間的聯(lián)系是：一棵樹(shù)去掉互不相交的樹(shù)集合；森林和樹(shù)之間的聯(lián)系是：一棵樹(shù)去掉根根 ，其子樹(shù)構(gòu)成一個(gè)森林；一個(gè)森林增加一個(gè)根結(jié)點(diǎn)成為樹(shù)。，其子樹(shù)構(gòu)成一個(gè)森林；一個(gè)森林增加一個(gè)根結(jié)

15、點(diǎn)成為樹(shù)。J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 樹(shù)的有關(guān)概念樹(shù)的有關(guān)概念p 樹(shù)的有關(guān)術(shù)語(yǔ)樹(shù)的有關(guān)術(shù)語(yǔ) 21 樹(shù)是一種分枝結(jié)構(gòu)的對(duì)象，在樹(shù)的概念中，對(duì)每一樹(shù)是一種分枝結(jié)構(gòu)的對(duì)象，在樹(shù)的概念中，對(duì)每一個(gè)結(jié)點(diǎn)孩子的個(gè)數(shù)沒(méi)有限制，因此樹(shù)的形態(tài)多種多樣，個(gè)結(jié)點(diǎn)孩子的個(gè)數(shù)沒(méi)有限制，因此樹(shù)的形態(tài)多種多樣，本節(jié)我們主要討論一種最簡(jiǎn)單的樹(shù)本節(jié)我們主要討論一種最簡(jiǎn)單的樹(shù)二叉樹(shù)。二叉樹(shù)。6.2 二叉樹(shù)二叉樹(shù) A A F F G G E E D D C C B B22 6.2.1 6.2.1 二叉樹(shù)的概念二叉樹(shù)的概念 6.2.2 6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) 6

16、.2.3 6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.2 二叉樹(shù)二叉樹(shù)23 6.2.1 二叉樹(shù)的概念二叉樹(shù)的概念說(shuō)明：說(shuō)明：二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)；即二叉樹(shù)二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)；即二叉樹(shù)每個(gè)結(jié)每個(gè)結(jié)點(diǎn)度小于等于點(diǎn)度小于等于2 2; ;左、右子樹(shù)不能顛倒左、右子樹(shù)不能顛倒有序樹(shù)有序樹(shù); ;二叉樹(shù)是二叉樹(shù)是遞歸結(jié)構(gòu)遞歸結(jié)構(gòu)，在二叉樹(shù)的定義中又用到了二叉，在二叉樹(shù)的定義中又用到了二叉樹(shù)的概念樹(shù)的概念; ; A A F F G G E E D D C C B B二叉樹(shù)二叉樹(shù)或?yàn)榭諛?shù)，或由根及兩顆不相交的左子樹(shù)、或?yàn)榭諛?shù)，或由根及兩顆不相交的左子樹(shù)、右子樹(shù)構(gòu)成，并且右子樹(shù)構(gòu)成，并且

17、左、右子樹(shù)本身也是二叉樹(shù)左、右子樹(shù)本身也是二叉樹(shù)。24 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)二叉樹(shù)是有左右之分的6.2.1 二叉樹(shù)的概念二叉樹(shù)的概念25 p 二叉樹(shù)的基本形態(tài)二叉樹(shù)的基本形態(tài)(a)空樹(shù)(b)僅有根(c) 右子樹(shù)空(d) 左子樹(shù)空(e) 左、右子樹(shù)均在6.2.1 二叉樹(shù)的概念二叉樹(shù)的概念26 應(yīng)用舉例 用二叉樹(shù)表示計(jì)算表達(dá)式用二叉樹(shù)表示計(jì)算表達(dá)式 a+b*(c-d)-e/f e e d d c c b b f f a a + + * * / / - - - -例例6.2.1 二叉樹(shù)的概念二叉樹(shù)的

18、概念27 6.2.1 6.2.1 二叉樹(shù)的概念二叉樹(shù)的概念 6.2.2 6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) 6.2.3 6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.2 二叉樹(shù)二叉樹(shù)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的二叉樹(shù)的二叉樹(shù)有有個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。性質(zhì)性質(zhì)1 1 在二叉樹(shù)的第在二叉樹(shù)的第i(i1)i(i1)層上層上有有個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 證明：用數(shù)學(xué)歸納法就可以證明。證明：用數(shù)學(xué)歸納法就可以證明。ABCDEFGIHJ k k層二叉樹(shù)層二叉樹(shù)6.

19、2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)29 p 兩種特殊的二叉樹(shù)兩種特殊的二叉樹(shù) A A G G F F E E D D C C B B(a)(a)K=3K=3的滿二叉樹(shù)的滿二叉樹(shù)滿二叉樹(shù)：滿二叉樹(shù)：如果深度為如果深度為k k的二叉樹(shù)，有的二叉樹(shù)，有2 2k k-1-1個(gè)結(jié)點(diǎn)則稱(chēng)為滿二叉樹(shù)；個(gè)結(jié)點(diǎn)則稱(chēng)為滿二叉樹(shù)；完全二叉樹(shù)：二叉樹(shù)中所含的二叉樹(shù)中所含的 n n 個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)為個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(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)完全二叉樹(shù) G G A A E E D D C C B B(c)(c)(c) (c

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

21、2:2:深度為深度為k k的二叉樹(shù)最多有的二叉樹(shù)最多有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 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)31 性質(zhì)性質(zhì)4 4 對(duì)任意二叉樹(shù)對(duì)任意二叉樹(shù)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。 證明：二叉樹(shù)證明：二叉樹(shù)T T的的結(jié)點(diǎn)總數(shù)結(jié)點(diǎn)總數(shù) n=nn=n0 0+n+n1 1+

22、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）二叉樹(shù)的二叉樹(shù)的分支結(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 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)32 性質(zhì)性質(zhì)5:5:若對(duì)含若對(duì)含 n n 個(gè)結(jié)點(diǎn)

23、的完全二叉樹(shù)從上到下且從左個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下且從左至右進(jìn)行至右進(jìn)行 1 1 至至 n n 的編號(hào)，則對(duì)完全二叉樹(shù)中任意一個(gè)的編號(hào)，則對(duì)完全二叉樹(shù)中任意一個(gè)編號(hào)為編號(hào)為 i i 的結(jié)點(diǎn)的結(jié)點(diǎn): :(1) (1) 若若 i=1i=1，則該結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)雙親，否則，則該結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)雙親，否則， 編號(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)無(wú)右孩子結(jié)點(diǎn)，否則，編號(hào)為，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，否則，編號(hào)為 2i+1 2i+1 的結(jié)點(diǎn)為其的結(jié)點(diǎn)為其右孩子右孩子結(jié)點(diǎn)。結(jié)點(diǎn)。(2) (2) 若若 2in2in，則該

24、結(jié)點(diǎn)無(wú)左孩子，否則，編號(hào)為，則該結(jié)點(diǎn)無(wú)左孩子，否則，編號(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 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)33 編號(hào)編號(hào)i=4i=4雙親為雙親為 i/2i/2 =2 =2左子樹(shù)為左子樹(shù)為2i=82i=8右子樹(shù)為右子樹(shù)為2i+1=92i+1=9i=1 只有根結(jié)點(diǎn)只有根結(jié)點(diǎn)編號(hào)編號(hào)i=5i=5雙親為雙親為 i/2i/2 =2 =2左子樹(shù)為左子樹(shù)為2i=10 2i=10 右子樹(shù)為右子樹(shù)為2i+1=112i+1=11i=8,i=8,2in2in無(wú)左子樹(shù)無(wú)左子/p>

25、 10 11 12 13 146.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)34 6.2.1 二叉樹(shù)的概念二叉樹(shù)的概念 6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) 6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.2 二叉樹(shù)二叉樹(shù)35 p二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示p 二叉樹(shù)的順序存儲(chǔ)表示二叉樹(shù)的順序存儲(chǔ)表示6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)36 性質(zhì)性質(zhì)5:5:若對(duì)含若對(duì)含 n n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下且從左至右個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下且從左至右進(jìn)行進(jìn)行 1 1 至至 n n 的編號(hào)，則對(duì)完全二叉樹(shù)中任意一個(gè)編號(hào)為的編號(hào)，則對(duì)完全二叉樹(shù)中任意一個(gè)編號(hào)為 i i 的結(jié)點(diǎn)的結(jié)點(diǎn): :

26、通過(guò)性質(zhì)5把非線性結(jié)構(gòu)輕易轉(zhuǎn)化成了線性結(jié)構(gòu)。 2i+2 2i+2 i/2 2i+12i+1 2i2i i+1i+1 i i6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)37 (1)(1)完全（或滿）二叉樹(shù)完全（或滿）二叉樹(shù)ABCDEFGIHJ采用采用一維數(shù)組一維數(shù)組，按，按層序順序?qū)有蝽樞蛞酪来未鎯?chǔ)二叉樹(shù)的每一個(gè)結(jié)點(diǎn)。次存儲(chǔ)二叉樹(shù)的每一個(gè)結(jié)點(diǎn)。如下圖所示：如下圖所示：p 二叉樹(shù)的順序存儲(chǔ)表示二叉樹(shù)的順序存儲(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

27、E F G1 2 3 4 5 6 7 8 9 10H IJ6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)38 (2)(2)一般二叉樹(shù)一般二叉樹(shù)A B C 0E 0G1 2 3 4 5 6 7 8 9 1000J通過(guò)通過(guò)虛設(shè)虛設(shè)部分結(jié)點(diǎn)，使其變成相應(yīng)的部分結(jié)點(diǎn)，使其變成相應(yīng)的完全二叉樹(shù)完全二叉樹(shù)。ABCEGJABC0E0G00Jp 二叉樹(shù)的順序存儲(chǔ)表示二叉樹(shù)的順序存儲(chǔ)表示6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)39 (3)(3)特殊的二叉樹(shù)特殊的二叉樹(shù)說(shuō)明：說(shuō)明：順序存儲(chǔ)方式對(duì)于畸形二叉樹(shù)，浪費(fèi)較大空間順序存儲(chǔ)方式對(duì)于畸形二叉樹(shù)，浪費(fèi)較大空間p 二叉樹(shù)的順序存儲(chǔ)表示二叉樹(shù)的順序存儲(chǔ)表示6.2.

28、3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)ABCJ40 二叉鏈表存儲(chǔ)：二叉鏈表存儲(chǔ)：二叉鏈表中每個(gè)結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域、左指針域、右指針域二叉鏈表中每個(gè)結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域、左指針域、右指針域 typedef typedef Struct nodeStruct node DataType data; DataType data; Struct nodeStruct node * *lch,lch,* *rch;rch; BinTNode; BinTNode;lchrchdataC 語(yǔ)言的類(lèi)型描述如下語(yǔ)言的類(lèi)型描述如下: :p 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二

29、叉樹(shù)的存儲(chǔ)結(jié)構(gòu)41 二叉鏈表圖示二叉鏈表圖示 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二叉樹(shù)二叉樹(shù)n 個(gè)結(jié)點(diǎn)的二叉樹(shù)中，有多少個(gè)空鏈接域？p 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)42 性質(zhì)性質(zhì)6 6：n n 個(gè)結(jié)點(diǎn)的二叉樹(shù)中，共有個(gè)結(jié)點(diǎn)的二叉樹(shù)中，共有 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ù)即所以

30、，剩余的結(jié)點(diǎn)數(shù)即空指針域個(gè)數(shù)空指針域個(gè)數(shù)為：為：2n-2n-（n-1n-1）=n+1 =n+1 二叉鏈表的缺點(diǎn)二叉鏈表的缺點(diǎn)是很難找到結(jié)點(diǎn)的雙親是很難找到結(jié)點(diǎn)的雙親二叉鏈表圖示二叉鏈表圖示 D D A A C C E E F F B B rootp 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)43 三叉鏈表（三叉鏈表（帶雙親指針的二叉鏈表帶雙親指針的二叉鏈表）: :三叉鏈表中每個(gè)結(jié)點(diǎn)三叉鏈表中每個(gè)結(jié)點(diǎn)包含四個(gè)域：數(shù)據(jù)域、左指針域、右指針域、包含四個(gè)域：數(shù)據(jù)域、左指針域、右指針域、雙親指針域雙親指針域typedef typedef Struct nodeS

31、truct node DataType data; DataType data; Struct nodeStruct node * *lch,lch,* *rch,rch,* *parent;parent;lch data rch parent結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):C 語(yǔ)言的類(lèi)型描述如下語(yǔ)言的類(lèi)型描述如下: :p 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)44 A A F F E E D D C C B BA AB BD DF FE EC Crootlch data rch parentp 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)

32、構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)45 二叉樹(shù)的生成的遞歸算法二叉樹(shù)的生成的遞歸算法bitree *creat() bitree *t; t=(bitree*)malloc(sizeof(bitree); t-data=x; t-lch=creat(); t-rch=creat(); return t;p 二叉樹(shù)的生成二叉樹(shù)的生成6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)46 6.3.1 二叉樹(shù)的遍歷方法二叉樹(shù)的遍歷方法 6.3.2 遍歷的遞歸算法遍歷的遞歸算法 6.3.3 遍歷的非遞歸算法遍歷的非遞歸算法6.3 二叉樹(shù)的遍歷二叉樹(shù)的遍歷47 遍歷遍歷：按某種搜索路徑：按某種搜索路徑訪問(wèn)訪問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)

33、，而且每個(gè)二叉樹(shù)的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。結(jié)點(diǎn)僅被訪問(wèn)一次。訪問(wèn)訪問(wèn)：含義很廣，可以是對(duì)結(jié)點(diǎn)的各種處理，如修改結(jié)點(diǎn)：含義很廣，可以是對(duì)結(jié)點(diǎn)的各種處理，如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)等。數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)等。遍歷遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其它的操作可以是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其它的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。在遍歷基礎(chǔ)上實(shí)現(xiàn)。 6.3 二叉樹(shù)的遍歷二叉樹(shù)的遍歷48 “ “遍歷遍歷”是任何類(lèi)型均有的操作：是任何類(lèi)型均有的操作：對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑( (因?yàn)槊總€(gè)結(jié)點(diǎn)均只因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼有一個(gè)后繼) )；二叉樹(shù)是非線性結(jié)構(gòu)

34、，則二叉樹(shù)是非線性結(jié)構(gòu)，則存在如何遍歷存在如何遍歷即按什么樣的即按什么樣的搜索搜索路徑路徑遍歷的問(wèn)題。遍歷的問(wèn)題。 如何訪問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)，如何訪問(wèn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)， 而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次？而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次？6.3 二叉樹(shù)的遍歷二叉樹(shù)的遍歷49 對(duì)對(duì)“二叉樹(shù)二叉樹(shù)”而言，可以有三條搜索路徑：而言，可以有三條搜索路徑：先上后下先上后下的按層次遍歷；的按層次遍歷；先左先左（子樹(shù)）（子樹(shù)）后右后右（子樹(shù)）的遍歷；（子樹(shù)）的遍歷；先右先右（子樹(shù)）（子樹(shù)）后左后左（子樹(shù)）的遍歷（子樹(shù)）的遍歷。6.3 二叉樹(shù)的遍歷方法二叉樹(shù)的遍歷方法50 二叉樹(shù)由根、左子樹(shù)、右子樹(shù)三部分組成二叉樹(shù)由根、左子

35、樹(shù)、右子樹(shù)三部分組成 二叉樹(shù)的遍歷可以分解為：訪問(wèn)根，遍歷左子樹(shù)和遍歷右子樹(shù)二叉樹(shù)的遍歷可以分解為：訪問(wèn)根，遍歷左子樹(shù)和遍歷右子樹(shù)令：令：L L：遍歷左子樹(shù)遍歷左子樹(shù) T T：訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) R R：遍歷右子樹(shù)遍歷右子樹(shù) 有六種遍歷方法：有六種遍歷方法： 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 ，分別稱(chēng)分別稱(chēng)為為 先序遍歷、中序遍歷、后序遍歷先序遍歷

36、、中序遍歷、后序遍歷 A A F F G G E E D D C C B B圖示圖示6.3 二叉樹(shù)的遍歷方法二叉樹(shù)的遍歷方法51 若二叉樹(shù)非空若二叉樹(shù)非空 （1 1）訪問(wèn)根結(jié)點(diǎn)；）訪問(wèn)根結(jié)點(diǎn)； （2 2）先序遍歷左子樹(shù)；）先序遍歷左子樹(shù)； （3 3）先序遍歷右子樹(shù)；）先序遍歷右子樹(shù)； 先序遍歷序列：先序遍歷序列：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 先先序遍歷右圖所示的二叉樹(shù)序遍歷右圖所示的二叉樹(shù) （1 1）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn)A A （2 2）先序遍歷左子樹(shù)：即按先序遍歷左子樹(shù)：即按 T T L L R R

37、的順序遍歷的順序遍歷左子樹(shù)左子樹(shù) （3 3）先序遍歷右子樹(shù)：即按）先序遍歷右子樹(shù)：即按 T T L L R R 的順序遍歷的順序遍歷右子樹(shù)右子樹(shù)圖示圖示p先序遍歷（先序遍歷（T T L L R R）例例6.3 二叉樹(shù)的遍歷方法二叉樹(shù)的遍歷方法52 若二叉樹(shù)非空若二叉樹(shù)非空（1 1）中序遍歷左子樹(shù)）中序遍歷左子樹(shù)（2 2）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn)（3 3）中序遍歷右子樹(shù)）中序遍歷右子樹(shù) 中序遍歷序列：中序遍歷序列：中序遍歷右圖所示的二叉樹(shù)中序遍歷右圖所示的二叉樹(shù) p中序遍歷（中序遍歷（ L L T T R R ） A A F F G G E E D D C C B B,F例例D,G,B,A,E,C

38、圖示圖示6.3 二叉樹(shù)的遍歷方法二叉樹(shù)的遍歷方法53 若二叉樹(shù)非空若二叉樹(shù)非空（1 1）后序遍歷左子樹(shù)）后序遍歷左子樹(shù)（2 2）后序遍歷右子樹(shù)）后序遍歷右子樹(shù)（3 3）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn) 后序遍歷序列：后序遍歷序列： D D, ,G G,E,E,B B,F,C,F,C,A A 后后序遍歷右圖所示的二叉樹(shù)序遍歷右圖所示的二叉樹(shù) （1 1）后序遍歷左子樹(shù)：即按）后序遍歷左子樹(shù)：即按 L L R R T T 的順序遍歷的順序遍歷左子樹(shù)左子樹(shù) （2 2）后序遍歷右子樹(shù)：即按）后序遍歷右子樹(shù)：即按 L L R R T T 的順序遍歷的順序遍歷右子樹(shù)右子樹(shù) （3 3）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn)A A圖示圖

39、示p后序遍歷（后序遍歷（ L L T T R R ） A A F F G G E E D D C C B B例例6.3 二叉樹(shù)的遍歷方法二叉樹(shù)的遍歷方法54 d d e e c c b b f f a a + + * * / / - - - - 先序遍歷、中序遍歷、后序遍歷下圖所示的二叉樹(shù)先序遍歷、中序遍歷、后序遍歷下圖所示的二叉樹(shù) 后序后序 a,b,c,d,-,a,b,c,d,-,* *,+,+,e,f,/,e,f,/,- - 中序中序 a,+,b,a,+,b,* *,c,-,d,c,-,d, ,- -,e,/,f,e,/,f 先序先序 - -,+,+,a,a,* *,b,-,c,d,b,-

40、,c,d,/,e,f,/,e,f例例6.3 二叉樹(shù)的遍歷方法二叉樹(shù)的遍歷方法55 6.3 二叉樹(shù)的遍歷二叉樹(shù)的遍歷 6.3.1 二叉樹(shù)的遍歷算法二叉樹(shù)的遍歷算法 6.3.2 遍歷的遞歸算法遍歷的遞歸算法 6.3.3 遍歷的非遞歸算法遍歷的非遞歸算法56 若二叉樹(shù)非空若二叉樹(shù)非空 （1 1）訪問(wèn)根結(jié)點(diǎn)；）訪問(wèn)根結(jié)點(diǎn)； （2 2）先序遍歷左子樹(shù)）先序遍歷左子樹(shù) （3 3）先序遍歷右子樹(shù)；）先序遍歷右子樹(shù)；上面先序遍歷的定義等價(jià)于：上面先序遍歷的定義等價(jià)于：若二叉樹(shù)為空，結(jié)束若二叉樹(shù)為空，結(jié)束 基本項(xiàng)基本項(xiàng)（也叫終止項(xiàng)）（也叫終止項(xiàng)）若二叉樹(shù)非空若二叉樹(shù)非空 遞歸項(xiàng)遞歸項(xiàng) （1 1）訪問(wèn)根結(jié)點(diǎn)；）訪

41、問(wèn)根結(jié)點(diǎn)； （2 2）先序遍歷左子樹(shù)；）先序遍歷左子樹(shù)； （3 3）先序遍歷右子樹(shù)；）先序遍歷右子樹(shù)；6.3.2 遍歷的遞歸算法遍歷的遞歸算法p先序遍歷（先序遍歷（T T L L R R）的定義的定義57 void prev (BinTree T) if (T) visit(T-data)； prev(T-lch); prev(T-rch); 先序序列為先序序列為 + * a b c / d e稱(chēng)為前綴表達(dá)式稱(chēng)為前綴表達(dá)式 e e a a + + * * / / / d d / - -T T b b c c a a* *(b-c)+d/e(b-c)+d/e6.3.2 遍歷的遞歸算法遍歷的遞歸算

42、法p先序遍歷遞歸算法先序遍歷遞歸算法58 void Mid (BinTree T) if (T) Mid(T-lch); visit( T-data)； Mid(T-rch); 中序序列為中序序列為 a * b c+ d / e稱(chēng)為中綴表達(dá)式稱(chēng)為中綴表達(dá)式a a* *(b-c)+d/e(b-c)+d/e e e a a + + * * / / / d d / - -T T b b c c 6.3.2 遍歷的遞歸算法遍歷的遞歸算法p中序遍歷遞歸算法中序遍歷遞歸算法59 void Post(BinTree T) if (T) Post(T-lch); Post(T-rch); visti( T-d

43、ata)； 后序序列為后序序列為 a b c * d e / + 稱(chēng)為后綴表達(dá)式稱(chēng)為后綴表達(dá)式a a* *(b-c)+d/e(b-c)+d/e e e a a + + * * / / / d d / - -T T b b c c 6.3.2 遍歷的遞歸算法遍歷的遞歸算法p后序遍歷遞歸算法后序遍歷遞歸算法60 6.3 二叉樹(shù)的遍歷二叉樹(shù)的遍歷 6.3.1 二叉樹(shù)的遍歷算法二叉樹(shù)的遍歷算法 6.3.2 遍歷的遞歸算法遍歷的遞歸算法 6.3.3 遍歷的非遞歸算法遍歷的非遞歸算法61 對(duì)每個(gè)結(jié)點(diǎn)，在訪問(wèn)完后，沿其左鏈一直訪問(wèn)下來(lái)，直到左鏈為空對(duì)每個(gè)結(jié)點(diǎn)，在訪問(wèn)完后，沿其左鏈一直訪問(wèn)下來(lái)，直到左鏈為空，

44、這時(shí)，所有已被訪問(wèn)過(guò)的結(jié)點(diǎn)進(jìn)棧。然后結(jié)點(diǎn)出棧，對(duì)于每個(gè)出，這時(shí)，所有已被訪問(wèn)過(guò)的結(jié)點(diǎn)進(jìn)棧。然后結(jié)點(diǎn)出棧，對(duì)于每個(gè)出棧結(jié)點(diǎn)，即表示該結(jié)點(diǎn)和其左子樹(shù)已被訪問(wèn)結(jié)束，應(yīng)該訪問(wèn)該結(jié)點(diǎn)棧結(jié)點(diǎn)，即表示該結(jié)點(diǎn)和其左子樹(shù)已被訪問(wèn)結(jié)束，應(yīng)該訪問(wèn)該結(jié)點(diǎn)的右子樹(shù)。的右子樹(shù)。（1 1）當(dāng)前指針指向根結(jié)點(diǎn)。）當(dāng)前指針指向根結(jié)點(diǎn)。（2 2）打印當(dāng)前結(jié)點(diǎn)，當(dāng)前指針指向其左孩子并進(jìn)棧，重復(fù)（）打印當(dāng)前結(jié)點(diǎn)，當(dāng)前指針指向其左孩子并進(jìn)棧，重復(fù)（2 2），），直到左孩子為直到左孩子為NULLNULL；（3 3）依次退棧，將當(dāng)前指針指向右孩子；）依次退棧，將當(dāng)前指針指向右孩子；（4 4）若棧非空或當(dāng)前指針?lè)牵┤魲７强栈虍?dāng)前指針?lè)荖UL

45、LNULL，執(zhí)行（執(zhí)行（2 2）；否則結(jié)束。）；否則結(jié)束。遞歸算法邏輯清晰、易懂，但在實(shí)現(xiàn)時(shí)，由于函數(shù)調(diào)用棧層層疊加，遞歸算法邏輯清晰、易懂，但在實(shí)現(xiàn)時(shí)，由于函數(shù)調(diào)用棧層層疊加，效率不高，故有時(shí)考慮非遞歸算法。效率不高，故有時(shí)考慮非遞歸算法。6.3.3 遍歷的非遞歸算法遍歷的非遞歸算法1 先序遍歷（先序遍歷（T L R）的非遞歸算法的非遞歸算法62 void prev (NODE *root) NODE *p, *nodeMAX; int top=0; p=root; do while( p!=NULL) visit(t-data); nodetop=p;top+; p=p-lch; if (

46、top0) top - -; p=nodetop; p=p-rch; while(top0|p!=NULL); d d b b e e a a * * - - / / c c + +p 先序遍歷的非遞歸算法先序遍歷的非遞歸算法6.3.3 遍歷的非遞歸算法遍歷的非遞歸算法63 d d b b a a * * - - / / c c + + e erootrootp pnode toptopprintf(“%c,”, root-data);+ +nodetop=p;top+;toptopp=p-lch;p p* *toptopp pa atoptopp pif (top0)top - -;p=no

47、detop;p=p-rch;p p- -p pb bp ptop - -; p=nodetop; p=p-rch;p pp pp pc cp pp pp p/ /top+;d d6 65 54 43 32 21 10 0p pp p6.3.3 遍歷的非遞歸算法遍歷的非遞歸算法64 BiTNode *GoFarLeft(BiTree T, Stack *S) if (!T ) return NULL; while (T-lch ) Push(S, T); T = T-lch; return T; d d b b e e a a * * - - / / c c + +p 中序遍歷的非遞歸算法中序遍

48、歷的非遞歸算法6.3.3 遍歷的非遞歸算法遍歷的非遞歸算法65 p 中序遍歷的非遞歸算法中序遍歷的非遞歸算法6.3.3 遍歷的非遞歸算法遍歷的非遞歸算法void Inorder_I(BiTree T, void (void Inorder_I(BiTree T, void (* *visit)visit) (TelemType& e) (TelemType& e) Stack Stack * *S;S; t = t = GoFarLeftGoFarLeft(T, S);(T, S); / / 找到最左下的結(jié)點(diǎn)找到最左下的結(jié)點(diǎn) while(t)while(t) visit(t-d

49、ata);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; / 棧空表明遍歷結(jié)束?？毡砻鞅闅v結(jié)束 / while / while/ Inorder_I / Inorder_I 66 6.4 遍歷的應(yīng)用遍歷的應(yīng)用 遍歷是二叉樹(shù)的基本操

50、作：二叉樹(shù)許多操遍歷是二叉樹(shù)的基本操作：二叉樹(shù)許多操作可在遍歷過(guò)程中完成，本節(jié)再舉幾個(gè)二叉樹(shù)作可在遍歷過(guò)程中完成，本節(jié)再舉幾個(gè)二叉樹(shù)遍歷應(yīng)用實(shí)例。遍歷應(yīng)用實(shí)例。67 6.4.1 遍歷的基本應(yīng)用遍歷的基本應(yīng)用 6.4.2 二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用 6.4.3 二叉樹(shù)的相似與等價(jià)二叉樹(shù)的相似與等價(jià)6.4 遍歷的應(yīng)用遍歷的應(yīng)用68 求二叉樹(shù)的葉子數(shù)。求二叉樹(shù)的葉子數(shù)。算法思想：采用任何遍歷方法，遍歷時(shí)判斷訪問(wèn)的結(jié)點(diǎn)是不是葉子，算法思想：采用任何遍歷方法，遍歷時(shí)判斷訪問(wèn)的結(jié)點(diǎn)是不是葉子，若是則葉子數(shù)加若是則葉子數(shù)加1 1。int countleaf(bitree t ,

51、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)用69 求二叉樹(shù)的深度求二叉樹(shù)的深度算法思想：從第一層的根結(jié)點(diǎn)開(kāi)始往下遞推可得算法思想：從第一層的根結(jié)點(diǎn)開(kāi)始往下遞推可得到。使用二叉樹(shù)的前序或后序遍歷的遞歸或非遞歸算法都可求得。下到。使用二叉樹(shù)的前序或后序遍歷的遞歸或非遞歸算法都可求得。下面給出后序遍歷求二叉樹(shù)深度的遞歸算法面給出后序遍歷求二叉樹(shù)深度的遞歸

52、算法：Int treedepth(bitree *t) int h,lh,rh; if(t=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)用70 6.4.1 遍歷的基本應(yīng)用遍歷的基本應(yīng)用 6.4.2 二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用 6.4.3 二叉樹(shù)的相似與等價(jià)二叉樹(shù)的相似與等價(jià)6.4. 遍歷的應(yīng)用遍歷的應(yīng)用71 問(wèn)題：?jiǎn)栴}：給定一個(gè)遍歷序列，能否唯一確定一棵二給定一個(gè)遍歷序列

53、，能否唯一確定一棵二叉樹(shù)？例如：先序序列為叉樹(shù)？例如：先序序列為ABCD,ABCD,其二叉樹(shù)的結(jié)構(gòu)是什么？其二叉樹(shù)的結(jié)構(gòu)是什么？答案是答案是不唯一不唯一6.4.2二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹(shù)的遍歷與存儲(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二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)之間的轉(zhuǎn)化二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)之間的轉(zhuǎn)化72 p構(gòu)造二叉樹(shù)構(gòu)造二叉樹(shù) 給定某兩種遍歷序列能否唯一確定一棵二叉樹(shù)？給定某兩種遍歷序列能否唯一確定一棵二叉樹(shù)？ 給定中序和后序給定中序和后序 給定中序和前序給定中序和前序 給定先序和后序給定先序和后序不能不能唯一確定

54、一棵二叉樹(shù)唯一確定一棵二叉樹(shù)唯一確定一棵二叉樹(shù)唯一確定一棵二叉樹(shù)唯一確定一棵二叉樹(shù)唯一確定一棵二叉樹(shù)關(guān)鍵關(guān)鍵（1 1）確定二叉樹(shù)的根結(jié)點(diǎn)；）確定二叉樹(shù)的根結(jié)點(diǎn)； （2 2）結(jié)點(diǎn)的左右次序。）結(jié)點(diǎn)的左右次序。6.4.2二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用73 給定二叉樹(shù)先序和中序遍歷序列，如何構(gòu)造二叉樹(shù)？給定二叉樹(shù)先序和中序遍歷序列，如何構(gòu)造二叉樹(shù)？ 先序：先序：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右右4

55、61前前3578中中3758246p構(gòu)造二叉樹(shù)構(gòu)造二叉樹(shù)6.4.2二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用74 后序遍歷序列：a,b,c,d,-,a,b,c,d,-,* *,+,e,f,/,-,+,e,f,/,-根據(jù)給定的遍歷次序構(gòu)造二叉樹(shù)根據(jù)給定的遍歷次序構(gòu)造二叉樹(shù)中序遍歷序列：中序遍歷序列：a,+,b,a,+,b,* *,c,-,d,-,e,/,f,c,-,d,-,e,/,f作業(yè)作業(yè)p構(gòu)造二叉樹(shù)構(gòu)造二叉樹(shù)6.4.2二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用75 e e d d c c b b f f a a + + * * / / - - - -先序先序:-,

56、+,a,:-,+,a,* *,b,-,c,d,b,-,c,d,/,e,f,/,e,fp構(gòu)造二叉樹(shù)構(gòu)造二叉樹(shù)6.4.2二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用76 結(jié)論：結(jié)論：p“遍歷遍歷”是二叉樹(shù)各種操作的基礎(chǔ)；是二叉樹(shù)各種操作的基礎(chǔ)；p可以在遍歷過(guò)程中對(duì)結(jié)點(diǎn)進(jìn)行各種操作，可以在遍歷過(guò)程中對(duì)結(jié)點(diǎn)進(jìn)行各種操作，對(duì)于一棵已知樹(shù)可求結(jié)點(diǎn)的雙親；對(duì)于一棵已知樹(shù)可求結(jié)點(diǎn)的雙親；求結(jié)點(diǎn)的孩子結(jié)點(diǎn)；求結(jié)點(diǎn)的孩子結(jié)點(diǎn)；判定結(jié)點(diǎn)所在層次；判定結(jié)點(diǎn)所在層次；樹(shù)的深度；樹(shù)的深度；生成二叉樹(shù)生成二叉樹(shù)6.3.26.3.2二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用 77 6.4 遍歷的應(yīng)用

57、遍歷的應(yīng)用 6.4.1 遍歷的基本應(yīng)用遍歷的基本應(yīng)用 6.4.2 二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用二叉樹(shù)的遍歷與存儲(chǔ)結(jié)構(gòu)的應(yīng)用 6.4.3 二叉樹(shù)的相似與等價(jià)二叉樹(shù)的相似與等價(jià)78 p二叉樹(shù)的相似與等價(jià)的含義二叉樹(shù)的相似與等價(jià)的含義兩株二叉樹(shù)具有兩株二叉樹(shù)具有相同結(jié)構(gòu)相同結(jié)構(gòu)指：指： （1）它們都是空的）它們都是空的 ； （2）它們都是非空的，且左右子樹(shù)分別具有相同結(jié)構(gòu)。）它們都是非空的，且左右子樹(shù)分別具有相同結(jié)構(gòu)。 “形狀形狀”相相同同6.4.3 二叉樹(shù)的相似與等價(jià)二叉樹(shù)的相似與等價(jià)79 p判斷兩株二叉樹(shù)是否等價(jià)判斷兩株二叉樹(shù)是否等價(jià)int EQUAL( t1 , t2 )BTREE t1 ,

58、t2 ; int x ; x = 0 ; if ( ISEMPTY(t1) & ISEMPTY(t2) ) x = 1 ; else if ( !ISEMPTY( t1 ) & ! ISEMPTY( t2) ) if ( DATA( t1 ) = DATA( t2 ) ) if ( EQUAL( LCHILD( t1 ) , LCHILD( t2 ) ) ) x= EQUAL( RCHILD( t1) , RCHILD( t2) ) return( x ) ; /* EQUAL */6.4.3 二叉樹(shù)的相似與等價(jià)二叉樹(shù)的相似與等價(jià)80 p二叉樹(shù)的復(fù)制二叉樹(shù)的復(fù)制BTREE CO

59、PY( BTREE oldtree ) BTREE temp ; if ( oldtree != NULL ) temp = new Node ; temp - lch = COPY( oldtree-lch ) ; temp - rch = COPY( oldtree-rch ) ; temp - data = oldtree-data ; return ( temp ); return ( NULL ) ; 6.4.3 二叉樹(shù)的相似與等價(jià)二叉樹(shù)的相似與等價(jià)81 6.5 線索二叉樹(shù)線索二叉樹(shù) 6.5.1 線索二叉樹(shù)的表示線索二叉樹(shù)的表示 6.5.2 二叉樹(shù)的線索化二叉樹(shù)的線索化 6.5.3

60、線索二叉樹(shù)的遍歷線索二叉樹(shù)的遍歷82 6.5.1 線索二叉樹(shù)的表示線索二叉樹(shù)的表示 6.5.2 二叉樹(shù)的線索化二叉樹(shù)的線索化 6.5.3 線索二叉樹(shù)的遍歷線索二叉樹(shù)的遍歷6.5 線索二叉樹(shù)線索二叉樹(shù)83 6.5 線索二叉樹(shù)線索二叉樹(shù)二叉鏈表是一種單向鏈接結(jié)構(gòu)二叉鏈表是一種單向鏈接結(jié)構(gòu)，從一個(gè)結(jié)點(diǎn)出發(fā)，沿著指，從一個(gè)結(jié)點(diǎn)出發(fā)，沿著指針走向只能到達(dá)其子孫結(jié)點(diǎn)，卻無(wú)法返回其祖先結(jié)點(diǎn)。針走向只能到達(dá)其子孫結(jié)點(diǎn)，卻無(wú)法返回其祖先結(jié)點(diǎn)。正像線性鏈表可以從單向鏈表發(fā)展到雙向鏈表一樣，正像線性鏈表可以從單向鏈表發(fā)展到雙向鏈表一樣，二叉二叉鏈表也可以采用雙向鏈表鏈表也可以采用雙向鏈表。遍歷二叉樹(shù)遍歷二叉樹(shù)就是按一定的規(guī)則將二叉樹(shù)中的結(jié)點(diǎn)排列成一就是按一定的規(guī)則將二叉樹(shù)中的結(jié)點(diǎn)排列成一個(gè)線性序列，即個(gè)線性