1、第6章 樹和二叉樹,6.1 樹的概念與定義 6.2 二叉樹 6.3 二叉樹的遍歷與線索化 6.4 樹、森林和二叉樹的關(guān)系 6.5 樹與等價(jià)類 6.6 哈夫曼樹及其應(yīng)用,6.1 樹的定義和基本術(shù)語,1. 樹的定義 樹是n（n0）個(gè)結(jié)點(diǎn)的有限集。當(dāng)n=0時(shí)，稱為空樹；在任意一棵非空樹中滿足如下條件： (1) 有且僅有一個(gè)特定的稱為根（root）的結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。 (2) 其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m0）個(gè)互不相交的有限集T1，T2，T3，Tm，其中Ti又是一棵樹，稱為根root的子樹。 每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。,2. 樹的邏輯

2、表示法 (1) 樹型表示法。這是樹的最基本的表示,使用一棵倒置的樹表示樹結(jié)構(gòu),非常直觀和形象。,(2)文氏圖表示法。使用集合以及集合的包含關(guān)系描述樹結(jié)構(gòu)。,(3)凹入表示法。使用線段的伸縮描述樹結(jié)構(gòu)。,(4)括號表示法(廣義表表示法)。將樹的根結(jié)點(diǎn)寫在括號的左邊,除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫在括號中并用逗號間隔來描述樹結(jié)構(gòu)。,3. 樹的基本術(shù)語 結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。 結(jié)點(diǎn)的度和樹的度(degree)：結(jié)點(diǎn)擁有的子樹個(gè)數(shù)。樹內(nèi)各結(jié)點(diǎn)的度的最大值。 葉子(leaf)和分支結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。

3、,孩子、雙親、兄弟、堂兄弟：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子。相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親。同一雙親的孩子之間互稱兄弟。其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。 B、C、D是A的孩子。 A 是B、C 、D的雙親。 結(jié)點(diǎn)H、I、 J互為兄弟結(jié)點(diǎn)。,路徑與路徑長度：對于任意兩個(gè)結(jié)點(diǎn)ki和kj,若樹中存在一個(gè)結(jié)點(diǎn)序列ki,ki1,ki2,kin,kj,使得序列中除ki外的任一結(jié)點(diǎn)都是其在序列中的前一個(gè)結(jié)點(diǎn)的后繼,則稱該結(jié)點(diǎn)序列為由ki到kj的一條路徑,用路徑所通過的結(jié)點(diǎn)序列(ki,ki1,ki2,kj)表示這條路徑。路徑的長度等于路徑所通過的結(jié)點(diǎn)數(shù)目減1(即路徑上分支數(shù)目)?？梢?路徑就是從ki出發(fā)“自上而下

4、”到達(dá)kj所通過的樹中結(jié)點(diǎn)序列。顯然,從樹的根結(jié)點(diǎn)到樹中其余結(jié)點(diǎn)均存在一條路徑。,結(jié)點(diǎn)的祖先和子孫：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)。以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。 結(jié)點(diǎn)的層次和樹的高度(深度)：從根結(jié)點(diǎn)開始定義，根為第一層，根的孩子為第二層，依此類推。樹中結(jié)點(diǎn)的最大層次。,1,2,3,4,有序樹和無序樹：在樹中，如果各子樹Ti是按照一定的次序從左向右安排的，且相對次序是不能隨意改變的，則稱為有序樹，否則稱為無序樹。 森林： m（m0）棵互不相交的樹的集合。將一棵非空樹的根結(jié)點(diǎn)刪去，樹就變成一個(gè)森林；反之，給m棵獨(dú)立的樹增加一個(gè)根結(jié)點(diǎn)，并把這m棵樹作為該結(jié)點(diǎn)的子樹，森林就

5、變成一棵樹。,森林,樹屬于森林。,樹是一個(gè)二元組 Tree = ( root ，F(xiàn) ) 。,root : 根結(jié)點(diǎn)。,樹的運(yùn)算主要分為三大類： 第一類,尋找滿足某種特定關(guān)系的結(jié)點(diǎn),如尋找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等； 第二類,插入或刪除某個(gè)結(jié)點(diǎn),如在樹的當(dāng)前結(jié)點(diǎn)上插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)等； 第三類,遍歷樹中每個(gè)結(jié)點(diǎn),這里著重介紹。,4.樹的基本運(yùn)算,6.2 二 叉 樹,1. 二叉樹的定義,滿足以下兩個(gè)條件的樹形結(jié)構(gòu)叫做二叉樹（Binary Tree）： （1） 每個(gè)結(jié)點(diǎn)的度都不大于2； （2） 每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。 由此定義可以看出，一個(gè)二叉樹中的每個(gè)結(jié)點(diǎn)只能含有0

6、、 1或2個(gè)孩子，而且每個(gè)孩子有左右之分。把位于左邊的孩子叫做左孩子，位于右邊的孩子叫做右孩子。,二叉樹的五種基本形態(tài),2. 二叉樹的性質(zhì),性質(zhì)1: 在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i1)。 證明： 用數(shù)學(xué)歸納法。 1) 當(dāng)i=1時(shí)，整個(gè)二叉樹只有一根結(jié)點(diǎn)，此時(shí)2i-1=20=1， 結(jié)論成立。 2) 設(shè)i=k時(shí)結(jié)論成立，即第k層上結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)。 現(xiàn)證明當(dāng)i=k+1時(shí)， 結(jié)論成立： 因?yàn)槎鏄渲忻總€(gè)結(jié)點(diǎn)的度最大為2，則第k+1層的結(jié)點(diǎn) 總數(shù)最多為第k層上結(jié)點(diǎn)最大數(shù)的2倍，即22k-1=2(k+1)-1， 故結(jié)論成立。,度為m的樹中第i層上至多有mi-1個(gè)結(jié)點(diǎn), (i1)。,性

7、質(zhì)2: 深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k1）。 證明：因?yàn)樯疃葹閗的二叉樹，其結(jié)點(diǎn)總數(shù)的最大值是將二叉樹每層上結(jié)點(diǎn)的最大值相加，所以深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多為,深度為k的m叉樹至多有 個(gè)結(jié)點(diǎn)。,性質(zhì)3: 對任意一棵二叉樹，若終端結(jié)點(diǎn)數(shù)為n0，度為 2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。 證明：設(shè)二叉樹中結(jié)點(diǎn)總數(shù)為n，n1為二叉樹中度為1 的結(jié)點(diǎn)總數(shù)，設(shè)二叉樹中分支數(shù)目為B 。 n=n0+n1+n2 除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對應(yīng)一個(gè)進(jìn)入它的分支： n=B+1 二叉樹中的分支都是由度為1和度為2的結(jié)點(diǎn)發(fā)出 B=n1+2n2,滿二叉樹：,深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。在滿二叉樹中，每

8、層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。 滿二叉樹的順序表示，即從二叉樹的根開始， 層間從上到下， 層內(nèi)從左到右，逐層進(jìn)行編號（1， 2， ， n）。,完全二叉樹： 深度為k，結(jié)點(diǎn)數(shù)為n的二叉樹，如果其結(jié)點(diǎn)1n的位置序號分別與滿二叉樹的結(jié)點(diǎn)1n的位置序號一一對應(yīng)，則為完全二叉樹， 滿二叉樹必為完全二叉樹， 而完全二叉樹不一定是滿二叉樹。,性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n+1或log2(n+1)。 證明：設(shè)n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù) 性質(zhì)2有 2k-1-1n 2k-1 可得 2k-1n 2k， 即 k-1log2n k 因?yàn)閗是整數(shù)，所以k-1= log2n，k

9、= log2n+1, 故結(jié)論成立。 2k-1n +12k k-1 log2(n+1) k k= log2(n+1) ,性質(zhì)5:對完全二叉樹中編號為i的結(jié)點(diǎn)(1in,n1,n為結(jié)點(diǎn)數(shù))有： (1)若i=1,則結(jié)點(diǎn)i是二叉樹的根，無雙親。 若i1,則它的雙親結(jié)點(diǎn)的編號為i/2。當(dāng)i為偶數(shù)時(shí),其雙親結(jié)點(diǎn)的編號為i/2,它是雙親結(jié)點(diǎn)的左孩子結(jié)點(diǎn),當(dāng)i為奇數(shù)時(shí),其雙親結(jié)點(diǎn)的編號為(i-1)/2,它是雙親結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。,(2)若編號為i的結(jié)點(diǎn)有左孩子結(jié)點(diǎn),則左孩子結(jié)點(diǎn)的編號為2i；若編號為i的結(jié)點(diǎn)有右孩子結(jié)點(diǎn),則右孩子結(jié)點(diǎn)的編號為(2i+1)。 當(dāng)2in，則結(jié)點(diǎn)i無左孩子，無左孩子則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)；

10、當(dāng)2i+1n，則結(jié)點(diǎn)無右孩子。,(3)若n為奇數(shù),則每個(gè)分支結(jié)點(diǎn)都既有左孩子結(jié)點(diǎn),也有右孩子結(jié)點(diǎn)；若n為偶數(shù),則編號最大的分支結(jié)點(diǎn)(編號為n/2)只有左孩子結(jié)點(diǎn),沒有右孩子結(jié)點(diǎn),其余分支結(jié)點(diǎn)都有左、右孩子結(jié)點(diǎn)。,3. 二叉樹的存儲結(jié)構(gòu),二叉樹的存儲結(jié)構(gòu)有兩種： 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。,順序存儲結(jié)構(gòu),編號從小到大的順序就是結(jié)點(diǎn)存放在連續(xù)存儲單元的先后次序,完全二叉樹: 編號為 i 的元素存儲在數(shù)組下標(biāo)為 i-1 的分量中；,1,3,7,15,一般二叉樹: 對照完全二叉樹，存儲在數(shù)組的相應(yīng)分量中；,在最壞情況下，深度為 k 的右單支二叉樹需要 2k-1 個(gè)存儲空間。,二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu) t

11、ypedef struct BiTNode ElemType data; struct BiTNode *lchild,*rchild; BiTNode, *BiTree; data表示值域,用于存儲對應(yīng)的數(shù)據(jù)元素, lchild和rchild分別表示左指針域和右指針域,用于分別存儲左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)(即左、右子樹的根結(jié)點(diǎn))的存儲位置。,二叉樹及其鏈?zhǔn)酱鎯Y(jié)構(gòu),n1個(gè)空鏈域，分支數(shù)目B=n-1， 即非空的鏈域有n-1個(gè)，故空鏈域有2n-(n-1)=n+1個(gè)。,作業(yè)： 6.2 6.3 6.5 6.6 6.8,6.3 遍歷二叉樹和線索二叉樹,1.二叉樹遍歷的概念 二叉樹的遍歷是指按照一定次序訪

12、問樹中所有結(jié)點(diǎn),并且每個(gè)結(jié)點(diǎn)僅被訪問一次的過程。它是最基本的運(yùn)算,是二叉樹中所有其他運(yùn)算的基礎(chǔ)。,用L、D、R分別表示遍歷左子樹、訪問根結(jié)點(diǎn)、 遍歷右子樹， 二叉樹的遍歷順序就可以有六種方式： 訪問根，遍歷左子樹，遍歷右子樹（記做DLR）。 訪問根，遍歷右子樹，遍歷左子樹（記做DRL）。 遍歷左子樹，訪問根，遍歷右子樹（記做LDR）。 遍歷左子樹，遍歷右子樹，訪問根（記做LRD）。 遍歷右子樹，訪問根，遍歷左子樹（記做RDL）。 遍歷右子樹，遍歷左子樹，訪問根（記做RLD）。,三種遍歷方法的遞歸定義 先序遍歷（DLR）操作過程： 若二叉樹為空， 則空操作， 否則 (1) 訪問根結(jié)點(diǎn)； (2)

13、按先序遍歷左子樹； (3) 按先序遍歷右子樹。 中序遍歷（LDR）操作過程： 若二叉樹為空，則空操作，否則： (1) 按中序遍歷左子樹； (2) 訪問根結(jié)點(diǎn)； (3) 按中序遍歷右子樹。,后序遍歷（LRD）操作過程： 若二叉樹為空， 則空操作， 否則： (1) 按后序遍歷左子樹； (2) 按后序遍歷右子樹； (3) 訪問根結(jié)點(diǎn)。,先序遍歷： A、 B、 D、 F、 G、 C、 E、 H 。 中序遍歷： B、 F、 D、 G、 A、 C、 E、 H 。 后序遍歷： F、 G、 D、 B、 H、 E、 C、 A 。,算術(shù)式的二叉樹表示,前綴： -+a*bc/de（波蘭表達(dá)式） 中綴： a+b*c-

14、d/e 后綴： abc*+de/-（逆波蘭表達(dá)式）,a+b*c-d/e,2. 二叉樹遍歷遞歸算法 先序遍歷的遞歸算法 void PreOrderTraverse(BiTree T) if (T!=NULL) printf(%c ,T-data); /*訪問根結(jié)點(diǎn)*/ PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); ,void PreOrderTraverse(BiTree T) 先序：第一次遇到就訪問 if (T!=NULL) printf(“%c ”,T-data); /訪問根結(jié)點(diǎn) PreOrderTraverse(T-lchi

15、ld); /先序遍歷根的左子樹 PreOrderTraverse(T-rchild); /先序遍歷根的右子樹 ,A,B,D,G,C,E,F,棧用于保存當(dāng)前結(jié)點(diǎn)的祖先結(jié)點(diǎn),中序遍歷的遞歸算法 void InOrderTraverse(BiTree T) if (T!=NULL) InOrderTraverse(T-lchild); printf(%c ,T-data); /*訪問根結(jié)點(diǎn)*/ InOrderTraverse(T-rchild); ,void InOrderTraverse(BiTree T)中序：第二次遇到就訪問 if (T!=NULL) InOrderTraverse(T-lch

16、ild); printf(%c ,T-data); /*訪問根結(jié)點(diǎn)*/ InOrderTraverse(T-rchild); ,A,B,D,G,C,E,F,棧用于保存當(dāng)前結(jié)點(diǎn)的祖先結(jié)點(diǎn),后序遍歷遞歸算法 void PostOrderTraverse(BiTree T) if (T!=NULL) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%c ,T-data); /*訪問根結(jié)點(diǎn)*/ ,void XXTraverse(BiTree T) /遍歷二叉樹的遞歸算法 if (T!=NULL) XXTraverse(T

17、-lchild); XXTraverse(T-rchild); printf(%c ,T-data); /*訪問根結(jié)點(diǎn)*/,將遞歸算法轉(zhuǎn)變?yōu)榈葍r(jià)的非遞歸算法，應(yīng)設(shè)置棧。,先序遍歷void PreOrderTraverse(BiTree T) 將根結(jié)點(diǎn)進(jìn)棧； while(棧不空) 出棧p; 訪問p; 其右孩子不空時(shí)，右孩子進(jìn)棧； 其左孩子不空時(shí)，左孩子進(jìn)棧； ,先序遍歷void PreOrderTraverse(BiTree T) InitStack(S); Push(S,T); while(!StackEmpty(S) Pop(S,p); coutdatarchild) Push(S, p-r

18、child); if(p-lchild) Push(S, p-lchild); ,中序遍歷void InOrderTraverse(BiTree T) InitStack(S); p = T; while( p | !StackEmpty(S) if(p) Push(S, p); p = p-lchild; else Pop(S, p); coutdatarchild; ,后序遍歷void PostOrderTraverse(BiTree T) typedef struct BiTree ptr; enum 0,1,2 mark; StackNode; mark=0表示剛剛訪問此結(jié)點(diǎn), mar

19、k=1表示左子樹處理結(jié)束返回, mark=2表示右子樹處理結(jié)束返回. 每次根據(jù)棧頂元素的mark域值決定做何種動作.,后序遍歷void PostOrderTraverse(BiTree T) StackNode a; InitStack(S); Push (S,T,0); /根結(jié)點(diǎn)入棧 while( !StackEmpty(S) ) Pop( S, a); switch( a.mark ) case 0: Push(S,a.ptr,1); if(a.ptr-lchild) Push(S,a.ptr-lchild,0); break; case 1: Push(S,a.ptr,2); if(a.

20、ptr-rchild) Push(S,a.ptr-rchild,0); break; case 2: coutdataLTag = 0) /有左孩子 while(pre-RTag = 0) pre = pre-rchild; return pre; ,找結(jié)點(diǎn)的中序后繼結(jié)點(diǎn) 結(jié)點(diǎn)p，無右孩子，右指針指向其后繼，否則p的 右子樹中“最左下”結(jié)點(diǎn)。 BiThrTree PostNode(BiThrTree p) post = p-rchild; if(p-RTag = 0) /有右孩子 while(post-LTag = 0) post = post-lchild; return post; ,帶頭

21、結(jié)點(diǎn)的線索二叉鏈表,帶頭結(jié)點(diǎn)的中序線索二叉鏈表,中序遍歷線索二叉樹 /0:有孩子；1：無孩子 Void InOrderTraverse_Thr(BiThrTree T)/T:頭結(jié)點(diǎn) p = T-lchild; while(p != T) while(p-LTag = 0) p=p-lchild; coutdataRTag=1) ,(2)后序線索二叉樹中，查找指定結(jié)點(diǎn)的前驅(qū)和后繼 找結(jié)點(diǎn)的后序前驅(qū)結(jié)點(diǎn) if(p-LTag = 1) pre = p-lchild;/無左孩子 if(p-LTag = 0) /有左孩子 if(p-RTag = 0) pre = p-rchild; /右孩子為前驅(qū) if

22、(p-RTag = 1) pre = p-lchild; /左孩子為前驅(qū) 從該結(jié)點(diǎn)出發(fā)就能找到。,找結(jié)點(diǎn)的后序后繼結(jié)點(diǎn) （需要知道該結(jié)點(diǎn)的雙親） P為根結(jié)點(diǎn)， 則無后繼結(jié)點(diǎn)； p無右孩子， If(p-RTag = 1) post = p-rchild; 若p是雙親的右孩子， 則雙親為p的后繼結(jié)點(diǎn)； 若p是雙親的左孩子，且p沒有右兄弟， 則雙親為其后繼結(jié)點(diǎn)； 若p是雙親的左孩子，且p有右兄弟， 則p的后繼是其雙親右子樹中第一個(gè)后序遍歷到的結(jié) 點(diǎn)。,(3)先序線索二叉樹中，查找指定結(jié)點(diǎn)的前驅(qū)和后繼 找結(jié)點(diǎn)的先序前驅(qū)結(jié)點(diǎn) 需知道該結(jié)點(diǎn)的雙親； 找結(jié)點(diǎn)的先序后繼結(jié)點(diǎn) 從該結(jié)點(diǎn)出發(fā)就能找到。,建立線索化

23、鏈表（以中序?yàn)槔?按某種次序?qū)⒍骀湵砭€索化，實(shí)質(zhì)是在遍歷過程中用線索取代空指針。,Status InOrderThreading(BiThrTree ,BiThrTree pre = Thrt; /*全局變量,剛剛訪問過的結(jié)點(diǎn)*/ void InThreading(BiThrTree p) if (p) InThreading(p-lchild); /*左子樹線索化*/ if (!p-lchild) /*前驅(qū)線索*/ p-lchild=pre; p-LTag=1; else p-LTag=0; if (!pre-rchild) /*后繼線索*/ pre-rchild=p; pre-rtag

24、=1; else pre-rtag=0; pre = p; InThreading(p-rchild); /*右子樹線索化*/ ,對線索樹進(jìn)行遍歷，顯然其效率要比傳統(tǒng)方式高些。如果程序中經(jīng)常要進(jìn)行二叉樹的遍歷或者需要查找在遍歷過程中的前驅(qū)和后繼，應(yīng)當(dāng)采用線索鏈表表示。,作業(yè)： 6.15,6.4 樹和森林,1. 樹的存儲結(jié)構(gòu)（三種方法）,雙親表示法：用一組連續(xù)的空間來存儲樹中的結(jié)點(diǎn)，在保存每個(gè)結(jié)點(diǎn)的同時(shí)附設(shè)一個(gè)指示器來指示其雙親結(jié)點(diǎn)在表中的位置， 其結(jié)點(diǎn)的結(jié)構(gòu)如下：,樹的雙親存儲結(jié)構(gòu)示意圖,define MAX_TREE_SIZE 100 typedef struct PTNode TElemT

25、ype data; int parent; PTNode; Typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; /根的位置和結(jié)點(diǎn)數(shù) PTree;,雙親表示法的類型說明：,孩子表示法：定長結(jié)點(diǎn)長度 空鏈域個(gè)數(shù)：nk (n-1) = n(k-1)+1. 把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，構(gòu)成一個(gè)單鏈表， 稱為孩子鏈表。n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空表），而n個(gè)結(jié)點(diǎn)的數(shù)據(jù)和n個(gè)孩子鏈表的頭指針又組成一個(gè)順序表。,typedef struct CTNode /* 孩子結(jié)點(diǎn)的定義 */ int Child; /* 該孩子結(jié)點(diǎn)在線性表中的位

26、置 */ struct CTNode *next; /* 指向下一個(gè)孩子結(jié)點(diǎn)的指針 */ *ChildPtr; typedef struct /* 順序表結(jié)點(diǎn)的結(jié)構(gòu)定義 */ TElemType data; /* 結(jié)點(diǎn)的信息 */ ChildPtr FirstChild ; /* 指向孩子鏈表的頭指針 */ CTBox; typedef struct /* 樹的定義 */ CTBox nodesMAX_TREE_SIZE; /* 順序表 */ int root, num; /* 根結(jié)點(diǎn)的位置和樹的結(jié)點(diǎn)個(gè)數(shù) */ CTree;,孩子兄弟表示法,typedef struct CSNode Elem

27、Type data; /*結(jié)點(diǎn)信息*/ Struct CSNode *FirstChild, *NextSibling; /*第一個(gè)孩子, 下一個(gè)兄弟*/ CSNode, *CSTree; 這種存儲結(jié)構(gòu)便于實(shí)現(xiàn)樹的各種操作。,樹的孩子兄弟鏈存儲結(jié)構(gòu)示意圖,2. 樹、森林與二叉樹的相互轉(zhuǎn)換,樹轉(zhuǎn)換為二叉樹,(1)在所有相鄰兄弟結(jié)點(diǎn)之間加一水平連線。 (2)對每個(gè)非葉結(jié)點(diǎn)k,除了其最左邊的孩子結(jié)點(diǎn)外,刪去k與其他孩子結(jié)點(diǎn)的連線。 (3)所有水平線段以左邊結(jié)點(diǎn)為軸心順時(shí)針旋轉(zhuǎn)45度，使之結(jié)構(gòu)層次分明。 樹做這樣的轉(zhuǎn)換所構(gòu)成的二叉樹是唯一的。,樹與二叉樹的對應(yīng),森林轉(zhuǎn)換為二叉樹 森林也可以方便地用孩子

28、兄弟鏈表表示。森林轉(zhuǎn)換為二叉樹的方法如下： （1）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。 （2）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子， 當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。,二叉樹還原為樹或森林 將一棵二叉樹還原為樹或森林，具體方法如下： （1） 若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、 右孩子的右孩子都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來。 （2） 刪掉原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。 （3） 整理由（1）、（2）兩步所得到的樹或森林， 使之結(jié)構(gòu)層次分明。,二叉樹到森林的轉(zhuǎn)換示例,3. 樹與森林的遍

29、歷,樹的遍歷（兩種） 1） 先根遍歷 若樹非空，則遍歷方法為： 訪問根結(jié)點(diǎn)。 從左到右， 依次先根遍歷根結(jié)點(diǎn)的每一棵子樹。,先根遍歷序列ABECFHGD,等同于轉(zhuǎn)換的二叉樹進(jìn)行先序遍歷,2后根遍歷 若樹非空， 則遍歷方法為： 從左到右， 依次后根遍歷根結(jié)點(diǎn)的每一棵子樹。 訪問根結(jié)點(diǎn)。 ,后根遍歷序列為EBHFGCDA,等同于轉(zhuǎn)換的二叉樹進(jìn)行中序遍歷,森林的遍歷（2種） 1） 先序遍歷 若森林非空， 則遍歷方法為： 訪問森林中第一棵樹的根結(jié)點(diǎn)。 先序遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林。 先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 ,先序遍歷序列為 ABCDEFGHIJ,等同于轉(zhuǎn)換的二叉樹進(jìn)行先序遍

30、歷,2） 中序遍歷 若森林非空， 則遍歷方法為： 中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林。 訪問第一棵樹的根結(jié)點(diǎn)。 中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。,中序遍歷序列為 BCDAFEHJIG,等同于轉(zhuǎn)換的二叉樹進(jìn)行中序遍歷,4. 幾個(gè)問題 給定樹的先根遍歷序列和后根遍歷序列可唯一畫出一棵樹。 給定森林的先序遍歷序列和中序遍歷序列可唯一確定一森林。 關(guān)于二叉樹的先序、中序和后序遍歷序列確定二叉樹的問題。,給定樹的先根遍歷序列和后根遍歷序列可唯一畫出一棵樹。 先根遍歷序列：A B E C F H G D 后根遍歷序列：E B H F G C D A,給定森林的先序遍歷序列和中序遍歷序列可

31、唯一確定一森林。 先序遍歷序列：A B C D E F G H I J 中序遍歷序列：B C D A F E H J I G,關(guān)于二叉樹的先序、中序和后序遍歷序列確定二叉樹的問題。,任何n(n0)個(gè)不同結(jié)點(diǎn)的二叉樹,都可由它的中序序列和先序序列唯一地確定。 證明： 先序序列是a1a2an 中序序列是b1b2bn 根結(jié)點(diǎn)：a1。 在中序序列中與a1相同的結(jié)點(diǎn)為：bj。 b1bj-1bjbj+1bn a1a2akak+1an,例：已知先序序列為ABDGCEF,中序序列為DGBAECF,根結(jié)點(diǎn)：G 左先序:空 左中序:空 右先序:空 右中序:空,根結(jié)點(diǎn)：A 左先序:BDG 左中序:DGB 右先序:C

32、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 左先序:空 左中序:空 右先序:空 右中序:空,由先序、中序序列構(gòu)造二叉樹的算法： BiTNode *CreateBT1(char *pre,char *in,int n) BiTNode *s; char *p; int k; if(n=1)s=malloc();s-lchild=s-rchild=NULL;retur

33、n s; for (p=in;pdata=*pre; s-lchild=s-rchild=NULL; if(k) s-lchild = CreateBT1(pre+1,in,k);/左子樹 if(n-k-1) s-rchild = CreateBT1(pre+k+1,p+1,n-k-1);/右子樹 return s; ,先序：ABDGCEF,中序：DGBAECF,任何n(n0)個(gè)不同結(jié)點(diǎn)的二叉樹,都可由它的中序序列和后序序列唯一地確定。 證明： 后序序列是a1a2an 中序序列是b1b2bn 根結(jié)點(diǎn)：an。 在中序序列中與an相同的結(jié)點(diǎn)為：bj。 b1bj-1bjbj+1bn a1a2akak

34、+1an-1an,例：后序序列為GDBEFCA,中序序列為DGBAECF,根結(jié)點(diǎn)：A 左中序:DGB 左根:B 右中序:ECF 右根:C,根結(jié)點(diǎn)：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 左中序:空 左根:空 右中序:空 右根:空,由后序、中序構(gòu)造二叉樹的算法： BiTNode *CreateBT2(char *post,char *in,int n)

35、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); /左子樹 if(n-k-1) s-rchild=CreateBT2(post+k, in+k+1, n-k-1);/右子樹 return s; ,后序:GDBEFCA,中序:DGBAECF,作業(yè)： 6.14 6.19 6.20 6.23 6.24 6.28,

36、離散數(shù)學(xué)中的定義 等價(jià)關(guān)系：若集合S中的關(guān)系R是自反的、對稱的和傳遞的，則稱為等價(jià)關(guān)系。 等價(jià)類：R是集合S的等價(jià)關(guān)系，由xR=y|ySxRy給出的集合xR稱為由xS生成的一個(gè)R等價(jià)類。 劃分：R是S上的等價(jià)關(guān)系，可以按R將S劃分為若干不相交的子集S1 ,S2,它們的并即為S，則這些子集Si就是S的R等價(jià)類。,6.5 樹與等價(jià)問題,假設(shè)集合S有n個(gè)元素，m個(gè)形如(x,y)的等價(jià)偶對確定了等價(jià)關(guān)系R，求S的劃分。,如何劃分等價(jià)類？,一種算法： 1）令S中每個(gè)元素各自形成一個(gè)只含單個(gè)成員的子集，記為S1 ,S2 ,Sn。 2) 重復(fù)讀入m個(gè)偶對，對每個(gè)偶對(x,y)，判斷x和y所屬的子集，設(shè)xSi

37、，ySj，若SiSj，則將Sj并入Si，并置Sj為空。 處理完m個(gè)偶對后剩下的非空子集就是S的R等價(jià)類。,劃分等價(jià)類需要的操作,1) 構(gòu)造只含單個(gè)元素的集合 2) 判定某個(gè)元素所屬集合 3) 合并兩個(gè)互不相交的集合,ADT MFSet：若S是MFSet類型的集合，則它由子集Si構(gòu)成，S1S2Sn=S。,基本操作： Initial( int parent; PTNode; Typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; /根的位置和結(jié)點(diǎn)數(shù) PTree; Typedef PTree MFSet;,int find_mfset(MFSet S,

38、 int i) if (iS.n) return -1; for (j=i;S.nodesj.parent0;j=S.nodej.parent) ; return j; Status merge_mfset(MFSet 時(shí)間復(fù)雜度分別為O(d)和O(1)，d為樹的深度,極端情況：,改進(jìn)方法？,Merge時(shí)，總是將成員少的子集根結(jié)點(diǎn)指向含成員多的子集的根 修改存儲結(jié)構(gòu)，令根結(jié)點(diǎn)的parent域存儲子集中所含成員數(shù)目的負(fù)值 可以將find_mfset的復(fù)雜度降到O(logn),Status mix_mfset(MFSet ,進(jìn)一步的改進(jìn)：Find時(shí)壓縮路徑,當(dāng)所查元素不在第二層時(shí)，將所有從根到該元

39、素路徑上的元素都變成根結(jié)點(diǎn)的孩子 int fix_mfset(MFSet ,6.6 哈夫曼樹及其應(yīng)用,1. 哈夫曼樹,路徑長度 從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑， 路徑上的分支數(shù)目稱做路徑長度。 樹的路徑長度 從樹根到每一結(jié)點(diǎn)的路徑長度之和。 結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長度 給樹的每個(gè)結(jié)點(diǎn)賦予一個(gè)具有某種實(shí)際意義的實(shí)數(shù)，我們稱該實(shí)數(shù)為這個(gè)結(jié)點(diǎn)的權(quán)。在樹形結(jié)構(gòu)中，我們把從樹根到某一結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積，叫做該結(jié)點(diǎn)的帶權(quán)路徑長度。,樹的帶權(quán)路徑長度WPL (Weighted Path Length of Tree) 樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，通常記為：,W

40、PL(a)=7252224236 WPL(b)=4273532146 WPL(c)=7152234335,哈夫曼樹(最優(yōu)二叉樹) 設(shè)二叉樹具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn),那么從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積的和,叫做二叉樹的帶權(quán)路徑長度。 具有最小帶權(quán)路徑長度的二叉樹稱為哈夫曼樹。,2.構(gòu)造哈夫曼樹(哈夫曼算法) 由給定的n個(gè)權(quán)值W1,W2,.,Wn,構(gòu)造n棵只有一個(gè)葉子結(jié)點(diǎn)的二叉樹,從而得到一個(gè)二叉樹的集合F=T1,T2,.,Tn; 在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹,這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和; 在集合F中

41、刪除作為左、右子樹的兩棵二叉樹,并將新建立的二叉樹加入到集合F中; 重復(fù)(2)、(3)兩步,當(dāng)F中只剩下一棵二叉樹時(shí),這棵二叉樹便是所要建立的哈夫曼樹。,給定權(quán)值w=(1,3,5,7)來構(gòu)造一棵哈夫曼樹 。,3 哈夫曼編碼,1. 編碼,例，傳送 ABACCD，四種字符，可以分別編碼為 00,01,10,11。,則原電文轉(zhuǎn)換為 00 01 00 10 10 11。,對方接收后，采用二位一分進(jìn)行譯碼。,電文,編碼,二進(jìn)制,二進(jìn)制,譯碼,電文,當(dāng)然，為電文編碼時(shí)，總是希望總長越短越好，,如果對每個(gè)字符設(shè)計(jì)長度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符采用較短的編碼，則可以減短電文的總長。,則原電文轉(zhuǎn)換

42、為 0 00 0 1 1 01。 減短了。,問題:,如何譯碼？,前四個(gè)二進(jìn)制字符就可以多種譯法。,AAAA,BB,2. 前綴編碼,若設(shè)計(jì)的長短不等的編碼，滿足任一個(gè)編碼都不是另一個(gè)編碼的前綴，則這樣的編碼稱為前綴編碼。,例， A , B , C , D 前綴編碼可以為 0 , 110 , 10 , 111,利用二叉樹設(shè)計(jì)二進(jìn)制前綴編碼。,葉子結(jié)點(diǎn)表示 A , B , C , D 這 4 個(gè)字符,左分支表示 0，右分支表示 1,從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上經(jīng)過的二進(jìn)制符號串作為該葉子結(jié)點(diǎn)字符的編碼,A(0),B(110),C(10),D(111),證明其必為前綴編碼,路徑長度為編碼長度,如何得到最

43、短的二進(jìn)制前綴編碼？,3. 赫夫曼編碼,設(shè)每種字符在電文中出現(xiàn)的概率 wi 為，則依此 n 個(gè)字符出現(xiàn)的概率做權(quán)，可以設(shè)計(jì)一棵赫夫曼樹，使,wi 為葉子結(jié)點(diǎn)的出現(xiàn)概率 ( 權(quán)),li 為根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑長度,例，某通信可能出現(xiàn) A B C D E F G H 8 個(gè)字符，其概率分別為 0.05 , 0.29 , 0.07 , 0.08 , 0.14 , 0.23 , 0.03 , 0.11 ，試設(shè)計(jì)赫夫曼編碼,不妨設(shè) w = 5 , 29 , 7 , 8 , 14 , 23 , 3 , 11 ,排序后 w = 3 , 5 , 7 , 8 , 11 , 14 , 23 , 29 ,ACEA

44、 編碼為 0110 1110 110 0110,如何譯碼？,1. 從根結(jié)點(diǎn)出發(fā)，從左至右掃描編碼，,2. 若為 0 則走左分支，若為1 則走右分支，直至葉結(jié)點(diǎn)為止，,3. 取葉結(jié)點(diǎn)字符為譯碼結(jié)果，返回重復(fù)執(zhí)行 1,2,3 直至全部譯完為止,A,C,E,A,4. 哈夫曼編碼算法的實(shí)現(xiàn),typedef struct unsigned int weight ; / 結(jié)點(diǎn)的權(quán)值 unsigned int parent, lchild, rchild ; HTNode, * HuffmanTree; /動態(tài)分配數(shù)組存儲哈夫曼樹 typedef char * *HuffmanCode ; /動態(tài)分配數(shù)組存

45、儲哈夫曼編碼,哈夫曼樹中沒有度為1的結(jié)點(diǎn)(嚴(yán)格的或正則的二叉樹)。 n個(gè)葉子結(jié)點(diǎn)，共有2n-1個(gè)結(jié)點(diǎn)。,void HuffmanCoding( HuffmanTree ,HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cd=(char * )malloc(n * sizeof(char ); cdn-1 0 ； for(i=1; irchild) 其他情況,void DispLeaf(BiTree b) if (b!=NULL) if (b-lchild=NULL ,例2:求高度BiTreeDepth(b) 求二叉樹的高度的遞歸模型f()如下： f(NULL)=0 f(b)=MAXf(b-lchild),f(b