數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版第六章嚴(yán)蔚敏學(xué)習(xí)教案

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)C語(yǔ)言版第六章語(yǔ)言版第六章課件嚴(yán)蔚敏課件嚴(yán)蔚敏第一頁(yè)，共134頁(yè)。6.1 樹(shù)的定義(dngy)和基本術(shù)語(yǔ)1. 樹(shù)的定義 樹(shù)是n（n0）個(gè)結(jié)點(diǎn)的有限(yuxin)集。當(dāng)n=0時(shí)，稱為空樹(shù)；在任意一棵非空樹(shù)中滿足如下條件： (1) 有且僅有一個(gè)特定的稱為根（root）的結(jié)點(diǎn)，它沒(méi)有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。 (2) 其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m0）個(gè)互不相交的有限(yuxin)集T1，T2，T3，Tm，其中Ti又是一棵樹(shù)，稱為根root的子樹(shù)。 每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。 第1頁(yè)/共134頁(yè)第二頁(yè)，共134頁(yè)。2

2、. 樹(shù)的邏輯表示法 (1) 樹(shù)型表示法。這是樹(shù)的最基本(jbn)的表示,使用一棵倒置的樹(shù)表示樹(shù)結(jié)構(gòu),非常直觀和形象。 A C G J B E D F I H M K L 樹(shù)樹(shù)形形表表示示法法 第2頁(yè)/共134頁(yè)第三頁(yè)，共134頁(yè)。l(2)文氏圖表示法。使用集合以及(yj)集合的包含關(guān)系描述樹(shù)結(jié)構(gòu)。 H L D K I M C G J E B F 文文氏氏圖圖表表示示法法 A 第3頁(yè)/共134頁(yè)第四頁(yè)，共134頁(yè)。l(3)凹入表示法。使用線段(xindun)的伸縮描述樹(shù)結(jié)構(gòu)。第4頁(yè)/共134頁(yè)第五頁(yè)，共134頁(yè)。l(4)括號(hào)表示法(廣義表表示法)。將樹(shù)的根結(jié)點(diǎn)寫在括號(hào)的左邊,除根結(jié)點(diǎn)之外的其余結(jié)

3、點(diǎn)寫在括號(hào)中并用逗號(hào)間隔(jin g)來(lái)描述樹(shù)結(jié)構(gòu)。 括括號(hào)號(hào) 表表示示法法 A(B(E,F),C(G(J),D(H,I(K,L,M) 第5頁(yè)/共134頁(yè)第六頁(yè)，共134頁(yè)。3. 樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支。 結(jié)點(diǎn)的度和樹(shù)的度(degree)：結(jié)點(diǎn)擁有的子樹(shù)個(gè)數(shù)。樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值。 葉子(leaf)和分支結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端(zhn dun)結(jié)點(diǎn)。度不為0的結(jié)點(diǎn)，也稱為非終端(zhn dun)結(jié)點(diǎn)。除根結(jié)點(diǎn)外，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。EFBAGKLMHIJCD第6頁(yè)/共134頁(yè)第七頁(yè)，共134頁(yè)。EFBAGKLMHIJCD第7頁(yè)/共134頁(yè)第八頁(yè)，

4、共134頁(yè)。l路徑與路徑長(zhǎng)度：對(duì)于任意兩個(gè)結(jié)點(diǎn)ki和kj,若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列ki,ki1,ki2,kin,kj,使得序列中除ki外的任一結(jié)點(diǎn)都是其在序列中的前一個(gè)結(jié)點(diǎn)的后繼,則稱該結(jié)點(diǎn)序列為由ki到kj的一條路徑,用路徑所通過(guò)的結(jié)點(diǎn)序列(ki,ki1,ki2,kj)表示這條路徑。路徑的長(zhǎng)度等于路徑所通過(guò)的結(jié)點(diǎn)數(shù)目減1(即路徑上分支數(shù)目)?？梢?jiàn),路徑就是從ki出發(fā)(chf)“自上而下”到達(dá)kj所通過(guò)的樹(shù)中結(jié)點(diǎn)序列。顯然,從樹(shù)的根結(jié)點(diǎn)到樹(shù)中其余結(jié)點(diǎn)均存在一條路徑。第8頁(yè)/共134頁(yè)第九頁(yè)，共134頁(yè)。l結(jié)點(diǎn)的祖先和子孫(z sn)：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)。以某結(jié)點(diǎn)為根的子樹(shù)中的任一

5、結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫(z sn)。l結(jié)點(diǎn)的層次和樹(shù)的高度(深度)：從根結(jié)點(diǎn)開(kāi)始定義，根為第一層，根的孩子為第二層，依此類推。樹(shù)中結(jié)點(diǎn)的最大層次。 EFBAGKLMHIJCD1234第9頁(yè)/共134頁(yè)第十頁(yè)，共134頁(yè)。l有序樹(shù)和無(wú)序樹(shù)：在樹(shù)中，如果各子樹(shù)Ti是按照一定的次序從左向右安排的，且相對(duì)次序是不能隨意改變的，則稱為有序樹(shù)，否則稱為無(wú)序樹(shù)。ll森林： m（m0）棵互不相交的樹(shù)的集合(jh)。將一棵非空樹(shù)的根結(jié)點(diǎn)刪去，樹(shù)就變成一個(gè)森林；反之，給m棵獨(dú)立的樹(shù)增加一個(gè)根結(jié)點(diǎn)，并把這m棵樹(shù)作為該結(jié)點(diǎn)的子樹(shù)，森林就變成一棵樹(shù)。第10頁(yè)/共134頁(yè)第十一頁(yè)，共134頁(yè)。森林(snln)樹(shù)屬于(sh

6、y)森林。樹(shù)是一個(gè)二元組 Tree = ( root ，F(xiàn) ) 。root : 根結(jié)點(diǎn)(ji din)。F : m(m0)棵樹(shù)的森林，F(xiàn) = (T1,T2,Tm)。Ti 稱為 root 的第 i 棵子樹(shù)。ABCDEFGIHJ第11頁(yè)/共134頁(yè)第十二頁(yè)，共134頁(yè)。 樹(shù)的運(yùn)算主要分為(fn wi)三大類： 第一類,尋找滿足某種特定關(guān)系的結(jié)點(diǎn),如尋找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等； 第二類,插入或刪除某個(gè)結(jié)點(diǎn),如在樹(shù)的當(dāng)前結(jié)點(diǎn)上插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)等； 第三類,遍歷樹(shù)中每個(gè)結(jié)點(diǎn),這里著重介紹。4.樹(shù)的基本(jbn)運(yùn)算第12頁(yè)/共134頁(yè)第十三頁(yè)，共134頁(yè)。6.2 二 叉 樹(shù) 1

7、. 二叉樹(shù)的定義(dngy) 滿足以下兩個(gè)條件的樹(shù)形結(jié)構(gòu)叫做(jiozu)二叉樹(shù)（Binary Tree）： （1） 每個(gè)結(jié)點(diǎn)的度都不大于2； （2） 每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。 由此定義可以看出，一個(gè)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)只能含有0、 1或2個(gè)孩子，而且每個(gè)孩子有左右之分。把位于左邊的孩子叫做(jiozu)左孩子，位于右邊的孩子叫做(jiozu)右孩子。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完完 全全 二二 叉叉 樹(shù)樹(shù) 第13頁(yè)/共134頁(yè)第十四頁(yè)，共134頁(yè)。二叉樹(shù)的五種(w zhn)基本形態(tài) (a) 空二叉樹(shù)(b) 只有根結(jié)點(diǎn)

8、 的二叉樹(shù)(c) 只有左子樹(shù) 的二叉樹(shù)(d) 左右子樹(shù)均非 空的二叉樹(shù)(e) 只有右子樹(shù)的二叉樹(shù)第14頁(yè)/共134頁(yè)第十五頁(yè)，共134頁(yè)。2. 二叉樹(shù)的性質(zhì)(xngzh) l性質(zhì)1: 在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i1)。 l 證明： 用數(shù)學(xué)歸納法。 l 1) 當(dāng)i=1時(shí)，整個(gè)二叉樹(shù)只有一根結(jié)點(diǎn)，此時(shí)2i-1=20=1，l結(jié)論成立(chngl)。l 2) 設(shè)i=k時(shí)結(jié)論成立(chngl)，即第k層上結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)。l 現(xiàn)證明當(dāng)i=k+1時(shí)， 結(jié)論成立(chngl)：l 因?yàn)槎鏄?shù)中每個(gè)結(jié)點(diǎn)的度最大為2，則第k+1層的結(jié)點(diǎn)l總數(shù)最多為第k層上結(jié)點(diǎn)最大數(shù)的2倍，即22k-1=2

9、(k+1)-1，l故結(jié)論成立(chngl)。 度為m的樹(shù)中第i層上至多(zhdu)有mi-1個(gè)結(jié)點(diǎn), (i1)。第15頁(yè)/共134頁(yè)第十六頁(yè)，共134頁(yè)。l性質(zhì)2: 深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（k1）。 l 證明：因?yàn)樯疃葹閗的二叉樹(shù)，其結(jié)點(diǎn)總數(shù)(zngsh)的最大值是將二叉樹(shù)每層上結(jié)點(diǎn)的最大值相加，所以深度為k的二叉樹(shù)的結(jié)點(diǎn)總數(shù)(zngsh)至多為 kikikii111122層上的最大結(jié)點(diǎn)個(gè)數(shù)第深度為k的m叉樹(shù)至多(zhdu)有 個(gè)結(jié)點(diǎn)。11kmm101111.1kkikimmmmmm第16頁(yè)/共134頁(yè)第十七頁(yè)，共134頁(yè)。l 性質(zhì)3: 對(duì)任意一棵二叉樹(shù)，若終端結(jié)點(diǎn)數(shù)為n0，度為

10、l2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。l 證明：設(shè)二叉樹(shù)中結(jié)點(diǎn)總數(shù)為n，n1為二叉樹(shù)中度為1l的結(jié)點(diǎn)總數(shù)，設(shè)二叉樹(shù)中分支數(shù)目為B 。l n=n0+n1+n2l 除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)(y )進(jìn)入它的分支：l n=B+1l 二叉樹(shù)中的分支都是由度為1和度為2的結(jié)點(diǎn)發(fā)出l B=n1+2n2第17頁(yè)/共134頁(yè)第十八頁(yè)，共134頁(yè)。l滿二叉樹(shù)： 深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。在滿二叉樹(shù)中，每層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。 滿二叉樹(shù)的順序表示，即從二叉樹(shù)的根開(kāi)始， 層間從上到下， 層內(nèi)從左到右，逐層進(jìn)行(jnxng)編號(hào)（1， 2， ， n）。 A B C D E H I

11、J K F G L M N O 1 2 3 4 5 6 7 8 9 10 15 11 12 13 14 滿滿二二叉叉樹(shù)樹(shù) 第18頁(yè)/共134頁(yè)第十九頁(yè)，共134頁(yè)。l完全二叉樹(shù)：l 深度為k，結(jié)點(diǎn)數(shù)為n的二叉樹(shù)，如果其結(jié)點(diǎn)1n的位置(wi zhi)序號(hào)分別與滿二叉樹(shù)的結(jié)點(diǎn)1n的位置(wi zhi)序號(hào)一一對(duì)應(yīng)，則為完全二叉樹(shù)，l 滿二叉樹(shù)必為完全二叉樹(shù)， 而完全二叉樹(shù)不一定是滿二叉樹(shù)。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完完 全全 二二 叉叉 樹(shù)樹(shù) 第19頁(yè)/共134頁(yè)第二十頁(yè)，共134頁(yè)。l 性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度(s

12、hnd)為l log2n+1或log2(n+1)。 l 證明：設(shè)n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度(shnd)為k，根據(jù)l性質(zhì)2有 2k-1-1n 2k-1l 可得 2k-1n 2k，l 即 k-1log2n k l 因?yàn)閗是整數(shù)，所以k-1= log2n，k= log2n+1,l故結(jié)論成立。 l 2k-1n +12k k-1 log2(n+1) k l k= log2(n+1) 第20頁(yè)/共134頁(yè)第二十一頁(yè)，共134頁(yè)。l性質(zhì)5:對(duì)完全二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)(1in,n1,n為結(jié)點(diǎn)數(shù))有：l(1)若i=1,則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親。l 若i1,則它的雙親結(jié)點(diǎn)的編號(hào)為i/2。當(dāng)i為偶數(shù)(u sh

13、)時(shí),其雙親結(jié)點(diǎn)的編號(hào)為i/2,它是雙親結(jié)點(diǎn)的左孩子結(jié)點(diǎn),當(dāng)i為奇數(shù)時(shí),其雙親結(jié)點(diǎn)的編號(hào)為(i-1)/2,它是雙親結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完完 全全 二二 叉叉 樹(shù)樹(shù) 第21頁(yè)/共134頁(yè)第二十二頁(yè)，共134頁(yè)。(2)若編號(hào)(bin ho)為i的結(jié)點(diǎn)有左孩子結(jié)點(diǎn),則左孩子結(jié)點(diǎn)的編號(hào)(bin ho)為2i；若編號(hào)(bin ho)為i的結(jié)點(diǎn)有右孩子結(jié)點(diǎn),則右孩子結(jié)點(diǎn)的編號(hào)(bin ho)為(2i+1)。當(dāng)2in，則結(jié)點(diǎn)i無(wú)左孩子，無(wú)左孩子則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)；當(dāng)2i+1n，則結(jié)點(diǎn)無(wú)右孩子。 A B C D E H

14、 I J K F G 1 2 3 4 5 6 7 8 9 1 0 11 完完 全全 二二 叉叉 樹(shù)樹(shù) 第22頁(yè)/共134頁(yè)第二十三頁(yè)，共134頁(yè)。(3)若n為奇數(shù),則每個(gè)分支結(jié)點(diǎn)都既有左孩子結(jié)點(diǎn),也有右孩子結(jié)點(diǎn)；若n為偶數(shù),則編號(hào)最大的分支結(jié)點(diǎn)(編號(hào)為n/2)只有(zhyu)左孩子結(jié)點(diǎn),沒(méi)有右孩子結(jié)點(diǎn),其余分支結(jié)點(diǎn)都有左、右孩子結(jié)點(diǎn)。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 1 0 11 完完 全全 二二 叉叉 樹(shù)樹(shù) 第23頁(yè)/共134頁(yè)第二十四頁(yè)，共134頁(yè)。3. 二叉樹(shù)的存儲(chǔ)(cn ch)結(jié)構(gòu) 二叉樹(shù)的存儲(chǔ)(cn ch)結(jié)構(gòu)有兩種： 順序存儲(chǔ)(cn

15、ch)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)(cn ch)結(jié)構(gòu)。 l順序存儲(chǔ)結(jié)構(gòu)(jigu) A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完完全全二二叉叉樹(shù)樹(shù) A B C D E F G H I J K編號(hào)從小到大的順序就是結(jié)點(diǎn)存放在連續(xù)存儲(chǔ)單元的先后次序完全二叉樹(shù): 編號(hào)為 i 的元素存儲(chǔ)在數(shù)組下標(biāo)為 i-1 的分量中；第24頁(yè)/共134頁(yè)第二十五頁(yè)，共134頁(yè)。ABCD(a) 單支二叉樹(shù)ABCD(b) 順 序 存 儲(chǔ) 結(jié) 構(gòu)13715一般二叉樹(shù): 對(duì)照完全二叉樹(shù)，存儲(chǔ)在數(shù)組的相應(yīng)(xingyng)分量中；在最壞情況(qngkung)下，深度為 k 的右單支二叉樹(shù)需要

16、 2k-1 個(gè)存儲(chǔ)空間。第25頁(yè)/共134頁(yè)第二十六頁(yè)，共134頁(yè)。l二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)ltypedef struct BiTNode l ElemType data;l struct BiTNode *lchild,*rchild;l BiTNode, *BiTree;ldata表示(biosh)值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素,llchild和rchild分別表示(biosh)左指針域和右指針域,用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)(即左、右子樹(shù)的根結(jié)點(diǎn))的存儲(chǔ)位置。第26頁(yè)/共134頁(yè)第二十七頁(yè)，共134頁(yè)。 A B C E F D G A B C D E F G (a) (b) l二叉樹(shù)及

17、其鏈?zhǔn)酱鎯?chǔ)(cn ch)結(jié)構(gòu) n1個(gè)空鏈域，分支(fnzh)數(shù)目B=n-1，即非空的鏈域有n-1個(gè)，故空鏈域有2n-(n-1)=n+1個(gè)。 第27頁(yè)/共134頁(yè)第二十八頁(yè)，共134頁(yè)。第28頁(yè)/共134頁(yè)第二十九頁(yè)，共134頁(yè)。6.3 遍歷(bin l)二叉樹(shù)和線索二叉樹(shù) 1.二叉樹(shù)遍歷的概念 二叉樹(shù)的遍歷是指按照一定次序訪問(wèn)樹(shù)中所有(suyu)結(jié)點(diǎn),并且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次的過(guò)程。它是最基本的運(yùn)算,是二叉樹(shù)中所有(suyu)其他運(yùn)算的基礎(chǔ)。LChildDataRChildLChildRChildData第29頁(yè)/共134頁(yè)第三十頁(yè)，共134頁(yè)。用L、D、R分別表示遍歷左子樹(shù)、訪問(wèn)(fngwn

18、)根結(jié)點(diǎn)、 遍歷右子樹(shù)， 二叉樹(shù)的遍歷順序就可以有六種方式： 訪問(wèn)(fngwn)根，遍歷左子樹(shù)，遍歷右子樹(shù)（記做DLR）。訪問(wèn)(fngwn)根，遍歷右子樹(shù)，遍歷左子樹(shù)（記做DRL）。遍歷左子樹(shù)，訪問(wèn)(fngwn)根，遍歷右子樹(shù)（記做LDR）。遍歷左子樹(shù)，遍歷右子樹(shù)，訪問(wèn)(fngwn)根（記做LRD）。遍歷右子樹(shù)，訪問(wèn)(fngwn)根，遍歷左子樹(shù)（記做RDL）。遍歷右子樹(shù)，遍歷左子樹(shù)，訪問(wèn)(fngwn)根（記做RLD）。 第30頁(yè)/共134頁(yè)第三十一頁(yè)，共134頁(yè)。三種(sn zhn)遍歷方法的遞歸定義先序遍歷（DLR）操作過(guò)程：若二叉樹(shù)為空， 則空操作， 否則 (1) 訪問(wèn)根結(jié)點(diǎn)； (2) 按

19、先序遍歷左子樹(shù)； (3) 按先序遍歷右子樹(shù)。中序遍歷（LDR）操作過(guò)程： 若二叉樹(shù)為空，則空操作，否則： (1) 按中序遍歷左子樹(shù)； (2) 訪問(wèn)根結(jié)點(diǎn)； (3) 按中序遍歷右子樹(shù)。 第31頁(yè)/共134頁(yè)第三十二頁(yè)，共134頁(yè)。l后序遍歷（LRD）操作過(guò)程： l 若二叉樹(shù)為空， 則空操作， 否則(fuz)： l (1) 按后序遍歷左子樹(shù)； l (2) 按后序遍歷右子樹(shù)； l (3) 訪問(wèn)根結(jié)點(diǎn)。 第32頁(yè)/共134頁(yè)第三十三頁(yè)，共134頁(yè)。 先序遍歷(bin l)： A、 B、 D、 F、 G、 C、 E、 H 。 中序遍歷(bin l)： B、 F、 D、 G、 A、 C、 E、 H 。 后

20、序遍歷(bin l)： F、 G、 D、 B、 H、 E、 C、 A 。 CEHGFBDA第33頁(yè)/共134頁(yè)第三十四頁(yè)，共134頁(yè)。l算術(shù)(sunsh)式的二叉樹(shù)表示 /edcb*a前綴： -+a*bc/de（波蘭(b ln)表達(dá)式）中綴： a+b*c-d/e 后綴： abc*+de/-（逆波蘭(b ln)表達(dá)式）a+b*c-d/e第34頁(yè)/共134頁(yè)第三十五頁(yè)，共134頁(yè)。2. 二叉樹(shù)遍歷遞歸算法先序遍歷的遞歸算法void PreOrderTraverse(BiTree T) if (T!=NULL) printf(%c ,T-data); /*訪問(wèn)(fngwn)根結(jié)點(diǎn)*/ PreOrde

21、rTraverse(T-lchild); PreOrderTraverse(T-rchild); 第35頁(yè)/共134頁(yè)第三十六頁(yè)，共134頁(yè)。l中序遍歷的遞歸算法lvoid InOrderTraverse(BiTree T) l l if (T!=NULL) l l InOrderTraverse(T-lchild);l printf(%c ,T-data); /*訪問(wèn)(fngwn)根結(jié)點(diǎn)*/l InOrderTraverse(T-rchild);ll 第36頁(yè)/共134頁(yè)第三十七頁(yè)，共134頁(yè)。l后序遍歷遞歸算法(sun f)lvoid PostOrderTraverse(BiTree T)

22、 l if (T!=NULL) l l PostOrderTraverse(T-lchild);l PostOrderTraverse(T-rchild);l printf(%c ,T-data); /*訪問(wèn)根結(jié)點(diǎn)*/ll 第37頁(yè)/共134頁(yè)第三十八頁(yè)，共134頁(yè)。ABDCE(a) 二叉樹(shù)的遍歷走向BD第一次經(jīng)過(guò)第二次經(jīng)過(guò)第三次經(jīng)過(guò)(b) 遍歷中三次經(jīng)過(guò)結(jié)點(diǎn)的情形第38頁(yè)/共134頁(yè)第三十九頁(yè)，共134頁(yè)。 void XXTraverse(BiTree T) /遍歷(bin l)二叉樹(shù)的遞歸算法 if (T!=NULL) XXTraverse(T-lchild); XXTraverse(T-

23、rchild); printf(%c ,T-data); /*訪問(wèn)根結(jié)點(diǎn)*/將遞歸算法(sun f)轉(zhuǎn)變?yōu)榈葍r(jià)的非遞歸算法(sun f)，應(yīng)設(shè)置棧。第39頁(yè)/共134頁(yè)第四十頁(yè)，共134頁(yè)。l先序遍歷void PreOrderTraverse(BiTree T)ll 將根結(jié)點(diǎn)(ji din)進(jìn)棧；l while(棧不空)l 出棧p;l 訪問(wèn)p;l 其右孩子不空時(shí)，右孩子進(jìn)棧；l 其左孩子不空時(shí)，左孩子進(jìn)棧；l l第40頁(yè)/共134頁(yè)第四十一頁(yè)，共134頁(yè)。l先序遍歷(bin l)void PreOrderTraverse(BiTree T)ll InitStack(S);l Push(S,T)

24、;l while(!StackEmpty(S)l Pop(S,p);l coutdatarchild) Push(S, p-rchild);l if(p-lchild) Push(S, p-lchild);l l第41頁(yè)/共134頁(yè)第四十二頁(yè)，共134頁(yè)。l中序遍歷(bin l)void InOrderTraverse(BiTree T)l InitStack(S); p = T;l while( p | !StackEmpty(S)l if(p) l Push(S, p); p = p-lchild; l l elsel Pop(S, p); coutdatarchild;l l l第42頁(yè)

25、/共134頁(yè)第四十三頁(yè)，共134頁(yè)。l后序遍歷void PostOrderTraverse(BiTree T)ltypedef struct BiTree ptr; enum 0,1,2 mark;l StackNode; lmark=0表示(biosh)剛剛訪問(wèn)此結(jié)點(diǎn),lmark=1表示(biosh)左子樹(shù)處理結(jié)束返回,lmark=2表示(biosh)右子樹(shù)處理結(jié)束返回.l每次根據(jù)棧頂元素的mark域值決定做何種動(dòng)作. 第43頁(yè)/共134頁(yè)第四十四頁(yè)，共134頁(yè)。l后序(hu x)遍歷void PostOrderTraverse(BiTree T)l StackNode a; InitSta

26、ck(S); Push (S,T,0); /根結(jié)點(diǎn)入棧l while( !StackEmpty(S) ) l Pop( S, a);l switch( a.mark ) l case 0:l Push(S,a.ptr,1); l if(a.ptr-lchild) Push(S,a.ptr-lchild,0); break;l case 1:l Push(S,a.ptr,2); l if(a.ptr-rchild) Push(S,a.ptr-rchild,0); break;l case 2:l coutdatadata=ch; l CreateBiTree(T-lchild); l Creat

27、eBiTree(T-rchild); l l 第49頁(yè)/共134頁(yè)第五十頁(yè)，共134頁(yè)。3. 線索(xin su)二叉樹(shù) 有2n-(n-1)=n+1個(gè)空鏈域一、將二叉樹(shù)遍歷(bin l)一遍，在遍歷(bin l)過(guò)程中便可得到結(jié)點(diǎn)的前驅(qū)和后繼，但這種動(dòng)態(tài)訪問(wèn)浪費(fèi)時(shí)間；二、充分利用二叉鏈表中的空鏈域， 將遍歷(bin l)過(guò)程中結(jié)點(diǎn)的前驅(qū)、 后繼信息保存下來(lái)。第50頁(yè)/共134頁(yè)第五十一頁(yè)，共134頁(yè)。lchildLtagDataRtagrchild0 lchild域指示結(jié)點(diǎn)的左孩子1lchild域指示結(jié)點(diǎn)的遍歷前驅(qū)0 rchild域指示結(jié)點(diǎn)的右孩子1 rchild域指示結(jié)點(diǎn)的遍歷后繼 LTag

28、=RTag=指向前驅(qū)和后繼結(jié)點(diǎn)的指針叫做線索。 以這種結(jié)構(gòu)組成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，叫做線索鏈表。對(duì)二叉樹(shù)以某種次序進(jìn)行(jnxng)遍歷并且加上線索的過(guò)程叫做線索化。線索化了的二叉樹(shù)稱為線索二叉樹(shù)。第51頁(yè)/共134頁(yè)第五十二頁(yè)，共134頁(yè)。typedef struct BiThrNode TElemType data; /*結(jié)點(diǎn)數(shù)據(jù)域*/ int LTag, RTag; /*增加的線索標(biāo)記(bioj)*/ struct BiThrNode *lchild;/*左孩子或線索指針*/ struct BiThrNode *rchild;/*右孩子或線索指針*/BiThrNode, *B

29、iThrTree; /*線索樹(shù)結(jié)點(diǎn)類型定義*/ 第52頁(yè)/共134頁(yè)第五十三頁(yè)，共134頁(yè)。ABCDEFGH(a) 二叉 樹(shù)ABCDEFGH(b )先序線索二叉 樹(shù)ACDEFGH(c) 中序線索二叉樹(shù)ABCDEFGH(d ) 后序線索二叉 樹(shù)BN U LLN U LLN U LLN U LLABDGCEHFDGBAEHCFGDBHEFCA第53頁(yè)/共134頁(yè)第五十四頁(yè)，共134頁(yè)。l訪問(wèn)線索二叉樹(shù)l(1)中序線索二叉樹(shù)中，查找指定結(jié)點(diǎn)(ji din)的前驅(qū)和后繼l找結(jié)點(diǎn)(ji din)的中序前驅(qū)結(jié)點(diǎn)(ji din)l 結(jié)點(diǎn)(ji din)p，無(wú)左孩子，左指針指向其前驅(qū)，否則p的l 左子樹(shù)“最右

30、下”結(jié)點(diǎn)(ji din)。lBiThrTree PreNode(BiThrTree p)ll pre = p-lchild;l if(p-LTag = 0) /有左孩子l while(pre-RTag = 0)l pre = pre-rchild;l return pre;l第54頁(yè)/共134頁(yè)第五十五頁(yè)，共134頁(yè)。找結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)結(jié)點(diǎn)p，無(wú)右孩子(hi zi)，右指針指向其后繼，否則p的右子樹(shù)中“最左下”結(jié)點(diǎn)。BiThrTree PostNode(BiThrTree p) post = p-rchild; if(p-RTag = 0) /有右孩子(hi zi) while(post-L

31、Tag = 0) post = post-lchild; return post;第55頁(yè)/共134頁(yè)第五十六頁(yè)，共134頁(yè)。 0 1 0 + 0 1 a 1 1 b 1 Thrt l帶頭結(jié)點(diǎn)(ji din)的線索二叉鏈表帶頭(di tu)結(jié)點(diǎn)的中序線索二叉鏈表第56頁(yè)/共134頁(yè)第五十七頁(yè)，共134頁(yè)。第57頁(yè)/共134頁(yè)第五十八頁(yè)，共134頁(yè)。(2)后序線索二叉樹(shù)中，查找指定(zhdng)結(jié)點(diǎn)的前驅(qū)和后繼找結(jié)點(diǎn)的后序前驅(qū)結(jié)點(diǎn) if(p-LTag = 1) pre = p-lchild;/無(wú)左孩子 if(p-LTag = 0) /有左孩子 if(p-RTag = 0) pre = p-rch

32、ild; /右孩子為前驅(qū) if(p-RTag = 1) pre = p-lchild; /左孩子為前驅(qū) 從該結(jié)點(diǎn)出發(fā)就能找到。 第58頁(yè)/共134頁(yè)第五十九頁(yè)，共134頁(yè)。找結(jié)點(diǎn)的后序后繼結(jié)點(diǎn) （需要知道該結(jié)點(diǎn)的雙親）P為根結(jié)點(diǎn)， 則無(wú)后繼結(jié)點(diǎn)；p無(wú)右孩子， If(p-RTag = 1) post = p-rchild;若p是雙親的右孩子， 則雙親為p的后繼結(jié)點(diǎn)；若p是雙親的左孩子，且p沒(méi)有右兄弟(xingd)， 則雙親為其后繼結(jié)點(diǎn)；若p是雙親的左孩子，且p有右兄弟(xingd)， 則p的后繼是其雙親右子樹(shù)中第一個(gè)后序遍歷到的結(jié) 點(diǎn)。第59頁(yè)/共134頁(yè)第六十頁(yè)，共134頁(yè)。(3)先序線索二叉

33、樹(shù)中，查找指定結(jié)點(diǎn)的前驅(qū)和后繼找結(jié)點(diǎn)的先序前驅(qū)結(jié)點(diǎn) 需知道(zh do)該結(jié)點(diǎn)的雙親；找結(jié)點(diǎn)的先序后繼結(jié)點(diǎn) 從該結(jié)點(diǎn)出發(fā)就能找到。 第60頁(yè)/共134頁(yè)第六十一頁(yè)，共134頁(yè)。 0 1 0 + 0 1 a 1 1 b 1 Thrt 第61頁(yè)/共134頁(yè)第六十二頁(yè)，共134頁(yè)。Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) Thrt = (BiThrTree)malloc(sizeof(BiThrNode); /創(chuàng)建頭結(jié)點(diǎn) Thrt-LTag=0; Thrt-RTag=1; Thrt-rchild=Thrt; if (!T) Thrt-

34、lchild=Thrt; /空二叉樹(shù) else Thrt-lchild = T;pre = Thrt; /pre: 剛剛(gng gng)訪問(wèn)過(guò)的結(jié)點(diǎn)； InThreading(T); pre-rchild=Thrt; pre-RTag=1;Thrt-rchild=pre; return OK; 第62頁(yè)/共134頁(yè)第六十三頁(yè)，共134頁(yè)。 BiThrTree pre = Thrt; /*全局變量,剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)*/ void InThreading(BiThrTree p) if (p) InThreading(p-lchild); /*左子樹(shù)線索(xin su)化*/ if (!p-lc

35、hild) /*前驅(qū)線索(xin su)*/ p-lchild=pre; p-LTag=1; else p-LTag=0; if (!pre-rchild) /*后繼線索(xin su)*/ pre-rchild=p; pre-rtag=1; else pre-rtag=0; pre = p; InThreading(p-rchild); /*右子樹(shù)線索(xin su)化*/ 第63頁(yè)/共134頁(yè)第六十四頁(yè)，共134頁(yè)。第64頁(yè)/共134頁(yè)第六十五頁(yè)，共134頁(yè)。第65頁(yè)/共134頁(yè)第六十六頁(yè)，共134頁(yè)。6.4 樹(shù)和森林(snln) 1. 樹(shù)的存儲(chǔ)結(jié)構(gòu)(jigu)（三種方法） l雙親表示法：

36、用一組連續(xù)的空間來(lái)存儲(chǔ)樹(shù)中的結(jié)點(diǎn)，在保存每個(gè)結(jié)點(diǎn)的同時(shí)附設(shè)(fsh)一個(gè)指示器來(lái)指示其雙親結(jié)點(diǎn)在表中的位置， 其結(jié)點(diǎn)的結(jié)構(gòu)如下： DataParent第66頁(yè)/共134頁(yè)第六十七頁(yè)，共134頁(yè)。 A D B C G E F A -1 B 0 C 0 D 0 E 2 F 2 G 2 0 1 2 3 4 5 6 (a) (b) 樹(shù)的雙親存儲(chǔ)(cn ch)結(jié)構(gòu)示意圖第67頁(yè)/共134頁(yè)第六十八頁(yè)，共134頁(yè)。define MAX_TREE_SIZE 100typedef struct PTNode TElemType data; int parent; PTNode; Typedef struct

37、PTNode nodesMAX_TREE_SIZE; int r, n; /根的位置(wi zhi)和結(jié)點(diǎn)數(shù)PTree;雙親(shungqn)表示法的類型說(shuō)明：第68頁(yè)/共134頁(yè)第六十九頁(yè)，共134頁(yè)。l孩子表示法：定長(zhǎng)結(jié)點(diǎn)長(zhǎng)度 l空鏈域個(gè)數(shù)：nk (n-1) = n(k-1)+1.l把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，構(gòu)成一個(gè)單鏈表， 稱為孩子鏈表。n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表（葉子(y zi)結(jié)點(diǎn)的孩子鏈表為空表），而n個(gè)結(jié)點(diǎn)的數(shù)據(jù)和n個(gè)孩子鏈表的頭指針又組成一個(gè)順序表。 A D B C G E F (a) A B C D E F G 0 1 2 3 4 5 6 (b) 1 2 3 4 5 6 第

38、69頁(yè)/共134頁(yè)第七十頁(yè)，共134頁(yè)。 typedef struct CTNode /* 孩子結(jié)點(diǎn)(ji din)的定義 */ int Child; /* 該孩子結(jié)點(diǎn)(ji din)在線性表中的位置 */ struct CTNode *next; /* 指向下一個(gè)孩子結(jié)點(diǎn)(ji din)的指針 */*ChildPtr;typedef struct /* 順序表結(jié)點(diǎn)(ji din)的結(jié)構(gòu)定義 */ TElemType data; /* 結(jié)點(diǎn)(ji din)的信息 */ ChildPtr FirstChild ; /* 指向孩子鏈表的頭指針 */CTBox;typedef struct /* 樹(shù)

39、的定義 */ CTBox nodesMAX_TREE_SIZE; /* 順序表 */ int root, num; /* 根結(jié)點(diǎn)(ji din)的位置和樹(shù)的結(jié)點(diǎn)(ji din)個(gè)數(shù) */ CTree; 第70頁(yè)/共134頁(yè)第七十一頁(yè)，共134頁(yè)。l孩子(hi zi)兄弟表示法typedef struct CSNode ElemType data; /*結(jié)點(diǎn)信息*/ Struct CSNode *FirstChild, *NextSibling; /*第一個(gè)孩子, 下一個(gè)兄弟(xingd)*/CSNode, *CSTree; 這種存儲(chǔ)結(jié)構(gòu)便于實(shí)現(xiàn)樹(shù)的各種操作。第71頁(yè)/共134頁(yè)第七十二頁(yè)，共1

40、34頁(yè)。 A B C F D E (a) G A B D C E G F (b) 樹(shù)的孩子(hi zi)兄弟鏈存儲(chǔ)結(jié)構(gòu)示意圖第72頁(yè)/共134頁(yè)第七十三頁(yè)，共134頁(yè)。2. 樹(shù)、森林與二叉樹(shù)的相互(xingh)轉(zhuǎn)換 l樹(shù)轉(zhuǎn)換(zhunhun)為二叉樹(shù) (1)在所有相鄰兄弟結(jié)點(diǎn)之間加一水平連線。(2)對(duì)每個(gè)非葉結(jié)點(diǎn)k,除了其最左邊的孩子結(jié)點(diǎn)外,刪去k與其他孩子結(jié)點(diǎn)的連線。(3)所有水平線段以左邊結(jié)點(diǎn)為軸心順時(shí)針旋轉(zhuǎn)45度，使之結(jié)構(gòu)層次分明。樹(shù)做這樣的轉(zhuǎn)換(zhunhun)所構(gòu)成的二叉樹(shù)是唯一的。第73頁(yè)/共134頁(yè)第七十四頁(yè)，共134頁(yè)。ABDEFCGHABDEFCGHABDEFCHG第74頁(yè)/

41、共134頁(yè)第七十五頁(yè)，共134頁(yè)。DABCE對(duì)應(yīng)ABCDEABCDEEABCDABCDE存儲(chǔ)存儲(chǔ)解釋解釋樹(shù)與二叉樹(shù)的對(duì)應(yīng)(duyng)第75頁(yè)/共134頁(yè)第七十六頁(yè)，共134頁(yè)。l森林轉(zhuǎn)換為二叉樹(shù)l 森林也可以方便地用孩子兄弟鏈表表示。森林轉(zhuǎn)換為二叉樹(shù)的方法如下： l （1）將森林中的每棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)。l （2）第一棵二叉樹(shù)不動(dòng)，從第二棵二叉樹(shù)開(kāi)始(kish)，依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子， 當(dāng)所有二叉樹(shù)連在一起后，所得到的二叉樹(shù)就是由森林轉(zhuǎn)換得到的二叉樹(shù)。 第76頁(yè)/共134頁(yè)第七十七頁(yè)，共134頁(yè)。ABCDEFGHIJ(a) 森林ABCDEFGHIJ(b

42、) 森林中每棵樹(shù)對(duì)應(yīng)的二叉樹(shù)ABEFGHIHCD(c) 森林對(duì)應(yīng)的二叉樹(shù)第77頁(yè)/共134頁(yè)第七十八頁(yè)，共134頁(yè)。l二叉樹(shù)還原為樹(shù)或森林l將一棵二叉樹(shù)還原為樹(shù)或森林，具體方法如下： l （1） 若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、 右孩子的右孩子都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來(lái)。 l （2） 刪掉原二叉樹(shù)中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線(lin xin)。 l （3） 整理由（1）、（2）兩步所得到的樹(shù)或森林， 使之結(jié)構(gòu)層次分明。 第78頁(yè)/共134頁(yè)第七十九頁(yè)，共134頁(yè)。ABECFGHIJD(a) 添加連線ABECFGHIJD(b) 刪除右孩子結(jié)點(diǎn)的連線ABCDEFGHIJ(c)

43、 整理二叉樹(shù)到森林(snln)的轉(zhuǎn)換示例第79頁(yè)/共134頁(yè)第八十頁(yè)，共134頁(yè)。3. 樹(shù)與森林(snln)的遍歷 l樹(shù)的遍歷（兩種）l1） 先根遍歷l若樹(shù)非空，則遍歷方法為： l訪問(wèn)根結(jié)點(diǎn)(ji din)。 l從左到右， 依次先根遍歷根結(jié)點(diǎn)(ji din)的每一棵子樹(shù)。 ACBDEFGH先根遍歷(bin l)序列ABECFHGD等同于轉(zhuǎn)換的二叉樹(shù)進(jìn)行先序遍歷第80頁(yè)/共134頁(yè)第八十一頁(yè)，共134頁(yè)。2后根遍歷若樹(shù)非空， 則遍歷方法為： 從左到右， 依次(yc)后根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。 訪問(wèn)根結(jié)點(diǎn)。 ACBDEFGH后根遍歷(bin l)序列為EBHFGCDA等同于轉(zhuǎn)換(zhunhun)

44、的二叉樹(shù)進(jìn)行中序遍歷第81頁(yè)/共134頁(yè)第八十二頁(yè)，共134頁(yè)。l森林的遍歷（2種）ll1） 先序遍歷l若森林非空， 則遍歷方法為： l訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)。 l先序遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林。 l先序遍歷除去第一棵樹(shù)之后(zhhu)剩余的樹(shù)構(gòu)成的森林。 l 先序遍歷(bin l)序列為ABCDEFGHIJ等同于轉(zhuǎn)換的二叉樹(shù)進(jìn)行(jnxng)先序遍歷第82頁(yè)/共134頁(yè)第八十三頁(yè)，共134頁(yè)。2） 中序遍歷若森林非空， 則遍歷方法(fngf)為： 中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林。 訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)。 中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。 中序遍歷(bin l)序

45、列為BCDAFEHJIG等同于轉(zhuǎn)換(zhunhun)的二叉樹(shù)進(jìn)行中序遍歷第83頁(yè)/共134頁(yè)第八十四頁(yè)，共134頁(yè)。第84頁(yè)/共134頁(yè)第八十五頁(yè)，共134頁(yè)。給定樹(shù)的先根遍歷序列(xli)和后根遍歷序列(xli)可唯一畫出一棵樹(shù)。先根遍歷序列(xli)：A B E C F H G D后根遍歷序列(xli)：E B H F G C D AACBDEFGH第85頁(yè)/共134頁(yè)第八十六頁(yè)，共134頁(yè)。給定(i dn)森林的先序遍歷序列和中序遍歷序列可唯一確定一森林。 先序遍歷序列：A B C D E F G H I J中序遍歷序列：B C D A F E H J I G第86頁(yè)/共134頁(yè)第八十七

46、頁(yè)，共134頁(yè)。關(guān)于二叉樹(shù)的先序、中序和后序遍歷序列確定(qudng)二叉樹(shù)的問(wèn)題。l任何n(n0)個(gè)不同結(jié)點(diǎn)的二叉樹(shù),都可由它的中序序列和先序序列唯一(wi y)地確定。l證明：l先序序列是a1a2anl中序序列是b1b2bnl根結(jié)點(diǎn)：a1。l在中序序列中與a1相同的結(jié)點(diǎn)為：bj。l b1bj-1bjbj+1bn a1a2akak+1an第87頁(yè)/共134頁(yè)第八十八頁(yè)，共134頁(yè)。例：已知先序序列(xli)為ABDGCEF,中序序列(xli)為DGBAECF根結(jié)點(diǎn)(ji din)：G左先序:空 左中序:空右先序:空 右中序:空根結(jié)點(diǎn)(ji din)：A左先序:BDG 左中序:DGB右先序:C

47、EF 右中序:ECF根結(jié)點(diǎn)：B左先序:DG 左中序:DG右先序:空 右中序:空根結(jié)點(diǎn)：D左先序:空 左中序:空右先序:G 右中序:G根結(jié)點(diǎn)：C左先序:E 左中序:E右先序:F 右中序:F根結(jié)點(diǎn)：E左先序:空 左中序:空右先序:空 右中序:空根結(jié)點(diǎn)：F左先序:空 左中序:空右先序:空 右中序:空第88頁(yè)/共134頁(yè)第八十九頁(yè)，共134頁(yè)。由先序、中序序列構(gòu)造二叉樹(shù)的算法(sun f)：BiTNode *CreateBT1(char *pre,char *in,int n) BiTNode *s; char *p; int k; if(n=1)s=malloc();s-lchild=s-rchil

48、d=NULL;return s; for (p=in;pdata=*pre; s-lchild=s-rchild=NULL; if(k) s-lchild = CreateBT1(pre+1,in,k);/左子樹(shù) if(n-k-1) s-rchild = CreateBT1(pre+k+1,p+1,n-k-1);/右子樹(shù) return s; 先序：ABDGCEF中序：DGBAECF第89頁(yè)/共134頁(yè)第九十頁(yè)，共134頁(yè)。l任何n(n0)個(gè)不同結(jié)點(diǎn)的二叉樹(shù),都可由它的中序序列和后序(hu x)序列唯一地確定。l證明：l后序(hu x)序列是a1a2anl中序序列是b1b2bnl根結(jié)點(diǎn)：an。l

49、在中序序列中與an相同的結(jié)點(diǎn)為：bj。l b1bj-1bjbj+1bn a1a2akak+1an-1an第90頁(yè)/共134頁(yè)第九十一頁(yè)，共134頁(yè)。例：后序(hu x)序列為GDBEFCA,中序序列為DGBAECF根結(jié)點(diǎn)(ji din)：A左中序:DGB 左根:B右中序:ECF 右根:C根結(jié)點(diǎn)(ji din)：B左中序:DG 左根:D右中序:空 右根:空根結(jié)點(diǎn)：D左中序:空 左根:空右中序:G 右根:G根結(jié)點(diǎn)：G左中序:空 左根:空右中序:空 右根:空根結(jié)點(diǎn)：C左中序:E 左根:E右中序:F 右根:F根結(jié)點(diǎn)：E左中序:空 左根:空右中序:空 右根:空根結(jié)點(diǎn)：F左中序:空 左根:空右中序:空 右

50、根:空第91頁(yè)/共134頁(yè)第九十二頁(yè)，共134頁(yè)。由后序、中序構(gòu)造二叉樹(shù)的算法：BiTNode *CreateBT2(char *post,char *in,int n) BiTNode *s; char *p; int k; if(n=1)s=malloc();s-lchild=s-rchild=NULL;return s; for (p=in;pdata=*(post+n-1); s-lchild=s-rchild=NULL; if(k) s-lchild=CreateBT2(post, in, k); /左子樹(shù) if(n-k-1) s-rchild=CreateBT2(post+k, i

51、n+k+1, n-k-1);/右子樹(shù) return s;后序(hu x):GDBEFCA中序:DGBAECF第92頁(yè)/共134頁(yè)第九十三頁(yè)，共134頁(yè)。第93頁(yè)/共134頁(yè)第九十四頁(yè)，共134頁(yè)。劃分：劃分：R是是S上的等價(jià)關(guān)系上的等價(jià)關(guān)系(gun x)，可以按，可以按R將將S劃分為若干不劃分為若干不相交的子集相交的子集S1 ,S2,它們的它們的并即為并即為S，則這些子集，則這些子集Si就是就是S的的R等價(jià)類。等價(jià)類。6.5 樹(shù)與等價(jià)(dngji)問(wèn)題第94頁(yè)/共134頁(yè)第九十五頁(yè)，共134頁(yè)。如何(rh)劃分等價(jià)類？一種算法：1）令S中每個(gè)元素各自形成一個(gè)只含單個(gè)成員的子集，記為S1 ,S2

52、 ,Sn。2) 重復(fù)(chngf)讀入m個(gè)偶對(duì)，對(duì)每個(gè)偶對(duì)(x,y)，判斷x和y所屬的子集，設(shè)xSi，ySj，若SiSj，則將Sj并入Si，并置Sj為空。 處理完m個(gè)偶對(duì)后剩下的非空子集就是S的R等價(jià)類。第95頁(yè)/共134頁(yè)第九十六頁(yè)，共134頁(yè)。ADT MFSet：若S是MFSet類型(lixng)的集合，則它由子集Si構(gòu)成，S1S2Sn=S。 基本操作：Initial(&S,n,x1,x2,xn)：構(gòu)造由n個(gè)子集構(gòu)成的集合S，每個(gè)子集只含單個(gè)元素。Find(S,x)：查找x所屬的子集Si。Merge(&S,i,j)：合并兩個(gè)不相交的集合Si和Sj。第96頁(yè)/共134頁(yè)第九十七頁(yè)，共134頁(yè)

53、。約定根結(jié)點(diǎn)兼作子集的名稱。約定根結(jié)點(diǎn)兼作子集的名稱。第97頁(yè)/共134頁(yè)第九十八頁(yè)，共134頁(yè)。集合(jh)的合并：將一棵樹(shù)的根指向(zh xin)另一顆樹(shù)的根。第98頁(yè)/共134頁(yè)第九十九頁(yè)，共134頁(yè)。define MAX_TREE_SIZE 100typedef struct PTNode TElemType data; int parent; PTNode; Typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; /根的位置(wi zhi)和結(jié)點(diǎn)數(shù)PTree;Typedef PTree MFSet;第99頁(yè)/共134頁(yè)第一百頁(yè)，共134

54、頁(yè)。第100頁(yè)/共134頁(yè)第一百零一頁(yè)，共134頁(yè)。第101頁(yè)/共134頁(yè)第一百零二頁(yè)，共134頁(yè)。第102頁(yè)/共134頁(yè)第一百零三頁(yè)，共134頁(yè)。第103頁(yè)/共134頁(yè)第一百零四頁(yè)，共134頁(yè)。第104頁(yè)/共134頁(yè)第一百零五頁(yè)，共134頁(yè)。6.6 哈夫曼樹(shù)及其應(yīng)用(yngyng) 1. 哈夫曼樹(shù) 路徑長(zhǎng)度 從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑， 路徑上的分支數(shù)目稱做路徑長(zhǎng)度。 樹(shù)的路徑長(zhǎng)度 從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度 給樹(shù)的每個(gè)結(jié)點(diǎn)賦予一個(gè)具有某種實(shí)際意義的實(shí)數(shù)，我們稱該實(shí)數(shù)為這個(gè)結(jié)點(diǎn)的權(quán)。在樹(shù)形結(jié)構(gòu)(jigu)中，我們把從樹(shù)根到某一結(jié)點(diǎn)

55、的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積，叫做該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。第105頁(yè)/共134頁(yè)第一百零六頁(yè)，共134頁(yè)。 樹(shù)的帶權(quán)路徑長(zhǎng)度WPL (Weighted Path Length of Tree) 樹(shù)中所有葉子結(jié)點(diǎn)(ji din)的帶權(quán)路徑長(zhǎng)度之和，通常記為： 1nk kkWPLw lABCD7524(a) 帶權(quán)路徑長(zhǎng)度為 36ABCD7524(b) 帶權(quán)路徑長(zhǎng)度為 46ADCB7524(c) 帶權(quán)路徑長(zhǎng)度為 35WPL(a)=7252224236WPL(b)=4273532146WPL(c)=7152234335 第106頁(yè)/共134頁(yè)第一百零七頁(yè)，共134頁(yè)。234723477432(a) W

56、PL 22 23 24 27 32(b) W PL 12 23 34 37 41(c) W PL 17 24 33 32 7 8 9 6 30哈夫曼樹(shù)(最優(yōu)二叉樹(shù)) 設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)(ji din),那么從根結(jié)點(diǎn)(ji din)到各個(gè)葉子結(jié)點(diǎn)(ji din)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)(ji din)權(quán)值的乘積的和,叫做二叉樹(shù)的帶權(quán)路徑長(zhǎng)度。 具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)稱為哈夫曼樹(shù)。第107頁(yè)/共134頁(yè)第一百零八頁(yè)，共134頁(yè)。2.構(gòu)造哈夫曼樹(shù)(哈夫曼算法)由給定的n個(gè)權(quán)值W1,W2,.,Wn,構(gòu)造n棵只有一個(gè)葉子結(jié)點(diǎn) 的 二 叉 樹(shù) , 從 而 得 到 一 個(gè) 二 叉 樹(shù) 的 集

57、 合(jh)F=T1,T2,.,Tn;在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù),這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和;在集合(jh)F中刪除作為左、右子樹(shù)的兩棵二叉樹(shù),并將新建立的二叉樹(shù)加入到集合(jh)F中;重復(fù)(2)、(3)兩步,當(dāng)F中只剩下一棵二叉樹(shù)時(shí),這棵二叉樹(shù)便是所要建立的哈夫曼樹(shù)。第108頁(yè)/共134頁(yè)第一百零九頁(yè)，共134頁(yè)。給定(i dn)權(quán)值w=(1,3,5,7)來(lái)構(gòu)造一棵哈夫曼樹(shù) 。 9 4 1 7 5 3 16 9 4 1 7 5 3 (c) (d) 1 3 5 7 4 5 7 1 3 (a) (b) 第109頁(yè)/共1

58、34頁(yè)第一百一十頁(yè)，共134頁(yè)。3 哈夫曼編碼(bin m)1. 編碼(bin m)例，傳送 ABACCD，四種字符(z f)，可以分別編碼為 00,01,10,11。則原電文轉(zhuǎn)換為 00 01 00 10 10 11。對(duì)方接收后，采用二位一分進(jìn)行譯碼。電文編碼二進(jìn)制二進(jìn)制譯碼電文第110頁(yè)/共134頁(yè)第一百一十一頁(yè)，共134頁(yè)。當(dāng)然，為電文編碼時(shí)，總是希望(xwng)總長(zhǎng)越短越好，如果對(duì)每個(gè)字符設(shè)計(jì)長(zhǎng)度不等的編碼，且讓電文(dinwn)中出現(xiàn)次數(shù)較多的字符采用較短的編碼，則可以減短電文(dinwn)的總長(zhǎng)。例，對(duì) ABACCD 重新編碼，分別編碼為 0 , 00 , 1 , 01。A B C

59、 D則原電文(dinwn)轉(zhuǎn)換為 0 00 0 1 1 01。 減短了。問(wèn)題: 如何譯碼？前四個(gè)二進(jìn)制字符就可以多種譯法。AAAABB第111頁(yè)/共134頁(yè)第一百一十二頁(yè)，共134頁(yè)。2. 前綴(qinzhu)編碼若設(shè)計(jì)的長(zhǎng)短不等的編碼，滿足任一個(gè)編碼都不是(b shi)另一個(gè)編碼的前綴，則這樣的編碼稱為前綴編碼。例， A , B , C , D 前綴(qinzhu)編碼可以為 0 , 110 , 10 , 111利用二叉樹(shù)設(shè)計(jì)二進(jìn)制前綴編碼。葉子結(jié)點(diǎn)表示 A , B , C , D 這 4 個(gè)字符ACBD000111左分支表示 0，右分支表示 1從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上經(jīng)過(guò)的二進(jìn)制符號(hào)串作

60、為該葉子結(jié)點(diǎn)字符的編碼A(0)B(110)C(10)D(111)證明其必為前綴編碼路徑長(zhǎng)度為編碼長(zhǎng)度第112頁(yè)/共134頁(yè)第一百一十三頁(yè)，共134頁(yè)。如何得到(d do)最短的二進(jìn)制前綴編碼？3. 赫夫曼編碼(bin m)設(shè)每種字符(z f)在電文中出現(xiàn)的概率 wi 為，則依此 n 個(gè)字符(z f)出現(xiàn)的概率做權(quán)，可以設(shè)計(jì)一棵赫夫曼樹(shù)，使WPL = wi li 最小ni=1wi 為葉子結(jié)點(diǎn)的出現(xiàn)概率 ( 權(quán))li 為根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑長(zhǎng)度第113頁(yè)/共134頁(yè)第一百一十四頁(yè)，共134頁(yè)。例，某通信可能(knng)出現(xiàn) A B C D E F G H 8 個(gè)字符，其概率分別為 0.05 ,