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

1、第六章第六章 樹與森林樹與森林學(xué)習(xí)要點(diǎn)：學(xué)習(xí)要點(diǎn)：樹的遞歸定義和森林的基本概念。樹的遞歸定義和森林的基本概念。樹與森林的存儲(chǔ)結(jié)構(gòu)。樹與森林的存儲(chǔ)結(jié)構(gòu)。樹與森林的遍歷算法樹與森林的遍歷算法樹、森林與二叉樹的相互轉(zhuǎn)換。樹、森林與二叉樹的相互轉(zhuǎn)換。26.1 樹及其相關(guān)概念樹及其相關(guān)概念6.1.1 樹的基本概念樹的基本概念1、樹的基本概念、樹的基本概念3樹（樹（Tree）是一個(gè)由是一個(gè)由n（n0）個(gè)結(jié)點(diǎn)構(gòu)成的有限集合）個(gè)結(jié)點(diǎn)構(gòu)成的有限集合T。 當(dāng)當(dāng)n=0時(shí)，稱時(shí)，稱T為為“空樹空樹”。 當(dāng)當(dāng)n0時(shí)，時(shí)，T中諸元素滿足下述條件：中諸元素滿足下述條件： 有且僅有一個(gè)特定數(shù)據(jù)元素沒有前驅(qū)，稱其為有且僅有一個(gè)

2、特定數(shù)據(jù)元素沒有前驅(qū)，稱其為T的的根結(jié)點(diǎn)根結(jié)點(diǎn)。 除根結(jié)點(diǎn)外其余數(shù)據(jù)元素，又可分為除根結(jié)點(diǎn)外其余數(shù)據(jù)元素，又可分為m（0mn）個(gè)互不相交）個(gè)互不相交的有限集合：的有限集合：T1，T2，Tm，每一個(gè)集合，每一個(gè)集合Ti（0im）又是一）又是一棵樹，稱為根的棵樹，稱為根的子樹子樹。6.1.1 樹的基本概念樹的基本概念1、樹的基本概念、樹的基本概念2樹的特性：樹的特性：4 空樹是樹的一個(gè)特例；空樹是樹的一個(gè)特例；一棵非空樹，至少有一個(gè)根結(jié)點(diǎn)，只有根結(jié)點(diǎn)的樹為最小樹；一棵非空樹，至少有一個(gè)根結(jié)點(diǎn)，只有根結(jié)點(diǎn)的樹為最小樹；在有多個(gè)結(jié)點(diǎn)的樹里，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)分屬若干個(gè)子樹，各子在有多個(gè)結(jié)點(diǎn)的樹里，除

3、根結(jié)點(diǎn)外，其余結(jié)點(diǎn)分屬若干個(gè)子樹，各子樹間互不相交；樹間互不相交；除根結(jié)點(diǎn)外，樹中其他結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)，但可以有零個(gè)或除根結(jié)點(diǎn)外，樹中其他結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)，但可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。多個(gè)后繼結(jié)點(diǎn)。6.1.1 樹的基本概念樹的基本概念1、樹的基本概念、樹的基本概念3有序樹有序樹與與無序樹無序樹 如果樹如果樹T中各子樹從左至右按照一定此序排列，不中各子樹從左至右按照一定此序排列，不得互換，則稱得互換，則稱T是有序樹（是有序樹（order tree），否則為無序樹（），否則為無序樹（unorder tree）。由此可知，二叉樹是一種特殊的有序樹，但不是一般樹的特）。由此可知，二叉樹

4、是一種特殊的有序樹，但不是一般樹的特例。例。森林森林 n（n0）棵互不相交的樹的集合，稱為森林（）棵互不相交的樹的集合，稱為森林（forest）。）。5 6.1.1 樹的基本概念樹的基本概念22、樹的表示方法、樹的表示方法 樹形表示法樹形表示法6 文氏圖表示法文氏圖表示法 凹入表示法凹入表示法 括弧表示法括弧表示法 （A（B（D）（）（E（I）（）（J）（）（F）（）（C（G）（）（H） 6.1.2 結(jié)點(diǎn)及其基本概念結(jié)點(diǎn)及其基本概念1、結(jié)點(diǎn)、結(jié)點(diǎn) 結(jié)點(diǎn)的結(jié)點(diǎn)的度度：結(jié)點(diǎn)擁有的子樹數(shù)目，即該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的個(gè)數(shù)結(jié)點(diǎn)擁有的子樹數(shù)目，即該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的個(gè)數(shù) 結(jié)點(diǎn)的結(jié)點(diǎn)的深度深度（層次層次）：結(jié)點(diǎn)位

5、于樹的層次數(shù)：結(jié)點(diǎn)位于樹的層次數(shù) 樹的度樹的度：一棵樹中各結(jié)點(diǎn)度的最大值：一棵樹中各結(jié)點(diǎn)度的最大值 樹的深度樹的深度：一棵樹中各結(jié)點(diǎn)深度的最大值：一棵樹中各結(jié)點(diǎn)深度的最大值 結(jié)點(diǎn)間結(jié)點(diǎn)間路徑路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支 路徑長(zhǎng)度路徑長(zhǎng)度：一條路徑上邊即連接兩個(gè)結(jié)點(diǎn)的線段的個(gè)數(shù)稱為該：一條路徑上邊即連接兩個(gè)結(jié)點(diǎn)的線段的個(gè)數(shù)稱為該路徑的長(zhǎng)度路徑的長(zhǎng)度 76.1.2 結(jié)點(diǎn)及其基本概念結(jié)點(diǎn)及其基本概念282、結(jié)點(diǎn)分類、結(jié)點(diǎn)分類（1 1）根結(jié)點(diǎn)）根結(jié)點(diǎn)：樹樹T中沒有前驅(qū)的結(jié)點(diǎn)稱為中沒有前驅(qū)的結(jié)點(diǎn)稱為T的根結(jié)點(diǎn)的根結(jié)點(diǎn) 葉結(jié)點(diǎn)葉結(jié)點(diǎn)：樹樹T中沒有后繼的點(diǎn)

6、稱為中沒有后繼的點(diǎn)稱為T的葉結(jié)點(diǎn)的葉結(jié)點(diǎn) 內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)：樹樹T中既有前驅(qū)又有后繼的結(jié)點(diǎn)稱為中既有前驅(qū)又有后繼的結(jié)點(diǎn)稱為T的內(nèi)部結(jié)點(diǎn)的內(nèi)部結(jié)點(diǎn) （2 2）分支結(jié)點(diǎn)）分支結(jié)點(diǎn)：樹樹T中度數(shù)不等于中度數(shù)不等于0的結(jié)點(diǎn)為的結(jié)點(diǎn)為T的分支結(jié)點(diǎn)的分支結(jié)點(diǎn) 非分支結(jié)點(diǎn)非分支結(jié)點(diǎn)：樹樹T中度數(shù)等于中度數(shù)等于0的結(jié)點(diǎn)稱為的結(jié)點(diǎn)稱為T的非分支結(jié)點(diǎn)的非分支結(jié)點(diǎn) 6.1.2 結(jié)點(diǎn)及其基本概念結(jié)點(diǎn)及其基本概念393、結(jié)點(diǎn)間關(guān)系描述、結(jié)點(diǎn)間關(guān)系描述 子結(jié)點(diǎn)子結(jié)點(diǎn)：樹樹T中一個(gè)結(jié)點(diǎn)中一個(gè)結(jié)點(diǎn)N的所有直接后繼，都被稱作是該結(jié)點(diǎn)的所有直接后繼，都被稱作是該結(jié)點(diǎn)N的子結(jié)點(diǎn)的子結(jié)點(diǎn) 父結(jié)點(diǎn)父結(jié)點(diǎn)：樹：樹T中把一個(gè)結(jié)點(diǎn)稱作是它所

7、有后繼結(jié)點(diǎn)的父結(jié)點(diǎn)中把一個(gè)結(jié)點(diǎn)稱作是它所有后繼結(jié)點(diǎn)的父結(jié)點(diǎn) 兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)：在樹：在樹T中，具有相同雙親的結(jié)點(diǎn)，互稱為是兄弟結(jié)點(diǎn)中，具有相同雙親的結(jié)點(diǎn)，互稱為是兄弟結(jié)點(diǎn) 堂兄弟結(jié)點(diǎn)堂兄弟結(jié)點(diǎn)：在樹：在樹T中，雙親在同一層的那些結(jié)點(diǎn)，互稱為是堂兄中，雙親在同一層的那些結(jié)點(diǎn)，互稱為是堂兄弟結(jié)點(diǎn)弟結(jié)點(diǎn) 子孫結(jié)點(diǎn)子孫結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的子樹中的所有結(jié)點(diǎn)，都被稱作是該結(jié)點(diǎn)的：一個(gè)結(jié)點(diǎn)的子樹中的所有結(jié)點(diǎn)，都被稱作是該結(jié)點(diǎn)的子孫結(jié)點(diǎn)子孫結(jié)點(diǎn) 祖先結(jié)點(diǎn)祖先結(jié)點(diǎn)：從根結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)的路徑上的所有分支結(jié)點(diǎn)，稱為：從根結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)的路徑上的所有分支結(jié)點(diǎn)，稱為該結(jié)點(diǎn)的祖先結(jié)點(diǎn)該結(jié)點(diǎn)的祖先結(jié)點(diǎn) 6.2 樹的存儲(chǔ)結(jié)構(gòu)樹的

8、存儲(chǔ)結(jié)構(gòu)6.2.1 父結(jié)點(diǎn)表示法存儲(chǔ)父結(jié)點(diǎn)表示法存儲(chǔ) 將樹中結(jié)點(diǎn)按照將樹中結(jié)點(diǎn)按照“由上到下由上到下”和和“由左到右由左到右”的順序做成一的順序做成一個(gè)結(jié)點(diǎn)序列，將該序列存放在一維數(shù)組個(gè)結(jié)點(diǎn)序列，將該序列存放在一維數(shù)組Tr當(dāng)中。當(dāng)中。Tr中每個(gè)元素中每個(gè)元素（結(jié)點(diǎn)）都有一個(gè)（結(jié)點(diǎn)）都有一個(gè)Data域域和一個(gè)和一個(gè)Parent域域，其中，其中Data域存放結(jié)域存放結(jié)點(diǎn)數(shù)據(jù)，而點(diǎn)數(shù)據(jù)，而Parent域存放結(jié)點(diǎn)的父結(jié)點(diǎn)在數(shù)組中下標(biāo)。域存放結(jié)點(diǎn)的父結(jié)點(diǎn)在數(shù)組中下標(biāo)。10 下標(biāo)下標(biāo) 0 1 2 3 4 5 6 7 8 9 10 Data A B C D E F G H I J K Parent -1 0

9、 0 0 1 1 3 3 6 6 6 root 6.2.2 子結(jié)點(diǎn)表示法存儲(chǔ)子結(jié)點(diǎn)表示法存儲(chǔ) 考慮通過設(shè)立結(jié)點(diǎn)的考慮通過設(shè)立結(jié)點(diǎn)的Children域來存儲(chǔ)樹結(jié)構(gòu)信息。域來存儲(chǔ)樹結(jié)構(gòu)信息。當(dāng)使用鏈?zhǔn)浇Y(jié)構(gòu)來實(shí)現(xiàn)樹存儲(chǔ)時(shí)，就需要將每個(gè)結(jié)點(diǎn)的孩當(dāng)使用鏈?zhǔn)浇Y(jié)構(gòu)來實(shí)現(xiàn)樹存儲(chǔ)時(shí)，就需要將每個(gè)結(jié)點(diǎn)的孩子信息都存放在存儲(chǔ)結(jié)點(diǎn)中。此時(shí)存儲(chǔ)結(jié)點(diǎn)除建立子信息都存放在存儲(chǔ)結(jié)點(diǎn)中。此時(shí)存儲(chǔ)結(jié)點(diǎn)除建立Data域域外，還需按照樹的度外，還需按照樹的度m對(duì)每個(gè)結(jié)點(diǎn)構(gòu)建對(duì)每個(gè)結(jié)點(diǎn)構(gòu)建m個(gè)指針域個(gè)指針域。 11 Data ChP1 數(shù)據(jù)域數(shù)據(jù)域 指向指向第第 1 個(gè)個(gè) 孩子孩子 ChP2 指向第指向第 2 個(gè)個(gè) 孩子孩子 ChPm

10、 指向第指向第 m個(gè)個(gè) 孩子孩子 這種子結(jié)點(diǎn)鏈?zhǔn)酱鎯?chǔ)效率低下，通常不這種子結(jié)點(diǎn)鏈?zhǔn)酱鎯?chǔ)效率低下，通常不直接采用上述方法。直接采用上述方法。6.2.2 子結(jié)點(diǎn)表示法存儲(chǔ)子結(jié)點(diǎn)表示法存儲(chǔ)1、子結(jié)點(diǎn)鏈表存儲(chǔ)法、子結(jié)點(diǎn)鏈表存儲(chǔ)法12 將樹將樹T中結(jié)點(diǎn)按照層序進(jìn)行排序。中結(jié)點(diǎn)按照層序進(jìn)行排序。 為樹為樹T中每個(gè)結(jié)點(diǎn)都設(shè)置一個(gè)單鏈表，該鏈表由該結(jié)點(diǎn)的所有子結(jié)點(diǎn)按照層序中每個(gè)結(jié)點(diǎn)都設(shè)置一個(gè)單鏈表，該鏈表由該結(jié)點(diǎn)的所有子結(jié)點(diǎn)按照層序進(jìn)行鏈接。這樣的鏈表也稱為進(jìn)行鏈接。這樣的鏈表也稱為子結(jié)點(diǎn)鏈表子結(jié)點(diǎn)鏈表。 將每個(gè)結(jié)點(diǎn)子結(jié)點(diǎn)鏈表的表頭指針按照樹將每個(gè)結(jié)點(diǎn)子結(jié)點(diǎn)鏈表的表頭指針按照樹T結(jié)點(diǎn)的層序集中起來組成數(shù)組結(jié)點(diǎn)

11、的層序集中起來組成數(shù)組Tr。 下標(biāo)下標(biāo) Data FChild 0 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K 數(shù)組數(shù)組 Tr Chn Next 1 2 3 4 5 6 7 8 9 10 （b） root 6.2.2 子結(jié)點(diǎn)表示法存儲(chǔ)子結(jié)點(diǎn)表示法存儲(chǔ)22、子結(jié)點(diǎn)順序表存儲(chǔ)法、子結(jié)點(diǎn)順序表存儲(chǔ)法13 將樹將樹T的結(jié)點(diǎn)按照層序進(jìn)行排序，組成數(shù)組的結(jié)點(diǎn)按照層序進(jìn)行排序，組成數(shù)組Tr。 對(duì)對(duì)Tr中每個(gè)數(shù)組元素開辟中每個(gè)數(shù)組元素開辟Data域域和和m個(gè)子結(jié)點(diǎn)域個(gè)子結(jié)點(diǎn)域：Child1，Child2，Childm，這些子結(jié)點(diǎn)域分別記錄每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)信息。，這些子

12、結(jié)點(diǎn)域分別記錄每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)信息。 將數(shù)組將數(shù)組Tr進(jìn)行存儲(chǔ)。進(jìn)行存儲(chǔ)。 root 下標(biāo)下標(biāo) Data Chr1 Chr2 Chr3 0 A 1 2 3 1 B 4 5 -1 2 C -1 -1 -1 3 D 6 7 -1 4 E -1 -1 -1 5 F -1 -1 -1 6 G 8 9 10 7 H -1 -1 -1 8 I -1 -1 -1 9 J -1 -1 -1 10 K -1 -1 -1 6.2.3 左子左子/右兄弟結(jié)點(diǎn)表示法存儲(chǔ)右兄弟結(jié)點(diǎn)表示法存儲(chǔ)結(jié)點(diǎn)由結(jié)點(diǎn)由Data域域（存放數(shù)據(jù)信息）、（存放數(shù)據(jù)信息）、Lch域域（存放該結(jié)點(diǎn)第（存放該結(jié)點(diǎn)第一個(gè)子結(jié)點(diǎn)即左子結(jié)點(diǎn)信息）和一個(gè)子

13、結(jié)點(diǎn)即左子結(jié)點(diǎn)信息）和RS域域（存放該結(jié)點(diǎn)第一個(gè)兄（存放該結(jié)點(diǎn)第一個(gè)兄弟結(jié)點(diǎn)即右兄弟結(jié)點(diǎn)信息）組成。弟結(jié)點(diǎn)即右兄弟結(jié)點(diǎn)信息）組成。14 （a） Data LCH 數(shù)據(jù)域數(shù)據(jù)域 第一個(gè)孩第一個(gè)孩子子下標(biāo)下標(biāo) RS 下一個(gè)兄下一個(gè)兄弟下標(biāo)弟下標(biāo) 6.2.3 左子左子/右兄弟結(jié)點(diǎn)表示法存儲(chǔ)右兄弟結(jié)點(diǎn)表示法存儲(chǔ)2可以分別按照可以分別按照順序順序或或鏈表鏈表方式進(jìn)行進(jìn)行存儲(chǔ)。方式進(jìn)行進(jìn)行存儲(chǔ)。 15 下標(biāo)下標(biāo) Data Lch RS 0 A 1 -1 1 B 4 2 2 C -1 3 3 D 6 -1 4 E -1 5 5 F -1 -1 6 G 8 7 7 H -1 -1 8 I -1 9 9 J -

14、1 10 10 K -1 -1 （b） 6.3 樹的遍歷樹的遍歷6.3.1 層次遍歷層次遍歷1、層次遍歷概念、層次遍歷概念16兩個(gè)步驟：兩個(gè)步驟： 按照樹的按照樹的“層層”的順序進(jìn)行訪問，即的順序進(jìn)行訪問，即“從上到下從上到下”。 訪問到達(dá)每一層后，再依次訪問該層的每個(gè)結(jié)點(diǎn)，即訪問到達(dá)每一層后，再依次訪問該層的每個(gè)結(jié)點(diǎn)，即“從左到右從左到右”。兩個(gè)基本點(diǎn)：兩個(gè)基本點(diǎn)： 采用子結(jié)點(diǎn)表示法的存儲(chǔ)結(jié)構(gòu)記錄樹中結(jié)點(diǎn)。采用子結(jié)點(diǎn)表示法的存儲(chǔ)結(jié)構(gòu)記錄樹中結(jié)點(diǎn)。 基于隊(duì)列的結(jié)點(diǎn)存儲(chǔ)基于隊(duì)列的結(jié)點(diǎn)存儲(chǔ) 當(dāng)進(jìn)入一個(gè)結(jié)點(diǎn)后，需要將該結(jié)點(diǎn)所有子結(jié)點(diǎn)當(dāng)進(jìn)入一個(gè)結(jié)點(diǎn)后，需要將該結(jié)點(diǎn)所有子結(jié)點(diǎn)信息記錄下來以便必要時(shí)能夠使

15、用。由于先達(dá)到結(jié)點(diǎn)的子結(jié)點(diǎn)，將來會(huì)得信息記錄下來以便必要時(shí)能夠使用。由于先達(dá)到結(jié)點(diǎn)的子結(jié)點(diǎn)，將來會(huì)得到首先訪問，所以需要采用隊(duì)列方式記錄結(jié)點(diǎn)的子結(jié)點(diǎn)信息以保證它們能到首先訪問，所以需要采用隊(duì)列方式記錄結(jié)點(diǎn)的子結(jié)點(diǎn)信息以保證它們能夠依照進(jìn)入隊(duì)列的先后順序得到訪問。夠依照進(jìn)入隊(duì)列的先后順序得到訪問。例子：例子：以以層次層次遍歷方式訪問如圖所示的二叉樹。遍歷方式訪問如圖所示的二叉樹。17解：解： A-B-C-D-E-F-G-H-I-J-K6.3.1 層次遍歷層次遍歷22、層次遍歷算法、層次遍歷算法18步驟步驟 當(dāng)前出隊(duì)結(jié)點(diǎn)當(dāng)前出隊(duì)結(jié)點(diǎn) 當(dāng)前訪問結(jié)點(diǎn)當(dāng)前訪問結(jié)點(diǎn) 當(dāng)前進(jìn)隊(duì)結(jié)點(diǎn)當(dāng)前進(jìn)隊(duì)結(jié)點(diǎn) 當(dāng)前隊(duì)列內(nèi)容

16、當(dāng)前隊(duì)列內(nèi)容 初始初始 A A A A 1 1 A A A A B B，C C，D D B B，C C，D D 2 2 B B B B E E，F(xiàn) F，G G C C，D D，E E，F(xiàn) F，G G 3 3 C C C C H H D D，E E，F(xiàn) F，G G，H H 4 D D I，J E，F(xiàn)，G，H，I，J 5 E E F，G，H，I，J 6 F F K G，H，I，J，K 7 G G H，I，J，K 8 H H I，J，K 9 I I J，K 10 J J K 11 K K 空空 2、層次遍歷算法、層次遍歷算法2算法算法6-1 樹的層次遍歷算法樹的層次遍歷算法1900 Level_Tr

17、(treenode tr, int m,int root)01 02 Queue Qs; int k;03 Qs.front=0; /* 隊(duì)首、隊(duì)尾指針初始化隊(duì)首、隊(duì)尾指針初始化 */04 Qs.rear=0;05 Qs.dataQs.rear = root; /* 讓根結(jié)點(diǎn)下標(biāo)進(jìn)隊(duì)列讓根結(jié)點(diǎn)下標(biāo)進(jìn)隊(duì)列 */06 Qs.rear + ; 已知一棵樹已知一棵樹T的度為的度為m，采用基于順序表的子結(jié)點(diǎn)表示法存儲(chǔ)。對(duì)，采用基于順序表的子結(jié)點(diǎn)表示法存儲(chǔ)。對(duì)T進(jìn)行層次進(jìn)行層次遍歷以獲得層次遍歷序列。遍歷以獲得層次遍歷序列。2、層次遍歷算法、層次遍歷算法2算法算法6-1 樹的層次遍歷算法樹的層次遍歷算法2

18、007 while (Qs.front != Qs.rear) /* 隊(duì)列非空隊(duì)列非空 */0809 k = QsQs.front ; /* 取隊(duì)首元素賦值給取隊(duì)首元素賦值給k */10 Qs.front+ ; /* 隊(duì)首元素出隊(duì)隊(duì)首元素出隊(duì) */11 printf (%c,trk.Data); /* 訪問該結(jié)點(diǎn)訪問該結(jié)點(diǎn) */12 for (i=1; i=m; i+) /* 讓該結(jié)點(diǎn)的孩子結(jié)點(diǎn)進(jìn)隊(duì)列讓該結(jié)點(diǎn)的孩子結(jié)點(diǎn)進(jìn)隊(duì)列 */13 if (trk.Childi != NULL)14 15 QsQs.rear = trk.Childi;16 Qs.rear + ;17 1819 6.3.2

19、先序遍歷先序遍歷過程：過程：（1）若）若T為空，遍歷結(jié)束；為空，遍歷結(jié)束；（2）若）若T非空，先訪問非空，先訪問T根結(jié)點(diǎn)，然后從左到右依次先序遍歷訪問根結(jié)點(diǎn)根結(jié)點(diǎn)，然后從左到右依次先序遍歷訪問根結(jié)點(diǎn)的每棵子樹。的每棵子樹。21例子：例子：以以先序先序遍歷方式訪問如圖所示的二叉樹。遍歷方式訪問如圖所示的二叉樹。解：解： A-B-E-F-K-G-C-H-D-I-J6.3.2 先序遍歷先序遍歷2算法算法6-2 樹的先序遍歷遞歸算法樹的先序遍歷遞歸算法已知樹已知樹T的度為的度為m，采用基于順序表的子結(jié)點(diǎn)表示法存儲(chǔ)，在此基礎(chǔ)上先序遍歷，采用基于順序表的子結(jié)點(diǎn)表示法存儲(chǔ)，在此基礎(chǔ)上先序遍歷，輸出先序遍歷序

20、列。，輸出先序遍歷序列。2200 Pre_Tr (treenode tr, int m,int root)01 02 int k;03 k = root;04 if (k!= NULL)05 06printf (%c, trk.Data); /* 訪問結(jié)點(diǎn)訪問結(jié)點(diǎn) */07for (i=1; i=m; i+) /* 依次先序遍歷結(jié)點(diǎn)的各子樹依次先序遍歷結(jié)點(diǎn)的各子樹 */08 Pre_Tr (tr,m,i);09 10 6.3.3 后序遍歷后序遍歷過程：過程：（1）若）若T為空，則遍歷結(jié)束；為空，則遍歷結(jié)束；（2）若）若T非空，則從左到右依次后序遍歷根結(jié)點(diǎn)的各子樹，然后訪問非空，則從左到右依次后

21、序遍歷根結(jié)點(diǎn)的各子樹，然后訪問根結(jié)點(diǎn)。根結(jié)點(diǎn)。23例子：例子：以以后序后序遍歷方式訪問如圖所示的二叉樹。遍歷方式訪問如圖所示的二叉樹。解：解： E-K-F-G-B-H-C-I-J-D-A6.3.3 后序遍歷后序遍歷2算法算法6-3 樹的后序遍歷遞歸算法樹的后序遍歷遞歸算法已知樹已知樹T的度為的度為m，采用基于順序表的子結(jié)點(diǎn)表示法存儲(chǔ)，在此基礎(chǔ)上實(shí)施后序，采用基于順序表的子結(jié)點(diǎn)表示法存儲(chǔ)，在此基礎(chǔ)上實(shí)施后序遍歷，輸出結(jié)果。遍歷，輸出結(jié)果。2400 Post_Tr(treenode tr, int m,int root)01 02 int k;03 k = root;04 if (k != NUL

22、L)0506 for (i=1; i=m; i+) /* 依次后序遍歷結(jié)點(diǎn)的各子樹依次后序遍歷結(jié)點(diǎn)的各子樹 */07 Post_Tr(tr,m,i);08 printf (%c, trk.Data); /* 訪問結(jié)點(diǎn)訪問結(jié)點(diǎn) */0910 6.4 森林森林森林森林：若干棵樹組成的集合：若干棵樹組成的集合1、森林的先序遍歷、森林的先序遍歷若森林為空，遍歷結(jié)束；若森林為空，遍歷結(jié)束；若森林非空，從左往右依次先序遍歷森林中的每棵樹，對(duì)結(jié)點(diǎn)的若森林非空，從左往右依次先序遍歷森林中的每棵樹，對(duì)結(jié)點(diǎn)的訪問順序，即是對(duì)森林先序遍歷的結(jié)點(diǎn)序列。訪問順序，即是對(duì)森林先序遍歷的結(jié)點(diǎn)序列。25例子：例子：以以先序先

23、序遍歷方式訪問如圖所示的遍歷方式訪問如圖所示的森林森林。解：解： E-K-F-G-B-H-C-I-J-D-A6.4 森林森林21、森林的后序遍歷、森林的后序遍歷若森林為空，則遍歷結(jié)束；若森林為空，則遍歷結(jié)束；若森林非空，則從左往右依次后序遍歷森林中的每棵樹，對(duì)結(jié)點(diǎn)若森林非空，則從左往右依次后序遍歷森林中的每棵樹，對(duì)結(jié)點(diǎn)的訪問順序，即是對(duì)森林后序遍歷的結(jié)點(diǎn)序列。的訪問順序，即是對(duì)森林后序遍歷的結(jié)點(diǎn)序列。26例子：例子：以以后序后序遍歷方式訪問如圖所示的遍歷方式訪問如圖所示的森林森林。解：解： B-A-E-F-G-D-C-I-K-L-M-J-H6.5 樹與二叉樹的轉(zhuǎn)換樹與二叉樹的轉(zhuǎn)換6.5.1 樹

24、轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹27 確定根結(jié)點(diǎn)。原樹的根結(jié)點(diǎn)即為轉(zhuǎn)換后二叉樹的根結(jié)點(diǎn)。確定根結(jié)點(diǎn)。原樹的根結(jié)點(diǎn)即為轉(zhuǎn)換后二叉樹的根結(jié)點(diǎn)。 處理根結(jié)點(diǎn)。這里涉及根結(jié)點(diǎn)的左孩子及其左孩子的所有處理根結(jié)點(diǎn)。這里涉及根結(jié)點(diǎn)的左孩子及其左孩子的所有右子孫。將樹中根結(jié)點(diǎn)的第一個(gè)孩子轉(zhuǎn)換為二叉樹根結(jié)點(diǎn)的左孩右子孫。將樹中根結(jié)點(diǎn)的第一個(gè)孩子轉(zhuǎn)換為二叉樹根結(jié)點(diǎn)的左孩子，該左孩子在樹中的所有兄弟依次轉(zhuǎn)換為二叉樹中該結(jié)點(diǎn)的右子，該左孩子在樹中的所有兄弟依次轉(zhuǎn)換為二叉樹中該結(jié)點(diǎn)的右孩子及右子孫。孩子及右子孫。 對(duì)新畫的每個(gè)結(jié)點(diǎn)依次處理。處理方法如同步驟對(duì)新畫的每個(gè)結(jié)點(diǎn)依次處理。處理方法如同步驟2，將樹，將樹中對(duì)應(yīng)結(jié)點(diǎn)的第

25、一個(gè)孩子轉(zhuǎn)換為該結(jié)點(diǎn)的左孩子，該左孩子在樹中對(duì)應(yīng)結(jié)點(diǎn)的第一個(gè)孩子轉(zhuǎn)換為該結(jié)點(diǎn)的左孩子，該左孩子在樹中的所有兄弟依次轉(zhuǎn)換為二叉樹中該結(jié)點(diǎn)的右孩子及右子孫。中的所有兄弟依次轉(zhuǎn)換為二叉樹中該結(jié)點(diǎn)的右孩子及右子孫。 反復(fù)執(zhí)行步驟反復(fù)執(zhí)行步驟3，直到所有結(jié)點(diǎn)均處理完畢。，直到所有結(jié)點(diǎn)均處理完畢。6.5.1 樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹2一個(gè)樹轉(zhuǎn)換為二叉樹的例子：一個(gè)樹轉(zhuǎn)換為二叉樹的例子：28轉(zhuǎn)轉(zhuǎn)換換6.5.1 樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹3由樹轉(zhuǎn)換過來的二叉樹特點(diǎn)：由樹轉(zhuǎn)換過來的二叉樹特點(diǎn)：二叉樹根結(jié)點(diǎn)無右孩子，只有左子樹。二叉樹根結(jié)點(diǎn)無右孩子，只有左子樹。除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)的左孩子為原樹結(jié)構(gòu)結(jié)點(diǎn)的第一個(gè)孩除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)的左孩子為原樹結(jié)構(gòu)結(jié)點(diǎn)的第一