數(shù)據(jù)結(jié)構(gòu)張華娣師樹(shù)與二叉樹(shù)PPT課件

1、 6.4.3樹(shù)和森林的遍歷 6.5 赫夫曼樹(shù)及其應(yīng)用 6.5.1 最優(yōu)二叉樹(shù)（赫夫曼樹(shù)） 6.5.2 赫夫曼編碼學(xué)習(xí)綱要第1頁(yè)/共147頁(yè)ACGBDE FK LHMIJ 非線性結(jié)構(gòu) 該結(jié)構(gòu)中至少存在一個(gè)數(shù)據(jù)元素，有兩個(gè)或兩個(gè)以上的直接前驅(qū)或直接后繼.如： 樹(shù)型結(jié)構(gòu)、圖型結(jié)構(gòu) 樹(shù)型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。 是結(jié)點(diǎn)之間有分支，并且具有層次關(guān)系的結(jié)構(gòu)。（直觀來(lái)看） 樹(shù)型結(jié)構(gòu)的邏輯特征 樹(shù)中任一結(jié)點(diǎn)都可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)，但至多只能有一個(gè)前趨結(jié)點(diǎn)，只有根結(jié)點(diǎn)無(wú)前趨，葉子結(jié)點(diǎn)無(wú)后繼。 最為常用的樹(shù)型結(jié)構(gòu) 樹(shù) 二叉樹(shù)6.1 樹(shù)的定義和基本術(shù)語(yǔ)第2頁(yè)/共147頁(yè)6.1 樹(shù)的基本概念及相關(guān)術(shù)語(yǔ) 一、樹(shù)

2、的定義 定義：樹(shù)(Tree)是n(n=0)個(gè)結(jié)點(diǎn)的有限集T，n=0時(shí)稱為空樹(shù)，否則對(duì)任意一棵非空樹(shù)，它滿足如下兩個(gè)條件：6.1 樹(shù)的定義和基本術(shù)語(yǔ)ACGBDE FKLHMIJ（1）有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)； (2)其余的結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的子集T1,T2,T3Tm，其中每個(gè)子集又是一棵樹(shù)，并稱其為根的子樹(shù)(Subtree)。樹(shù)的定義是采用遞歸方法第3頁(yè)/共147頁(yè)6.1 樹(shù)的定義和基本術(shù)語(yǔ)(a) 一棵樹(shù)結(jié)構(gòu) (b)一個(gè)非樹(shù)結(jié)構(gòu) (c)一個(gè)非樹(shù)結(jié)構(gòu) 一、樹(shù)的定義ACBGFEDHIACBGFDACBGFDE第4頁(yè)/共147頁(yè)6.1 樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)的應(yīng)用舉例文件結(jié)

3、構(gòu)My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic第5頁(yè)/共147頁(yè)6.1 樹(shù)的定義和基本術(shù)語(yǔ)ACGBDEFKLHMIJ二、樹(shù)的特點(diǎn)第6頁(yè)/共147頁(yè)6.1 樹(shù)的定義和基本術(shù)語(yǔ)三、樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)。樹(shù)的度：樹(shù)中各結(jié)點(diǎn)度的最大值。CGBDEFKLHMIJA第7頁(yè)/共147頁(yè)6.1 樹(shù)的定義和基本術(shù)語(yǔ)三、樹(shù)的基本術(shù)語(yǔ)葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。CGBDEFKLHMIJA第8頁(yè)/共147頁(yè)6.1 樹(shù)的定義和基本術(shù)語(yǔ)三、

4、樹(shù)的基本術(shù)語(yǔ)孩子、雙親：樹(shù)中某結(jié)點(diǎn)子樹(shù)的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；兄弟：具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。 CGBDEFKLHMIJA第9頁(yè)/共147頁(yè)6.1 樹(shù)的定義和基本術(shù)語(yǔ)三、樹(shù)的基本術(shù)語(yǔ)路徑：如果樹(shù)的結(jié)點(diǎn)序列n1, n2, , nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的雙親（1=i=0)個(gè)結(jié)點(diǎn)的有限集合，此集合或者為空集（n=0），或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹(shù)組成，并且左右子樹(shù)都是二叉樹(shù)。123485679 10第19頁(yè)/共147頁(yè)6.2 6.2 二叉樹(shù)二叉樹(shù) 二、二叉樹(shù)的特點(diǎn) 1.每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)（即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn))

5、; 2.該兩棵子樹(shù)可以為空; 3.該兩棵子樹(shù)有次序之分，分別稱之為左子樹(shù)和右子樹(shù),其次序不能任意顛倒。123485679 10ABAB第20頁(yè)/共147頁(yè)6.2 6.2 二叉樹(shù)二叉樹(shù) (a)空二叉樹(shù)空二叉樹(shù) (b)僅有根結(jié)僅有根結(jié)點(diǎn)的二叉點(diǎn)的二叉樹(shù)樹(shù) (c)右子樹(shù)為右子樹(shù)為空的二叉空的二叉樹(shù)樹(shù)L (d)左子樹(shù)為空的二叉樹(shù)R (e)左、右子樹(shù)均非左、右子樹(shù)均非空的二叉樹(shù)空的二叉樹(shù)LR三、二叉樹(shù)的基本形態(tài)第21頁(yè)/共147頁(yè)6.2 6.2 二叉樹(shù)二叉樹(shù)a ab bc cd de e(a)a ac cd de eb b(b)b bc cd de ea a(c)四、二叉樹(shù)與樹(shù)和有序樹(shù)的區(qū)別第22頁(yè)/共

6、147頁(yè)a ac cd de eb b(b)6.2 6.2 二叉樹(shù)二叉樹(shù)二叉樹(shù)與樹(shù)的區(qū)別：A樹(shù)中結(jié)點(diǎn)的最大度數(shù)沒(méi)有限制，二叉樹(shù)結(jié)點(diǎn)最大度數(shù)為2。B樹(shù)的每個(gè)結(jié)點(diǎn)的子樹(shù)無(wú)左、右之分，二叉樹(shù)的結(jié)點(diǎn)子樹(shù)有明確的左、右之分。二叉樹(shù)與有序樹(shù)的區(qū)別：C.在有序樹(shù)中，某個(gè)結(jié)點(diǎn)只有一個(gè)孩子時(shí)就無(wú)左、右之分 特別要注意：二叉樹(shù)不是樹(shù)的特殊情況，它們是兩種不同的樹(shù)型結(jié)構(gòu)。四、二叉樹(shù)與樹(shù)和有序樹(shù)的區(qū)別a ab bc cd de e(a)第23頁(yè)/共147頁(yè)練習(xí)：畫(huà)出含有3個(gè)結(jié)點(diǎn)（非空）的樹(shù)與二叉樹(shù)的所有不同形態(tài) 樹(shù) 二叉樹(shù)第24頁(yè)/共147頁(yè)6.2 二叉樹(shù)特殊的二叉樹(shù)斜樹(shù)1 . .所有結(jié)點(diǎn)都只有左子樹(shù)的二叉樹(shù)稱為左斜

7、樹(shù)2 . .所有結(jié)點(diǎn)都只有右子樹(shù)的二叉樹(shù)稱為右斜樹(shù)3.3.左斜樹(shù)和右斜樹(shù)統(tǒng)稱為斜樹(shù)。1. 在斜樹(shù)中，每一層只有一個(gè)結(jié)點(diǎn)；2. .斜樹(shù)的結(jié)點(diǎn)個(gè)數(shù)與其深度相同。 斜樹(shù)的特點(diǎn)：ABCABC第25頁(yè)/共147頁(yè)滿二叉樹(shù)：在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的二叉樹(shù)稱為滿二叉樹(shù)。 特點(diǎn)：6.2 二叉樹(shù)123485679 1011 1213 1415特殊的二叉樹(shù)特殊的二叉樹(shù)1. 葉子只能出現(xiàn)在最下一層；葉子只能出現(xiàn)在最下一層；2. 只有度為只有度為0和度為和度為2的結(jié)點(diǎn)。的結(jié)點(diǎn)。第26頁(yè)/共147頁(yè)6.2 二叉樹(shù)特殊的二叉樹(shù)特殊的二叉樹(shù)不是滿二叉樹(shù)，雖然

8、不是滿二叉樹(shù)，雖然所有分支結(jié)點(diǎn)都有左所有分支結(jié)點(diǎn)都有左右子樹(shù)，但葉子不在右子樹(shù)，但葉子不在同一層上。同一層上。滿二叉樹(shù)在同樣深度的二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)最多滿二叉樹(shù)在同樣深度的二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)最多A1523467BCDEFGLM89第27頁(yè)/共147頁(yè)6.2 二叉樹(shù) -深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹(shù)（也稱為近似滿二叉樹(shù)） 完全二叉樹(shù)123485679 10特點(diǎn)：（1 1）葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn) （2 2）對(duì)任一結(jié)點(diǎn)，若其右分支下的子孫最大層次為L(zhǎng) L，則其左分支下的子孫最大層次必為L(zhǎng) L或L+1

9、L+1特殊的二叉樹(shù)特殊的二叉樹(shù)123485679 10 111213 1415第28頁(yè)/共147頁(yè)12345612345721367(a)完全二叉樹(shù)(b)非完全二叉樹(shù)( c)非完全二叉樹(shù)滿二叉樹(shù)是完全二叉樹(shù)的特例。滿二叉樹(shù)是完全二叉樹(shù)的特例。6.2 二叉樹(shù)特殊的二叉樹(shù)特殊的二叉樹(shù)第29頁(yè)/共147頁(yè)由此可得出如下結(jié)論：對(duì)一棵完全二叉樹(shù)，有：1.至多只有最下面兩層上結(jié)點(diǎn)的度數(shù)可以小于22.最下面一層結(jié)點(diǎn)都集中在該層的最左邊3.滿二叉樹(shù)是完全二叉樹(shù)，反之不然，在完全二叉樹(shù)中，若某個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它一定沒(méi)有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。123485679 106.2 二叉樹(shù)特殊的二叉樹(shù)特殊的二叉樹(shù)

10、第30頁(yè)/共147頁(yè)第31頁(yè)/共147頁(yè)6.2.2 6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) 性質(zhì)1： 在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i=1)。第三層上(i=3)(i=3)，有2 23-13-1=4=4個(gè)結(jié)點(diǎn)。第四層上(i=4)(i=4)，有2 24-14-1=8=8個(gè)結(jié)點(diǎn)。第32頁(yè)/共147頁(yè)6.2.2 6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) 性質(zhì)2：深度為k的二叉樹(shù)至多有2k1個(gè)結(jié)點(diǎn)（k=1)）.第33頁(yè)/共147頁(yè)6.2.2 6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)性質(zhì)3： 對(duì)任何一棵二叉樹(shù)，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0n21。第34頁(yè)/共147頁(yè)6.2.2 6.

11、2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) 性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 符號(hào) 表示不大于x的最大整數(shù)。1log2n x123485679 10413110log2K完全二叉樹(shù)的兩個(gè)重要特性第35頁(yè)/共147頁(yè)6.2.2 6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) 性質(zhì)5： 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層次編號(hào),則對(duì)編號(hào)為i的結(jié)點(diǎn)（1=i1，則其雙親是結(jié)點(diǎn)。 （2）如果2in，則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無(wú)左孩子； 否則，其左孩子是結(jié)點(diǎn)。 （3）如果2i1n， 則結(jié)點(diǎn)i無(wú)右孩子 否則，其右孩子是結(jié)點(diǎn)。123485679 10完全二叉樹(shù)的兩個(gè)重要特性性質(zhì)5表明，在完全二叉樹(shù)中，結(jié)點(diǎn)的層序編號(hào)反映

12、了結(jié)點(diǎn)之間的邏輯關(guān)系。第36頁(yè)/共147頁(yè)6.2.2 6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) i/2ii+12i2i+12(i+1)2i+3i+12(i+1)2i+3i2i2i+1完全二叉樹(shù)中結(jié)點(diǎn)i和i+1(a)i和i+1結(jié)點(diǎn)在同一層 (b)i和i+1結(jié)點(diǎn)不在同一層如圖所示為完全二叉樹(shù)上結(jié)點(diǎn)及其左右子如圖所示為完全二叉樹(shù)上結(jié)點(diǎn)及其左右子樹(shù)在結(jié)點(diǎn)之間的關(guān)系。樹(shù)在結(jié)點(diǎn)之間的關(guān)系。第37頁(yè)/共147頁(yè)6.2.2 6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) 在此過(guò)程中，可以從（2）和（3）推出（1），所以先證明（2）和（3）。 對(duì)于i1，由完全二叉樹(shù)的定義，其左孩子是結(jié)點(diǎn)2，若2n，即不存在結(jié)點(diǎn)2，此是，結(jié)點(diǎn)

13、i無(wú)孩子。結(jié)點(diǎn)i的右孩子也只能是結(jié)點(diǎn)3，若結(jié)點(diǎn)3不存在，即3n，此時(shí)結(jié)點(diǎn)i無(wú)右孩子。 對(duì)于i1，可分為兩種情況： （1）設(shè)第j（1=jn，則無(wú)左孩子：第38頁(yè)/共147頁(yè)6.2.2 6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) 其右孩子必定為第j1層的第二個(gè)結(jié)點(diǎn)，編號(hào)為2i1。若2i+1n，則無(wú)右孩子。 （2）假設(shè)第j（1=j=log2n)層上的某個(gè)結(jié)點(diǎn)編號(hào)為i（2j-1=i= 2j -1),且2i11時(shí)，如果i為左孩子，即2（i/2)=i,則i/2是i的雙親；如果i為右孩子，i2p+1,i的雙親應(yīng)為p，p（i1）/2=i/2. 證畢。第39頁(yè)/共147頁(yè)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)二叉樹(shù)

14、的順序存儲(chǔ)結(jié)構(gòu)就是用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹(shù)中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）應(yīng)能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系 如何利用數(shù)組下標(biāo)來(lái)反映結(jié)點(diǎn)之間的邏輯關(guān)系? ?完全二叉樹(shù)和滿二叉樹(shù)中結(jié)點(diǎn)的序號(hào)可以惟一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系 。二叉樹(shù)的邏輯關(guān)系父子關(guān)系。 第40頁(yè)/共147頁(yè)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) A B C D E F G H I J數(shù)組下標(biāo) 1 2 3 4 5 6 7 8 9 10完全二叉樹(shù)的順序存儲(chǔ)CDEFGHIJ以編號(hào)為下標(biāo)第41頁(yè)/共147頁(yè)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)ABC DE F G數(shù)組下標(biāo) 1 2 3 4 5 6 7 8 9 1

15、0 11 12 13ABCDEGF以編號(hào)為下標(biāo)ABCDEGF123561013按照完全二叉樹(shù)編號(hào)第42頁(yè)/共147頁(yè)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)一棵斜樹(shù)的順序存儲(chǔ)會(huì)怎樣呢？深度為k的右斜樹(shù)，k個(gè)結(jié)點(diǎn)需分配2k1個(gè)存儲(chǔ)單元。 一棵二叉樹(shù)改造后成完全二叉樹(shù)形態(tài)，需增加很多空結(jié)點(diǎn)，造成存儲(chǔ)空間的浪費(fèi)。二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)一般僅存儲(chǔ)完全二叉樹(shù)ABC137D15第43頁(yè)/共147頁(yè)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉鏈表基本思想：令二叉樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，鏈表結(jié)點(diǎn)除了存放與二叉樹(shù)結(jié)點(diǎn)有關(guān)的數(shù)據(jù)信息外，還要設(shè)置指示左右孩子的指針。 第44頁(yè)/共147頁(yè)二叉樹(shù)的鏈表表示lChild data rChi

16、lddatalChildrChild每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域、左指針域和右指針域組成。二叉鏈表其中，data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息； lchild：左指針域，存放指向左孩子的指針； rchild：右指針域，存放指向右孩子的指針。 結(jié)點(diǎn)結(jié)構(gòu)第45頁(yè)/共147頁(yè)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)GFEDBAABCDEFGC二叉鏈表具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有多少個(gè)空指針？n+1個(gè)第46頁(yè)/共147頁(yè)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)ABCDEFGGFEDBAC在二叉鏈表中，如何求某結(jié)點(diǎn)的雙親？二叉鏈表第47頁(yè)/共147頁(yè)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)leftChild data parent rightChil

17、dparentdataleftChildrightChild三叉鏈表三叉鏈表 在二叉鏈表的基礎(chǔ)上增加了一個(gè)指向雙親的指針域。第48頁(yè)/共147頁(yè)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)ABCDEFGABDEFCG三叉鏈表第49頁(yè)/共147頁(yè)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 在二叉鏈表這種存儲(chǔ)結(jié)構(gòu)上，二叉樹(shù)的多數(shù)基本運(yùn)算如求根、求左、右孩子等很容易實(shí)現(xiàn)。但求雙親運(yùn)算的實(shí)現(xiàn)比較麻煩，而且其時(shí)間性能較低 空間利用不高，在含有n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域， 三叉鏈表 優(yōu)點(diǎn)： 求雙親運(yùn)算很容易實(shí)現(xiàn)，且時(shí)間性能很好二叉鏈表與三叉鏈表的比較第50頁(yè)/共147頁(yè)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)typedef struct

18、 BiTNode /樹(shù)結(jié)點(diǎn)定義 ElemType data; /結(jié)點(diǎn)數(shù)據(jù)域 struct BiTNode *lChild, *rChild; /左右孩子指針左右孩子指針 BiTNode ,*BiTree;datalChildrChild第51頁(yè)/共147頁(yè)二叉樹(shù)存儲(chǔ)結(jié)構(gòu)課堂練習(xí) 練習(xí) 分別畫(huà)出下圖所示二叉樹(shù)的二叉鏈表、三叉鏈表和順序存儲(chǔ)結(jié)構(gòu)示意圖ABECFD第52頁(yè)/共147頁(yè)6.3 遍歷二叉樹(shù)和線索二叉樹(shù) 6.3.1遍歷二叉樹(shù) 二叉樹(shù)的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。二叉樹(shù)遍歷操作的結(jié)果？非線性結(jié)構(gòu)線性化抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)

19、行的各種處理，這里簡(jiǎn)化為輸出結(jié)點(diǎn)的數(shù)據(jù)。第53頁(yè)/共147頁(yè)6.3.16.3.1遍歷二叉樹(shù)遍歷二叉樹(shù)6.3 6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)(右子樹(shù))(根結(jié)點(diǎn))(左子樹(shù))DLR考慮二叉樹(shù)的組成：二叉樹(shù)的遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD 如果限定先左后右，則二叉樹(shù)遍歷方式有三種：先序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹(shù)的層序編號(hào)的次序訪問(wèn)各結(jié)點(diǎn)。 第54頁(yè)/共147頁(yè)6.3.1遍歷二叉樹(shù)- -/ /+ +* *abcdef.（前綴表示波蘭式）先序遍歷 (Preorder Traversal)(Preorder Traversal)第55頁(yè)

20、/共147頁(yè)6.3.1遍歷二叉樹(shù)void PreOrder (BiTNode *T) if (T = = NULL) return error; /遞歸調(diào)用的結(jié)束條件 visit (T-data); PreOrder (T-lChild); PreOrder (T-rChild);二叉樹(shù)遞歸的先序遍歷算法第56頁(yè)/共147頁(yè)6.3.1遍歷二叉樹(shù)- -/ /+ +* *abcdef.（中綴表示）中序遍歷 (Inorder Traversal)第57頁(yè)/共147頁(yè)6.3.1遍歷二叉樹(shù)void InOrder (BiTNode *T) if (T != NULL) InOrder (T-lChild

21、); visit (T-data); InOrder (T-rChild); 第58頁(yè)/共147頁(yè)6.3.1遍歷二叉樹(shù).(后綴表示逆波蘭式)后序遍歷 (Postorder Traversal)- -/ /+ +* *abcdef第59頁(yè)/共147頁(yè)6.3.1遍歷二叉樹(shù)void PostOrder (BiTNode *T) if (T != NULL) PostOrder (T-lChild); PostOrder (T-rChild); visit (T-data); 二叉樹(shù)遞歸的后序遍歷算法第60頁(yè)/共147頁(yè)AB1111111112222222223333先序序列：A B D E A B

22、D E H I C F GH I C F G中序序列：D B D B H E I A F C GH E I A F C G后序序列：D H D H I E B F G C AI E B F G C A333336.3.1遍歷二叉樹(shù)第61頁(yè)/共147頁(yè)6.3.1遍歷二叉樹(shù)BEAFDCGHIJBEAFDCGHIJ先序序列：A B C D A B C D E F G H I JE F G H I J中序序列：B C D B C D A F E H J I GA F E H J I G后序序列：D C B D C B F J I H G E A F J I H G E A 課堂練習(xí)二第62頁(yè)/共147

23、頁(yè)6.3.1遍歷二叉樹(shù)層序遍歷二叉樹(shù)的層次遍歷是指從二叉樹(shù)的第一層（即根結(jié)點(diǎn)）開(kāi)始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。 - -/ /+ +* *abcdef遍歷結(jié)果：- + / a * e f b c d第63頁(yè)/共147頁(yè)6.3.1遍歷二叉樹(shù)若已知一棵二叉樹(shù)的先序（或中序，或后序，或?qū)有颍┬蛄校芊裎┮淮_定這棵二叉樹(shù)呢？遍歷的性質(zhì)性質(zhì)1 1、由一棵二叉樹(shù)的先序序列和中序序列可惟一確定這棵二叉樹(shù)性質(zhì)2 2、由一棵二叉樹(shù)的后序序列和中序序列可惟一確定這棵二叉樹(shù)由遍歷序列恢復(fù)二叉樹(shù)第64頁(yè)/共147頁(yè)6.3.1遍歷二叉樹(shù)例如，已知一棵二叉樹(shù)的中序序列和后序序列分別為B

24、DCEAFHG和DECBHGFA，試畫(huà)出這棵二叉樹(shù)。BDCEFHGAFHGABDCE由遍歷序列恢復(fù)二叉樹(shù)第65頁(yè)/共147頁(yè)FHGABDCEFABECDGHFHGABCDEHGABCDEF由遍歷序列恢復(fù)二叉樹(shù)中序序列BDCEAFHG 后序序列DECBHGFA6.3.1遍歷二叉樹(shù)第66頁(yè)/共147頁(yè)6.3.1遍歷二叉樹(shù)練習(xí)三第67頁(yè)/共147頁(yè)6.3.1遍歷二叉樹(shù)HBDFEKCGAEKCGABHDF第68頁(yè)/共147頁(yè)6.3.1遍歷二叉樹(shù)KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG 第69頁(yè)/共147頁(yè)6.3.1遍歷二叉樹(shù)int Height (BiTNode *T)

25、 if (T = NULL) return 0 0; else int m = Height (T-lChild); int n = Height (T-rChild); return (m n) ? m+1 : n+1; 第70頁(yè)/共147頁(yè)Status CreateBiTree(BiTree &T)Status CreateBiTree(BiTree &T)/建立一棵二叉樹(shù)建立一棵二叉樹(shù) scanf(&ch); scanf(&ch); /依次輸入字符，空格字符表示空樹(shù)依次輸入字符，空格字符表示空樹(shù) if(ch=) T=NULL;if(ch=) T=NULL;

26、 else else if(!(T=(BiTNode if(!(T=(BiTNode * *)malloc(sizeof(BiTNode) )malloc(sizeof(BiTNode) exit(OVERFLOW); exit(OVERFLOW); T Tdata=ch; data=ch; /生成根結(jié)點(diǎn)生成根結(jié)點(diǎn) CreateBiTree(TCreateBiTree(Tlchild); lchild); /構(gòu)造左子樹(shù)構(gòu)造左子樹(shù) CreateBiTree(TCreateBiTree(Trchildd); rchildd); /構(gòu)造右子樹(shù)構(gòu)造右子樹(shù) return OK; return OK; 例

27、二：構(gòu)建一棵二叉樹(shù)（使用先序遍歷）6.3.1遍歷二叉樹(shù)第71頁(yè)/共147頁(yè)AB1111111112222222223333先序序列：A B D E A B D E H I C F GH I C F G中序序列：D B D B H E I A F C GH E I A F C G后序序列：D H D H I E B F G C AI E B F G C A333336.3.2二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn)第72頁(yè)/共147頁(yè)6.3.2二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn)先序遍歷的定義：1）訪問(wèn)根結(jié)點(diǎn)2）先序遍歷左子樹(shù)3）先序遍歷右子樹(shù)(右子樹(shù))(根結(jié)點(diǎn))(左子樹(shù))vLRXTPre(T)Pre(t-lchild)Pre

28、(t-rchild). .XLXR(a)(b)第73頁(yè)/共147頁(yè)6.3.26.3.2二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn)abcde先序遍歷的定義：1）訪問(wèn)根結(jié)點(diǎn)2）先序遍歷左子樹(shù)3）先序遍歷右子樹(shù)cdcc訪問(wèn)訪問(wèn)a進(jìn)棧進(jìn)棧c左進(jìn)左進(jìn)b訪問(wèn)訪問(wèn)b進(jìn)棧進(jìn)棧d左進(jìn)左進(jìn)空空退棧退棧d訪問(wèn)訪問(wèn)d左進(jìn)左進(jìn)空空退棧退棧c訪問(wèn)訪問(wèn)c左進(jìn)左進(jìn)e訪問(wèn)訪問(wèn)e左進(jìn)左進(jìn)空空退棧退棧 結(jié)束結(jié)束第74頁(yè)/共147頁(yè)6.3.2二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn)void PreOrder(BiTree T) stack S; InitStack(&S); /遞歸工作棧 BiTNode * p = T; Push (&S, NULL);

29、 while (p != NULL) visit(p-data); if (p-rChild != NULL) Push(&S, p-rChild); if (p-lChild != NULL) p = p-lChild; /進(jìn)左子樹(shù) else Pop(&S, p-rChild); /左子樹(shù)空, 進(jìn)右子樹(shù) 第75頁(yè)/共147頁(yè)6.3.2二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn)abcdebaadaa左空左空退棧退棧訪問(wèn)訪問(wèn)左空左空 退棧退棧訪問(wèn)訪問(wèn)退棧退棧訪問(wèn)訪問(wèn)左空左空ec退棧訪問(wèn)退棧訪問(wèn)cc右空右空退棧訪問(wèn)退棧訪問(wèn) ?？战Y(jié)束棧空結(jié)束中序遍歷的定義：1）中序遍歷左子樹(shù)2）訪問(wèn)根結(jié)點(diǎn)3）中序遍歷右

30、子樹(shù)第76頁(yè)/共147頁(yè)6.3.2二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn)void InOrder(BiTree T) stack S; InitStack(S); /遞歸工作棧 BiTNode *p = T; /初始化 while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lChild; /根指針進(jìn)棧，根指針進(jìn)棧，遍歷左子樹(shù)遍歷左子樹(shù) else Pop(S, p); /退棧 visit(p-data); /訪問(wèn)根結(jié)點(diǎn) p = p-rChild; /遍歷右子樹(shù) 第77頁(yè)/共147頁(yè)6.3.2二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn) 思考：后序遍歷的非遞歸算法第78頁(yè)/共147頁(yè)6.

31、3.2 線索二叉樹(shù)如何保存二叉樹(shù)的某種遍歷序列？ 將二叉鏈表中的空指針域指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn) 當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí), ,只能找到結(jié)點(diǎn)的左右孩子的信息, ,而不能找到結(jié)點(diǎn)的任一序列的前驅(qū)與后繼信息, ,這種信息只有在遍歷的動(dòng)態(tài)過(guò)程中才能得到。第79頁(yè)/共147頁(yè)6.3.2 線索二叉樹(shù)線索：將二叉鏈表中的空指針域指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針被稱為線索；線索化：使二叉鏈表中結(jié)點(diǎn)的空鏈域存放其前驅(qū)或后繼信息的過(guò)程稱為線索化；加上線索的二叉鏈表稱為線索鏈表線索二叉樹(shù)：加上線索的二叉樹(shù)稱為線索二叉樹(shù)。第80頁(yè)/共147頁(yè)6.3.2 線索二叉樹(shù) ltag lchild data child rta

32、g0: lchild指向該結(jié)點(diǎn)的左孩子1: lchild指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)0: rchild指向該結(jié)點(diǎn)的右孩子1: rchild指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)ltag=rtag=結(jié)點(diǎn)結(jié)構(gòu)線索鏈表第81頁(yè)/共147頁(yè)例如下圖（a）是一棵中序線索二叉樹(shù)，它的線索鏈表如圖 (b)所示。 （a）n注：不同的遍歷次序注：不同的遍歷次序其得到的線索二叉樹(shù)其得到的線索二叉樹(shù)也不同也不同( (可分別稱為可分別稱為先序線索二叉樹(shù)、中先序線索二叉樹(shù)、中序線索二叉樹(shù)和后序序線索二叉樹(shù)和后序線索二叉樹(shù)線索二叉樹(shù)) )6.3.2 線索二叉樹(shù)第82頁(yè)/共147頁(yè)線索鏈表preprep(b)6.3.2 線索二叉樹(shù)第83頁(yè)/共147

33、頁(yè)如何在線索二叉樹(shù)中找結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)？： 1）樹(shù)中所有葉結(jié)點(diǎn)的左鏈?zhǔn)蔷€索，因此葉結(jié)點(diǎn)的左鏈域直接指向其前驅(qū)結(jié)點(diǎn)。 2）對(duì)于非終端結(jié)點(diǎn)，若該結(jié)點(diǎn)無(wú)左孩子，則其左鏈域?yàn)榫€索，直接指向其前驅(qū)結(jié)點(diǎn)。若有左孩子，則該結(jié)點(diǎn)的前驅(qū)為中序遍歷其左子樹(shù)時(shí)最后訪問(wèn)的那個(gè)結(jié)點(diǎn)，即左子樹(shù)中最右下的結(jié)點(diǎn)為其前驅(qū)結(jié)點(diǎn)。 1）樹(shù)中所有葉結(jié)點(diǎn)的右鏈?zhǔn)蔷€索，因此葉結(jié)點(diǎn)的右鏈域直接指示該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。 2）非終端結(jié)點(diǎn)若無(wú)右孩子，則其右鏈?zhǔn)蔷€索，指向后繼，若有右孩子，則其后繼是中序遍歷其右子樹(shù)時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)，即右子樹(shù)中最左下結(jié)點(diǎn) 。6.3.2 線索二叉樹(shù)第84頁(yè)/共147頁(yè)線索鏈表preprepT T6.3.2 線索二

34、叉樹(shù)第85頁(yè)/共147頁(yè)如何進(jìn)行二叉樹(shù)的線索化呢？ 線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向結(jié)點(diǎn)前驅(qū)或后繼的線索，而一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼的信息只有在遍歷時(shí)才能得到，因此線索化過(guò)程即為在遍歷的過(guò)程中修改空指針的過(guò)程。6.3.2 線索二叉樹(shù)第86頁(yè)/共147頁(yè)6.4 樹(shù)與森林實(shí)現(xiàn)樹(shù)的存儲(chǔ)結(jié)構(gòu)，關(guān)鍵是什么? ?樹(shù)中結(jié)點(diǎn)之間的邏輯關(guān)系是什么? ?思考問(wèn)題的出發(fā)點(diǎn)：如何表示結(jié)點(diǎn)的雙親和孩子如何表示樹(shù)中結(jié)點(diǎn)之間的邏輯關(guān)系。6.4.1 6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)父子關(guān)系第87頁(yè)/共147頁(yè)6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親表示法基本思想：用一組連續(xù)的存儲(chǔ)空間（一維數(shù)組）存儲(chǔ)樹(shù)的各個(gè)結(jié)點(diǎn)（一般按層序存儲(chǔ)），同時(shí)在每

35、個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在數(shù)組中的位置。 data parentdata：存儲(chǔ)樹(shù)中結(jié)點(diǎn)的數(shù)據(jù)信息parent：存儲(chǔ)該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)結(jié)點(diǎn)結(jié)構(gòu)： 第88頁(yè)/共147頁(yè)6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu) #define MAXNODE typedef struct PTNode /結(jié)點(diǎn)結(jié)構(gòu) elemtype data; int parent; /雙親位置域 PTNode;PTNode tMAXNODE; data parent樹(shù)的雙親表示法實(shí)質(zhì)上是一個(gè)靜態(tài)鏈表。雙親表示法第89頁(yè)/共147頁(yè)6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)下標(biāo) data parent012345678 A - -1 B 0 C

36、0 D 1 E 1 F 1 G 2 H 2 I 4 雙親表示法ACBHFEDGI優(yōu)點(diǎn)： 實(shí)現(xiàn)Parent（t，x）操作 和Root（x）操作很方便不足：求某結(jié)點(diǎn)的孩子結(jié)點(diǎn)，即實(shí)現(xiàn)Child（t，x，i）操作時(shí)，則需要查詢整個(gè)數(shù)組。不能反映各兄弟結(jié)點(diǎn)之間的關(guān)系，所以實(shí)現(xiàn)RightSibling（t，x）操作也比較困難。第90頁(yè)/共147頁(yè)6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)。 如何確定鏈表中的結(jié)點(diǎn)結(jié)構(gòu)？ 方案一：指針域的個(gè)數(shù)等于樹(shù)的度-同構(gòu)data child1 child2 childd 其中：data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)

37、信息； child1childd：指針域，指向該結(jié)點(diǎn)的孩子。 孩子鏈表表示法第91頁(yè)/共147頁(yè)6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)缺點(diǎn)：浪費(fèi)空間ACBHFEDGIABCDEFGHI 孩子鏈表表示法第92頁(yè)/共147頁(yè)6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)。 如何確定鏈表中的結(jié)點(diǎn)結(jié)構(gòu)？方案二： 指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度-異構(gòu) data degree child1 child2 childd其中：data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息； degree：度域，存放該結(jié)點(diǎn)的度； child1childd：指針域，指向該結(jié)點(diǎn)的孩子孩子鏈表表示法第9

38、3頁(yè)/共147頁(yè)6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)缺點(diǎn)：結(jié)點(diǎn)結(jié)構(gòu)不一致，操作不方便ACBHFEDGIA 2B 3C 2E 1I 0G 0H 0F 0D 0孩子鏈表表示法第94頁(yè)/共147頁(yè)6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子鏈表表示法基本思想：把每個(gè)結(jié)點(diǎn)的孩子排列起來(lái)，看成是一個(gè)線性表，且以單鏈表存儲(chǔ)，則n個(gè)結(jié)點(diǎn)共有 n 個(gè)孩子鏈表。這 n 個(gè)單鏈表共有 n 個(gè)頭指針，這 n 個(gè)頭指針又組成了一個(gè)線性表，為了便于進(jìn)行查找采用順序存儲(chǔ)。最后，將存放 n 個(gè)頭指針的數(shù)組和存放n個(gè)結(jié)點(diǎn)的數(shù)組結(jié)合起來(lái)，構(gòu)成孩子鏈表的表頭數(shù)組。 如何確定鏈表中的結(jié)點(diǎn)結(jié)構(gòu)？將結(jié)點(diǎn)的所有孩子放在一起，構(gòu)成線性表。第95頁(yè)/共147頁(yè)6.4.

39、1 樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子鏈表表示法ACBHFEDGI012345678下標(biāo) data firstchild A B C D E F G H I 12 345 7 68 child next孩子結(jié)點(diǎn)data firstchild表頭結(jié)點(diǎn)第96頁(yè)/共147頁(yè)ACBHFEDGI6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親孩子表示法012345678 A - -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 data parent firstchild12 345 7 68 第97頁(yè)/共147頁(yè)6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法(二叉鏈表表示法)ACBHFEDGI某結(jié)點(diǎn)的第一個(gè)孩子是惟一的某結(jié)點(diǎn)的

40、右兄弟是惟一的設(shè)置兩個(gè)分別指向該結(jié)點(diǎn)的第一個(gè)孩子和右鄰兄弟的指針 第98頁(yè)/共147頁(yè)6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)類型描述如下：Typedef struct CSNode elemtype data; /結(jié)點(diǎn)信息 struct CSNode *firstchild, /指向第一個(gè)孩子結(jié)點(diǎn)的指針 *nextsibling; /指向下一個(gè)兄弟結(jié)點(diǎn)的指針 CSNode,*CSTree; /用指向樹(shù)的根結(jié)點(diǎn)的指針來(lái)表示一棵樹(shù)結(jié)點(diǎn)結(jié)構(gòu)firstchild data nextsiblingdata：數(shù)據(jù)域，存儲(chǔ)該結(jié)點(diǎn)的數(shù)據(jù)信息；firstchild：指針域，指向該結(jié)點(diǎn)第一個(gè)孩子；nextsibling：指針域

41、，指向該結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)。 孩子兄弟表示法第99頁(yè)/共147頁(yè)6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法ACBHFEDGI A B C D E F G H I第100頁(yè)/共147頁(yè)優(yōu)缺點(diǎn)： 可以直接實(shí)現(xiàn)樹(shù)的大部分操作，如找結(jié)點(diǎn)的孩子、兄弟等操作。但對(duì)樹(shù)結(jié)點(diǎn)作Parent操作時(shí)需遍歷樹(shù)。如果要反復(fù)執(zhí)行Parent操作， 則可為每個(gè)結(jié)點(diǎn)增設(shè)一個(gè)parent域，這樣就能方便地實(shí)現(xiàn)parent(T,x)運(yùn)算6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)第101頁(yè)/共147頁(yè)6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)畫(huà)出下列樹(shù)的孩子兄弟表示法的結(jié)構(gòu)圖(a)(c)樹(shù)二叉樹(shù)ABCDEFGA BCED F GAEBCFDG(b)練習(xí)第102頁(yè)/共147

42、頁(yè) 以二叉鏈表為媒介可導(dǎo)出樹(shù)與二叉樹(shù)之間的對(duì)應(yīng)關(guān)系。將樹(shù)轉(zhuǎn)換為二叉樹(shù)，這樣，對(duì)樹(shù)的操作就可以借助二叉樹(shù)存儲(chǔ)，利用二叉樹(shù)上的操作來(lái)實(shí)現(xiàn)。6.4.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換第103頁(yè)/共147頁(yè)6.4.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換方法一：借助二叉鏈表，讓該結(jié)點(diǎn)的左分枝指向該結(jié)點(diǎn)的第一個(gè)孩子，右分枝指向該結(jié)點(diǎn)的下一個(gè)兄弟。ABCDEFGAEBCFDG第104頁(yè)/共147頁(yè) I A B C DE F G H(b) A B CDE G H FI(a)ABEFCDGHI(d)ABCDEFGHI(c)方法二： 在樹(shù)中所有的兄弟結(jié)點(diǎn)之間加一連線； 對(duì)每個(gè)結(jié)點(diǎn)，除保留與其長(zhǎng)子（最左孩子）的連線外，去除該結(jié)點(diǎn)與其它

43、孩子之間的聯(lián)線； 以根結(jié)點(diǎn)為軸心，將整個(gè)樹(shù)順時(shí)針轉(zhuǎn)4545度。6.4.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換第一步：在樹(shù)中所有的兄弟結(jié)點(diǎn)之間加一連線第二步：對(duì)每個(gè)結(jié)點(diǎn)，除保留與其長(zhǎng)子（最左孩子）的連線外，去除該結(jié)點(diǎn)與其它孩子之間的聯(lián)線；第三步：以根結(jié)點(diǎn)為軸心，將整個(gè)樹(shù)順時(shí)針轉(zhuǎn)45度。第105頁(yè)/共147頁(yè)6.4.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換 將下列的樹(shù)轉(zhuǎn)換為二叉樹(shù)課堂練習(xí)第106頁(yè)/共147頁(yè)6.4.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換 將下列的樹(shù)轉(zhuǎn)換為二叉樹(shù)DIABECFGH轉(zhuǎn)換后的二叉樹(shù)課堂練習(xí)第107頁(yè)/共147頁(yè)6.4.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換2. 森林轉(zhuǎn)換為二叉樹(shù) 森林轉(zhuǎn)換為二叉樹(shù)的方法： 逐個(gè)轉(zhuǎn)換 將森

44、林中的每一棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù)； 加線 將各二叉樹(shù)的根結(jié)點(diǎn)視為兄弟用線連起來(lái)； 層次調(diào)整 以第一棵樹(shù)的根結(jié)點(diǎn)作為二叉樹(shù)的根結(jié)點(diǎn)，按順時(shí)針?lè)较蜻m當(dāng)旋轉(zhuǎn)。第108頁(yè)/共147頁(yè)ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ6.4.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換將如圖所示的森林轉(zhuǎn)換為二叉樹(shù)第109頁(yè)/共147頁(yè)ADCBEFHIGJ二、二叉樹(shù)轉(zhuǎn)換成樹(shù)、森林二、二叉樹(shù)轉(zhuǎn)換成樹(shù)、森林方法一方法一1.二叉樹(shù)的根作為森林中第一棵樹(shù)的根二叉樹(shù)的根作為森林中第一棵樹(shù)的根2.二叉樹(shù)的左子樹(shù)轉(zhuǎn)換成森林中第一棵樹(shù)的子樹(shù)二叉樹(shù)的左子樹(shù)轉(zhuǎn)換成森林中第一棵樹(shù)的子樹(shù)森林森林3.二叉樹(shù)的右子樹(shù)轉(zhuǎn)換成

45、森林中其它的樹(shù)二叉樹(shù)的右子樹(shù)轉(zhuǎn)換成森林中其它的樹(shù)6.4.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換第110頁(yè)/共147頁(yè)6.4.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換ADCBEFHIGJEFADCBHIGJADCBEFHIGJ二叉樹(shù)轉(zhuǎn)換為森林第111頁(yè)/共147頁(yè)方法二1）將結(jié)點(diǎn)的左孩子的右孩子、右孩子的右孩子與該結(jié)點(diǎn)連接起來(lái)2）去掉所有結(jié)點(diǎn)與其右孩子的連線EFADCBEFHIGJADCBHIGJ6.4.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換第112頁(yè)/共147頁(yè)將如圖所示的森林轉(zhuǎn)換為二叉樹(shù)將如圖所示的森林轉(zhuǎn)換為二叉樹(shù)GHIJLNKOMADCBFE6.4.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換課堂練習(xí)第113頁(yè)/共147頁(yè)將如圖所示的森林轉(zhuǎn)換為

46、二叉樹(shù)將如圖所示的森林轉(zhuǎn)換為二叉樹(shù)GHIJLNKOMADCBFEFADBECGHIJLKOMN6.4.2 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換第114頁(yè)/共147頁(yè)FADBECGHIJLKOMN最后轉(zhuǎn)換成的二叉樹(shù)最后轉(zhuǎn)換成的二叉樹(shù)第115頁(yè)/共147頁(yè)6.4.3 樹(shù)與森林的遍歷1、先序（根）遍歷樹(shù)-先訪問(wèn)樹(shù)根結(jié)點(diǎn)n，然后從左到右，依次先序遍歷根的每棵子樹(shù)T1,T2,.,Tk 。2、后序（根）遍歷樹(shù)-先從左到右，依次對(duì)樹(shù)的每棵子樹(shù)T1,T2,.,Tk進(jìn)行后序遍歷，最后訪問(wèn)樹(shù)根結(jié)點(diǎn)n。 設(shè)T以n為樹(shù)根，樹(shù)根的子樹(shù)從左到右依次為T(mén)1,T2,.,Tk，那么有：第116頁(yè)/共147頁(yè)6.4.3 樹(shù)與森林的遍歷先根：A

47、 B E F C D G H I 后根：E F B C G H I D A 例如例如,右圖樹(shù)右圖樹(shù) AEI B CD E G H FI樹(shù)樹(shù)ABFCDGH二叉樹(shù)二叉樹(shù)右圖二叉樹(shù)右圖二叉樹(shù)先序先序: A B E F C D G H I 中序：中序：E F B C G H I D A先根遍歷樹(shù)先根遍歷樹(shù) 先序遍歷該樹(shù)先序遍歷該樹(shù)對(duì)應(yīng)的二叉樹(shù)對(duì)應(yīng)的二叉樹(shù)后根遍歷樹(shù)后根遍歷樹(shù) 中序遍歷該樹(shù)中序遍歷該樹(shù)對(duì)應(yīng)的二叉樹(shù)對(duì)應(yīng)的二叉樹(shù)第117頁(yè)/共147頁(yè)6.4.3 樹(shù)與森林的遍歷按照樹(shù)與森林相互遞歸定義，可推出森林的兩種遍歷方法：一、先序遍歷森林 若森林非空，則可按下述規(guī)則遍歷：1.訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn);

48、2.先序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林;3.先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。二、中序遍歷森林 若森林非空，則可按下述規(guī)則遍歷：1.中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林;2.訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn);3.中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林 第118頁(yè)/共147頁(yè)6.4.3 樹(shù)與森林的遍歷ADCBEFHIGJ先序遍歷序列：先序遍歷序列：A B C D E F G H J I中序遍歷序列：中序遍歷序列：B C D A F E J H I G先序遍歷森林 先序遍歷該森林對(duì)應(yīng)的二叉樹(shù)中序遍歷森林 中序遍歷該森林對(duì)應(yīng)的二叉樹(shù)ADCBEFHIGJ第119頁(yè)/共147頁(yè)6.4.3 樹(shù)與森林

49、的遍歷總 結(jié) 由上述討論可知: 當(dāng)用二叉鏈表作樹(shù)和森林的存儲(chǔ)結(jié)構(gòu)時(shí)，樹(shù)和森林的先根遍歷（先序）和后根遍歷（中序）可借助二叉樹(shù)的先序遍歷和中序遍歷算法來(lái)實(shí)現(xiàn)第120頁(yè)/共147頁(yè)相關(guān)概念1.1.結(jié)點(diǎn)間的路徑長(zhǎng)度-從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支數(shù)目6.5 赫夫曼樹(shù)及其應(yīng)用2.葉子結(jié)點(diǎn)的權(quán)值-對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值。 3.3.結(jié)點(diǎn)帶權(quán)的路徑長(zhǎng)度從該根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)值的乘積。2347第121頁(yè)/共147頁(yè)6.5 赫夫曼樹(shù)及其應(yīng)用4.4.二叉樹(shù)的帶權(quán)路徑長(zhǎng)度（weighted path weighted path length of treelength of t

50、ree）-二叉樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。WPL= nkkklw1第k個(gè)葉子的權(quán)值；從根結(jié)點(diǎn)到第k個(gè)葉子的路徑長(zhǎng)度AB CD2347WPL=2*2+3*2+4*2+7*2=32第122頁(yè)/共147頁(yè)6.5 赫夫曼樹(shù)及其應(yīng)用5.赫夫曼樹(shù)：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。例：給定4個(gè)葉子結(jié)點(diǎn)，其權(quán)值分別為2，3，4，7，可以構(gòu)造出形狀不同的多個(gè)二叉樹(shù)。 WPL=32 WPL=41 WPL=30234723477423第123頁(yè)/共147頁(yè)6.5 赫夫曼樹(shù)及其應(yīng)用赫夫曼樹(shù)的特點(diǎn)：1. 權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。 2. 只有度為

51、0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn). 2347WPL=32 WPL=41 WPL=3023477423第124頁(yè)/共147頁(yè)6.5 赫夫曼樹(shù)及其應(yīng)用赫夫曼算法基本思想：赫夫曼算法基本思想： 初始化初始化：由給定的：由給定的n n個(gè)權(quán)值個(gè)權(quán)值 w w1 1，w w2 2，w wn n 構(gòu)構(gòu)造造n n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)，從而得到一個(gè)棵只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)，從而得到一個(gè)二叉樹(shù)集合二叉樹(shù)集合F F T T1 1，T T2 2，T Tn n ； 選取與合并選取與合并：在：在F F中選取根結(jié)點(diǎn)的權(quán)值中選取根結(jié)點(diǎn)的權(quán)值最小最小的的兩棵二叉樹(shù)分別作為左、右子樹(shù)構(gòu)造一棵新的兩棵

52、二叉樹(shù)分別作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，這棵新二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左二叉樹(shù)，這棵新二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和；、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和； 刪除與加入刪除與加入：在：在F F中刪除作為左、右子樹(shù)的兩中刪除作為左、右子樹(shù)的兩棵二叉樹(shù)，并將新建立的二叉樹(shù)加入到棵二叉樹(shù)，并將新建立的二叉樹(shù)加入到F F中；中； 重復(fù)重復(fù)、兩步，當(dāng)集合、兩步，當(dāng)集合F F中只剩下一棵二叉中只剩下一棵二叉樹(shù)時(shí)，這棵二叉樹(shù)便是赫夫曼樹(shù)。樹(shù)時(shí)，這棵二叉樹(shù)便是赫夫曼樹(shù)。 怎樣構(gòu)造一棵赫夫曼樹(shù)呢？第125頁(yè)/共147頁(yè)第1步：初始化例：給定權(quán)值 W2，3，4，5 ，構(gòu)造赫夫曼樹(shù)3524第2步：選取與

53、合并32 5第3步：刪除與加入5432 5赫夫曼樹(shù)的構(gòu)造過(guò)程6.5 赫夫曼樹(shù)及其應(yīng)用第126頁(yè)/共147頁(yè)W2，3，4，5 赫夫曼樹(shù)的構(gòu)造過(guò)程重復(fù)第2步5432 554 9重復(fù)第3步 554 9326.5 赫夫曼樹(shù)及其應(yīng)用第127頁(yè)/共147頁(yè)W2，3，4，5 赫夫曼樹(shù)的構(gòu)造過(guò)程重復(fù)第2步重復(fù)第3步 554 932 554 932146.5 赫夫曼樹(shù)及其應(yīng)用第128頁(yè)/共147頁(yè)6.5 赫夫曼樹(shù)及其應(yīng)用 給定權(quán)值7，18，3，32，5，26，12，8，構(gòu)造相應(yīng)的赫夫曼樹(shù),要求左子樹(shù)根結(jié)點(diǎn)的權(quán)值盡可能地小于右子樹(shù)根結(jié)點(diǎn)的權(quán)值。課堂練習(xí)第129頁(yè)/共147頁(yè)赫夫曼樹(shù)的應(yīng)用-判定樹(shù)在解決某些判定問(wèn)題

54、時(shí)，利用赫夫曼樹(shù)可以得到最佳判定算法。例1 將學(xué)生百分成績(jī)按分?jǐn)?shù)段分級(jí)的程序。若學(xué)生成績(jī)分布是均勻的，可用圖（a)二叉樹(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。 a60 a70 a80 a90 不及格中等良好優(yōu)秀及格YNYNYNYN(a)輸入10000個(gè)數(shù)據(jù)，則需進(jìn)行31500次比較。6.5 赫夫曼樹(shù)及其應(yīng)用第130頁(yè)/共147頁(yè)分?jǐn)?shù)分?jǐn)?shù)0596069707980899099比例比例0.050.150.40.30.10 70a 80 a60 及格中等良好 80a90 60a70 不及格優(yōu)秀YNYYYNNN(b) 不及格Y a90 a80 a70 a60 優(yōu)秀中等及格良好YNNN(c)YYY 學(xué)生成績(jī)分布不是均勻的情況：以

55、比例數(shù)為權(quán)構(gòu)造一棵赫夫曼樹(shù)，如（b)判斷樹(shù)所示。再將每一比較框的兩次比較改為一次，可得到（c)判定樹(shù)。輸入10000個(gè)數(shù)據(jù)，僅需進(jìn)行22000次比較。6.5 赫夫曼樹(shù)及其應(yīng)用第131頁(yè)/共147頁(yè)赫夫曼樹(shù)的應(yīng)用-赫夫曼編碼 利用赫夫曼樹(shù)構(gòu)造通訊中電文編碼例如：要傳輸一個(gè)電文：CAS；CAT；SAT；AT;要傳輸?shù)淖址?D=C，A，S，T， ；每個(gè)字符出現(xiàn)的頻率是W= 2，4， 2，3， 3 6.5 赫夫曼樹(shù)及其應(yīng)用等長(zhǎng)編碼等長(zhǎng)編碼：C(000)A(001)S(010)T(011);(100)000001010100000001011100010001011100001011 42位不等長(zhǎng)編

56、碼不等長(zhǎng)編碼：C(0)A(00)S(1)T(01);(10)000110000011010001100001 24位 無(wú)法翻譯前綴編碼：前綴編碼：任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴C(0)A(10)S(110)T(1110);(1111)0101101111010111011111101011101111101110 40位前綴碼第132頁(yè)/共147頁(yè)6.5 赫夫曼樹(shù)及其應(yīng)用電文總長(zhǎng)達(dá)到最短的前綴編碼的方法-構(gòu)造一棵赫夫曼樹(shù)（1）用頻率作為葉子結(jié)點(diǎn)的權(quán)值生成一棵赫夫曼樹(shù)，并將對(duì)應(yīng)權(quán)值wi的葉子結(jié)點(diǎn)注明對(duì)應(yīng)的字符；（2）約定左分支表示字符“0”，

57、右分支表示字符1 則從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)所經(jīng)過(guò)的路徑分支組成的0和1的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼，我們稱之為赫夫曼編碼。求編碼的過(guò)程：從葉子結(jié)點(diǎn)出發(fā)走一條從葉子到根的路徑求譯碼的過(guò)程：從根出發(fā)走一條從根到葉子的路徑怎樣才能使總的串長(zhǎng)達(dá)到最小呢？第133頁(yè)/共147頁(yè)例子：要傳輸?shù)碾娢氖荂AS；CAT；SAT；AT要傳輸?shù)淖址?D=C，A，S，T， ；每個(gè)字符出現(xiàn)的頻率是W= 2，4， 2，3， 3 各字符編碼是 T ； A C S 00 01 10 110 111上述電文編碼：（32位）1101011101110100001111100001100003342200111T;ACS106

58、14846.5 赫夫曼樹(shù)及其應(yīng)用第134頁(yè)/共147頁(yè)赫夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)及其算法的實(shí)現(xiàn)1. 設(shè)置一個(gè)數(shù)組huffTree2n-1保存赫夫曼樹(shù)中各點(diǎn)的信息，數(shù)組元素的結(jié)點(diǎn)結(jié)構(gòu) ：其存儲(chǔ)結(jié)構(gòu)為：Typedef struct float weight; int lchild,rchild,parent; hufmtree;hufmtree treem;/設(shè)patent域不僅是為了使涉及雙親的運(yùn)算方便，其主要作用是區(qū)分根和非根結(jié)點(diǎn)，若parent的值為-1，則表示該結(jié)點(diǎn)是無(wú)雙親的根結(jié)點(diǎn)，否則非根結(jié)點(diǎn)。weightweightLchildLchildParentParentrchildrchild結(jié)點(diǎn)結(jié)構(gòu)第135頁(yè)/共147頁(yè)6.5 赫夫曼樹(shù)及其應(yīng)用1. 數(shù)組huffTree初始化，所有元素結(jié)點(diǎn)的雙親、左、右孩子都置為- -1；2. 數(shù)組huffTree的前n個(gè)元素的權(quán)值置給定值wn；3. 進(jìn)行n- -1次合并 3.1 在二叉樹(shù)集合中選取兩個(gè)權(quán)值最小的根結(jié)點(diǎn)，其下標(biāo)分別為i1, i2； 3.2 將二叉樹(shù)i1、i2合并為一棵新的二叉樹(shù)k；在上述存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)hufmtreehufmtree算法的基本步驟：第136頁(yè)/共1