《數(shù)據(jù)結(jié)構(gòu)教學(xué)》第08章

第8章樹(shù)和二叉樹(shù)樹(shù)二叉樹(shù)二叉樹(shù)設(shè)計(jì)二叉樹(shù)遍歷線索二叉樹(shù)哈夫曼樹(shù)等價(jià)問(wèn)題樹(shù)與二叉樹(shù)的轉(zhuǎn)換樹(shù)的遍歷主要知識(shí)點(diǎn)編輯ppt編輯ppt8.1樹(shù)1.樹(shù)的定義直觀上：樹(shù)是由n(n≥0)個(gè)數(shù)據(jù)組成的有限集合，

其中僅有一個(gè)沒(méi)有直接前驅(qū)的數(shù)據(jù)，稱(chēng)之為根結(jié)點(diǎn),

若干沒(méi)有后繼的數(shù)據(jù)，稱(chēng)之為

葉結(jié)點(diǎn)，

其他的數(shù)據(jù)只有一個(gè)前驅(qū)數(shù)據(jù)，且至少有一個(gè)后繼數(shù)據(jù)。ABCGEIDHFJFLK編輯ppt8.1樹(shù)1.樹(shù)的定義（嚴(yán)謹(jǐn)）樹(shù)是由n(n≥0)個(gè)結(jié)點(diǎn)組成的有限集合T。n=0的樹(shù)稱(chēng)為空樹(shù)；對(duì)n>0的樹(shù)，有:(1)僅有一個(gè)特殊的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)，根結(jié)點(diǎn)沒(méi)有前驅(qū)

結(jié)點(diǎn)；(2)當(dāng)n>1時(shí)，除根結(jié)點(diǎn)外其余的結(jié)點(diǎn)分為m(m>0)個(gè)互

不相交的有限集合T1,T2，…，Tm，其中每個(gè)集合Ti

本身又是一棵結(jié)構(gòu)和樹(shù)類(lèi)似的子樹(shù)。注：樹(shù)的定義具有遞歸性，即“樹(shù)中還有樹(shù)”。編輯ppt若干術(shù)語(yǔ)結(jié)點(diǎn)：由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成ABCGEIDHFJFLK結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱(chēng)作

終端結(jié)點(diǎn)

分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)ABCGEIDHFJFLK編輯ppt孩子結(jié)點(diǎn)：樹(shù)中一個(gè)結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)雙親結(jié)點(diǎn)：若樹(shù)中某結(jié)點(diǎn)有孩子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)就稱(chēng)作它的孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)：具有相同的雙親結(jié)點(diǎn)的結(jié)點(diǎn)樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)到樹(shù)中某結(jié)點(diǎn)所經(jīng)路徑上的分支數(shù)樹(shù)的深度：樹(shù)中所有結(jié)點(diǎn)的層次的最大值A(chǔ)BCGEIDHFJFLK0123編輯ppt無(wú)序樹(shù)：樹(shù)中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)之間的次序構(gòu)成無(wú)關(guān)緊要的樹(shù)有序樹(shù)：樹(shù)中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)有嚴(yán)格排列次序的樹(shù)森林：m（m≥0）棵樹(shù)的集合2.樹(shù)的表示方法(1)直觀表示法(2)形式化表示法(3)凹入表示法(描述樹(shù)的邏輯結(jié)構(gòu))編輯pptT=（D，R）DF=D1∪D2∪…∪Dm

（1≤i,j≤m,Di∩Dj=￠）R={<Root,ri>,i=1,2,…,n-1}ABCDEFGHIJKL形式化表示凹進(jìn)表示(樹(shù)的理論討論)(樹(shù)的屏幕顯示和打印機(jī)輸出)編輯ppt3.樹(shù)的抽象數(shù)據(jù)類(lèi)型數(shù)據(jù)集合:

樹(shù)的結(jié)點(diǎn)集合，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成。操作集合:

（1）初始化Initiate(T)

（2）撤消DestroyTree(T)

（3）雙親結(jié)點(diǎn)Parent(T,curr)

（4）左孩子結(jié)點(diǎn)LeftChild(T,curr)

（5）右兄弟結(jié)點(diǎn)RightSibling(T,curr)

（6）遍歷樹(shù)Traverse(T,Visit())編輯ppt4.樹(shù)的存儲(chǔ)結(jié)構(gòu)

樹(shù)的結(jié)點(diǎn)之間的邏輯關(guān)系主要有雙親-孩子關(guān)系，兄弟關(guān)系。因此，從結(jié)點(diǎn)之間的邏輯關(guān)系分，樹(shù)的存儲(chǔ)結(jié)構(gòu)主要有：雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法四種組合。指針有常規(guī)指針和仿真指針指向內(nèi)存單元地址的指針；靜態(tài)鏈表形式的指針；結(jié)點(diǎn)的數(shù)據(jù)元素信息結(jié)點(diǎn)之間邏輯關(guān)系編輯ppt4H2G1F1E1D0C0B-1AI4dataparent012345678ABDEFHICG(1)雙親表示法(a)一棵樹(shù)（b)仿真指針的雙親表示法存儲(chǔ)結(jié)構(gòu)樹(shù)及其使用仿真指針的雙親表示法編輯ppt(2)孩子表示法A∧C∧G∧B∧D∧E∧F∧I∧H∧∧∧∧∧∧∧∧∧∧∧root常規(guī)指針的孩子表示法ABDEFHICG編輯ppt雙親孩子表示法存儲(chǔ)結(jié)構(gòu)(3)雙親孩子表示法∧4H2G1F1E1D0C0B-1AI4dataparenthead012345678∧∧∧∧childnext∧87∧∧∧123456ABDEFHICG編輯ppt(4)孩子兄弟表示法常規(guī)指針的孩子兄弟表示法root∧BCDEFGHI∧∧∧∧∧∧∧∧∧AABDEFHICG編輯ppt8.2二叉樹(shù)二叉樹(shù)：是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。n=0的樹(shù)稱(chēng)為空二叉樹(shù)；n>0的二叉樹(shù)由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。邏輯結(jié)構(gòu)：一對(duì)二（1:2）基本特征:①每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)（不存在度大于2的結(jié)點(diǎn)）；②左子樹(shù)和右子樹(shù)次序不能顛倒。所以下面是兩棵不同的樹(shù)1.二叉樹(shù)的定義編輯pptBACEDFGBACEDFG滿(mǎn)二叉樹(shù)：在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)。完全二叉樹(shù)：如果一棵深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)結(jié)構(gòu)與深度為k的滿(mǎn)二叉樹(shù)的前n個(gè)結(jié)點(diǎn)的結(jié)構(gòu)相同，那么該二叉樹(shù)稱(chēng)為完全二叉樹(shù)。如下圖所示左子樹(shù)右子樹(shù)編輯pptBACEDFGHIJKLMNO(a)滿(mǎn)二叉樹(shù)BACEDFGHIJ(b)完全二叉樹(shù)問(wèn)題:一個(gè)深度為h的完全二叉樹(shù)最多有多少個(gè)結(jié)點(diǎn)?最少有多少個(gè)結(jié)點(diǎn)?BACEDFGHIJJ(C)不是完全二叉樹(shù)編輯ppt數(shù)據(jù)集合：二叉樹(shù)的結(jié)點(diǎn)集合，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成。操作集合：（1）初始化Initiate(T)（2）撤消DestroyTree(T)（3）左插入結(jié)點(diǎn)InsertLeftNode(curr,x)（4）右插入結(jié)點(diǎn)InsertRightNode(curr,x)（5）左刪除子樹(shù)DeleteLeftTree(curr)（6）右刪除子樹(shù)DeleteRightTree(curr)（7）遍歷二叉樹(shù)Traverse(T,Visit())2.二叉樹(shù)抽象數(shù)據(jù)類(lèi)型編輯ppt3.二叉樹(shù)的性質(zhì)性質(zhì)1在一棵非空二叉樹(shù)的第i層上至多有2i個(gè)結(jié)點(diǎn)（i≥0）。性質(zhì)2深度為k的二叉樹(shù)至多有2k+1-1個(gè)結(jié)點(diǎn)。說(shuō)明：深度k=-1，表示沒(méi)有一個(gè)結(jié)點(diǎn)；深度k=0，表示只有一個(gè)根結(jié)點(diǎn)。首項(xiàng)為a0公比為q的等比數(shù)列的前n項(xiàng)和為：編輯ppt性質(zhì)3

對(duì)于一棵非空的二叉樹(shù)，如果葉結(jié)點(diǎn)個(gè)數(shù)為n0，度為1的結(jié)點(diǎn)數(shù)為n1，度為2的結(jié)點(diǎn)數(shù)為n2，結(jié)點(diǎn)總數(shù)為n,分支總數(shù)為M，則有下列結(jié)論成立，

(1)n=n0+n1+n2;(2)M=n-1;(3)M=n1+2n2;(4)n0=n2+1。（除根結(jié)點(diǎn)外都有惟一的進(jìn)入分支）編輯ppt性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度k為大于或等于lb(n+1)-1的最小整數(shù)。證明：由性質(zhì)2和完全二叉樹(shù)的定義可知，對(duì)于有n個(gè)結(jié)點(diǎn)的深度為k的完全二叉樹(shù)有：2k-1<n≤2k+1-1移項(xiàng)有：2k<n+1≤2k+1對(duì)不等式求對(duì)數(shù)，有：k<lb(n+1)≤k+1

因?yàn)閘b(n+1)介于k和k+1之間且大于k，而二叉樹(shù)的深度又只能是整數(shù)，所以必有k為大于或等于lb(n+1)-1的最小整數(shù)?？珊?jiǎn)寫(xiě)為k=lb(n+1)-1。例如，2.0=2，2.1=3。編輯ppt

若結(jié)點(diǎn)個(gè)數(shù)n=0，則有深度k=-1，滿(mǎn)足k=lb(0+1)-1=-1；若結(jié)點(diǎn)個(gè)數(shù)n=1，則有深度k=0，滿(mǎn)足k=lb(1+1)-1=0；若結(jié)點(diǎn)個(gè)數(shù)n=2，則有深度k=1，滿(mǎn)足k=lb(2+1)-1=0.xx=1；若結(jié)點(diǎn)個(gè)數(shù)n=3，則有深度k=1，滿(mǎn)足k=lb(3+1)-1=1。

編輯ppt性質(zhì)5對(duì)于一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，按照從上至下和從左至右的順序?qū)λ薪Y(jié)點(diǎn)從0開(kāi)始順序編號(hào),則對(duì)于序號(hào)為i的結(jié)點(diǎn)(0≤i<n),有：

(1)如果i>0，則其雙親是結(jié)點(diǎn)(i-1)/2(“/”表示整除）；如果i=0，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無(wú)雙親。

(2)如果2i+1＜n，其左孩子是結(jié)點(diǎn)2i+1；如果2i+1≥n，則結(jié)點(diǎn)i無(wú)左孩子。

(3)如果2i＋2＜n，其右孩子是結(jié)點(diǎn)2i＋2；如果2i＋2≥n，則結(jié)點(diǎn)i無(wú)右孩子。結(jié)論：如果完全二叉樹(shù)按照從上到下和從左到右的順序?qū)λ薪Y(jié)點(diǎn)順序編號(hào)，則可以用一維數(shù)組存儲(chǔ)完全二叉樹(shù)。二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)編輯ppt8.3.1二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)主要有三種：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和仿真指針存儲(chǔ)結(jié)構(gòu)。1.二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)完全二叉樹(shù)的結(jié)點(diǎn)可按從上至下和從左至右的次序存儲(chǔ)在一維數(shù)組中，其結(jié)點(diǎn)之間的關(guān)系可由公式計(jì)算得到，這就是二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)。下面兩棵樹(shù)在數(shù)組中的存儲(chǔ)結(jié)構(gòu)分別為：8.3二叉樹(shù)的設(shè)計(jì)和實(shí)現(xiàn)編輯pptABCDEF012345ABCDEF012345數(shù)據(jù)雙親左孩子右孩子012345ABCDEF和n=6比較和0比較-112034i05∧∧∧1∧∧1∧∧2編輯pptBACEDFGHIJKLMNOABCDONMLKJIHGFE12043576118109121314編輯ppt

對(duì)于一般的非完全二叉樹(shù)顯然不能直接使用二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)?？梢允紫仍诜峭耆鏄?shù)中增添一些并不存在的空結(jié)點(diǎn)使之變成完全二叉樹(shù)的形態(tài)，然后再用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。

BACEDFGHIJABCDJIHGFE1204357689編輯pptBACDEGFBACDEGF(a)一般二叉樹(shù)(b)完全二叉樹(shù)形態(tài)(c)在數(shù)組中的存儲(chǔ)形式

ABC∧G∧∧F∧∧∧ED1204357611810912數(shù)組下標(biāo)編輯ppt2.二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用指針建立二叉樹(shù)中結(jié)點(diǎn)之間的關(guān)系。二叉樹(shù)最常用的的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是二叉鏈。二叉鏈存儲(chǔ)結(jié)構(gòu)的每個(gè)結(jié)點(diǎn)包含三個(gè)域，分別是數(shù)據(jù)域data、左孩子指針域leftChild和右孩子指針域rightChild。二叉鏈存儲(chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)的圖示結(jié)構(gòu)為：

rightChilddataleftChild

二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)也有不帶頭結(jié)點(diǎn)和帶頭結(jié)點(diǎn)兩種。帶頭結(jié)點(diǎn)的二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)見(jiàn)下圖(b)，不帶頭結(jié)點(diǎn)的二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)如下圖(a)所示。編輯ppt圖8-10二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)root∧A∧BC∧D∧E∧F∧G∧∧∧rootA∧BC∧D∧E∧F∧G∧∧∧(a)不帶頭結(jié)點(diǎn)的二叉樹(shù)(b)帶頭結(jié)點(diǎn)的二叉樹(shù)編輯ppt3.二叉樹(shù)的仿真指針二叉樹(shù)的仿真指針存儲(chǔ)結(jié)構(gòu)是用數(shù)組存儲(chǔ)二叉樹(shù)中的結(jié)點(diǎn)，數(shù)組中每個(gè)結(jié)點(diǎn)除數(shù)據(jù)元素域外，再增加仿真指針域用于仿真常規(guī)指針建立二叉樹(shù)中結(jié)點(diǎn)之間的關(guān)系。二叉樹(shù)的仿真二叉鏈存儲(chǔ)結(jié)構(gòu)root∧A∧BC∧D∧E∧F∧G∧∧∧編輯ppt8.3.2二叉鏈結(jié)構(gòu)的二叉樹(shù)設(shè)計(jì)root∧A∧BC∧D∧E∧F∧G∧∧∧帶頭結(jié)點(diǎn)的二叉樹(shù)數(shù)據(jù)域右孩子指針結(jié)點(diǎn)于是，一棵二叉樹(shù)就可以用一個(gè)指向根節(jié)點(diǎn)上述結(jié)構(gòu)體的指針變量表示。用一個(gè)變量表示結(jié)構(gòu)體變量結(jié)構(gòu)體指針整體看待左孩子指針首先：定義相應(yīng)的結(jié)點(diǎn)結(jié)構(gòu)體編輯ppt二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)體定義typedefstructNode{ DataTypedata; structNode*leftChild; structNode*rightChild;}BiTreeNode;數(shù)據(jù)域右孩子指針左孩子指針編輯ppt初始化：對(duì)于給定的二叉樹(shù)化為空樹(shù)。voidInitiate(BiTreeNode**root){*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));(*root)->leftChild=NULL;(*root)->rightChild=NULL;}root∧A∧BC∧D∧E∧F∧G∧∧∧給定：BiTreeNode*root;∧編輯ppt/*左子樹(shù)插入結(jié)點(diǎn)*/功能：在當(dāng)前結(jié)點(diǎn)處插入一個(gè)新的結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)的左子樹(shù)；而當(dāng)前結(jié)點(diǎn)的原來(lái)左子樹(shù)變成新插入結(jié)點(diǎn)的左子樹(shù)。root∧A∧BC∧D∧E∧F∧G∧∧∧curr(1)確定當(dāng)前結(jié)點(diǎn)是否存在(2)斷其左子樹(shù)(引入新的指針)(3)創(chuàng)建新的結(jié)點(diǎn)s(4)s添加數(shù)據(jù)x×tsx(5)確定s的左右孩子∧(6)確定當(dāng)前結(jié)點(diǎn)curr的左孩子(7)還回插入結(jié)點(diǎn)的指針編輯ppt/*左子樹(shù)插入結(jié)點(diǎn)*/BiTreeNode*InsertLeftNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*t;

if(curr==NULL)returnNULL;t=curr->leftChild; s=(BiTreeNode*)malloc(sizeof(BiTreeNode)); s->data=x; s->leftChild=t; s->rightChild=NULL;

curr->leftChild=s; returncurr->leftChild; }編輯ppt/*右子樹(shù)插入結(jié)點(diǎn)*/---思想和左子樹(shù)插入相同BiTreeNode*InsertRightNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*t;

if(curr==NULL)returnNULL;t=curr->rightChild; s=(BiTreeNode*)malloc(sizeof(BiTreeNode)); s->data=x; s->rightChild=t; s->leftChild=NULL;

curr->rightChild=s; returncurr->rightChild; }編輯ppt/*刪除當(dāng)前結(jié)點(diǎn)的左子樹(shù)*/BiTreeNode*DeleteLeftTree(BiTreeNode*curr){if(________________________________________)returnNULL;

Destroy(&curr->leftChild);curr->leftChild=___________;returncurr;}root∧A∧BC∧D∧E∧F∧G∧∧∧curr存在否？存在否？curr==NULL||curr->leftChild==NULLNULL編輯ppt/*刪除當(dāng)前結(jié)點(diǎn)的右子樹(shù)*/BiTreeNode*DeleteRightTree(BiTreeNode*curr){if(curr==NULL||curr->rightChild==NULL)return______;

Destroy(&curr->rightChild);curr->rightChild=NULL;return________;}root∧A∧BC∧D∧E∧F∧G∧∧∧curr存在否？存在否？NULLcurr編輯ppt例8-1編寫(xiě)一個(gè)建立如圖8-10（b）所示的帶頭結(jié)點(diǎn)的二叉鏈存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的程序。#include<stdlib.h>#include<stdio.h>typedefcharDataType;#include"Bitree.h“Voidmain(void){BiTreeNode*root,*p;

Initiate(&root);p=InsertLeftNode(root,'A');p=_______________(p,'B');p=InsertLeftNode(_____,'D');p=InsertRightNode(p,______);p=InsertRightNode(____________________,'C');InsertLeftNode(p,'E');InsertRightNode(p,'F');}InsertLeftNodep'G'root->leftChildroot∧A∧BC∧D∧E∧F∧G∧∧∧編輯ppt8.4二叉樹(shù)遍歷1.二叉樹(shù)遍歷的基本方法

從二叉樹(shù)的定義知，一棵二叉樹(shù)由三部分組成：根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。若規(guī)定D,L,R分別代表“訪問(wèn)根結(jié)點(diǎn)”、“遍歷根結(jié)點(diǎn)的左子樹(shù)”和“遍歷根結(jié)點(diǎn)的右子樹(shù)”，根據(jù)遍歷算法對(duì)訪問(wèn)根結(jié)點(diǎn)處理的位置，稱(chēng)下面三種遍歷算法分別為前序遍歷（DLR）、中序遍歷（LDR）和后序遍歷（LRD）。8.4.1二叉樹(shù)遍歷編輯ppt前序遍歷（DLR）遞歸算法為：若二叉樹(shù)為空則算法結(jié)束；否則：（1）訪問(wèn)根結(jié)點(diǎn)；（2）前序遍歷根結(jié)點(diǎn)的左子樹(shù)；（3）前序遍歷根結(jié)點(diǎn)的右子樹(shù)。對(duì)于圖8-7（b）所示的二叉樹(shù)，前序遍歷訪問(wèn)結(jié)點(diǎn)的次序?yàn)椋篈BDGCEFroot∧A∧BC∧D∧E∧F∧G∧∧∧編輯ppt中序遍歷（LDR）遞歸算法為：若二叉樹(shù)為空則算法結(jié)束；否則：（1）中序遍歷根結(jié)點(diǎn)的左子樹(shù)；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷根結(jié)點(diǎn)的右子樹(shù)。對(duì)于圖8-7（b）所示的二叉樹(shù)，中序遍歷訪問(wèn)結(jié)點(diǎn)的次序?yàn)椋篋GBAECFroot∧A∧BC∧D∧E∧F∧G∧∧∧編輯ppt后序遍歷（LRD）遞歸算法為：若二叉樹(shù)為空則算法結(jié)束；否則：（1）后序遍歷根結(jié)點(diǎn)的左子樹(shù)；（2）后序遍歷根結(jié)點(diǎn)的右子樹(shù)；（3）訪問(wèn)根結(jié)點(diǎn)。對(duì)于圖8-7（b）所示的二叉樹(shù)，后序遍歷訪問(wèn)結(jié)點(diǎn)的次序?yàn)椋篏DBEFCAroot∧A∧BC∧D∧E∧F∧G∧∧∧編輯ppt

此外，二叉樹(shù)還有層序遍歷。層序遍歷的要求是：按二叉樹(shù)的層序次序（即從根結(jié)點(diǎn)層至葉結(jié)點(diǎn)層），同一層中按先左子樹(shù)再右子樹(shù)的次序遍歷二叉樹(shù)。它的特點(diǎn)是，在所有未被訪問(wèn)結(jié)點(diǎn)的集合中，排列在已訪問(wèn)結(jié)點(diǎn)集合中最前面結(jié)點(diǎn)的左子樹(shù)的根結(jié)點(diǎn)將最先被訪問(wèn)，然后是該結(jié)點(diǎn)的右子樹(shù)的根結(jié)點(diǎn)。這樣，如果把已訪問(wèn)的結(jié)點(diǎn)放在一個(gè)隊(duì)列中，那么，所有未被訪問(wèn)結(jié)點(diǎn)的訪問(wèn)次序就可以由存放在隊(duì)列中的已訪問(wèn)結(jié)點(diǎn)的出隊(duì)列次序決定。因此可以借助隊(duì)列實(shí)現(xiàn)二叉樹(shù)的層序遍歷。編輯ppt二叉樹(shù)的層序遍歷算法如下：（1）初始化設(shè)置一個(gè)隊(duì)列；（2）把根結(jié)點(diǎn)指針入隊(duì)列；（3）當(dāng)隊(duì)列非空時(shí)，循環(huán)執(zhí)行步驟（3.a）到步驟（3.c）；（3.a）出隊(duì)列取得一個(gè)結(jié)點(diǎn)指針，訪問(wèn)該結(jié)點(diǎn)；（3.b）若該結(jié)點(diǎn)的左子樹(shù)非空，則將該結(jié)點(diǎn)的左子樹(shù)指 針入隊(duì)列；（3.c）若該結(jié)點(diǎn)的右子樹(shù)非空，則將該結(jié)點(diǎn)的右子樹(shù)指 針入隊(duì)列；（4）結(jié)束。編輯ppt2.二叉樹(shù)的遍歷方法和二叉樹(shù)的結(jié)構(gòu)二叉樹(shù)是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)會(huì)有零個(gè)、一個(gè)或兩個(gè)孩子結(jié)點(diǎn)，一個(gè)二叉樹(shù)的遍歷序列不能決定一棵二叉樹(shù)，但某些不同的遍歷序列組合可以惟一確定一棵二叉樹(shù)?？梢宰C明，給定一棵二叉樹(shù)的前序遍歷序列和中序遍歷序列可以惟一確定一棵二叉樹(shù)的結(jié)構(gòu)。

當(dāng)對(duì)一個(gè)二叉樹(shù)用一種特定的遍歷方法來(lái)遍歷時(shí)，其遍歷序列一定是線性的，且是惟一的。編輯ppt8.4.2二叉鏈存儲(chǔ)結(jié)構(gòu)下二叉樹(shù)遍歷的實(shí)現(xiàn)(1/4)

root∧A∧BC∧D∧E∧F∧G∧∧∧前序遍歷思想：先根，再左子樹(shù)，最后右子樹(shù)前序遍歷思想遍歷左子樹(shù)前序遍歷思想遍歷右子樹(shù)函數(shù)實(shí)現(xiàn)：函數(shù)名PreOrder函數(shù)PreOrder的調(diào)用問(wèn)題函數(shù)PreOrder的調(diào)用問(wèn)題什么時(shí)候停止重復(fù)操作？!=NULL編輯ppt8.4.2二叉鏈存儲(chǔ)結(jié)構(gòu)下二叉樹(shù)遍歷的實(shí)現(xiàn)(2/4)

voidPreOrder(BiTreeNode*t,voidVisit(DataTypeitem))/*前序遍歷二叉樹(shù)t，訪問(wèn)操作為Visit()函數(shù)*/

{if(t!=NULL){ Visit(t->data); _____________(t->leftChild,Visit); PreOrder(t->rightChild,Visit);}}

為了通用性，把對(duì)結(jié)點(diǎn)的訪問(wèn)操作設(shè)計(jì)成前序遍歷二叉樹(shù)函數(shù)的一個(gè)函數(shù)虛參Visit()。PreOrder編輯pptABD∧G∧∧∧CE∧∧∧F∧∧編輯pptvoidInOrder(BiTreeNode*t,voidVisit(DataTypeitem))/*中序t*/{if(t!=NULL) {InOrder(t->leftChild,Visit); Visit(t->data); InOrder(t->rightChild,Visit); }}

voidPostOrder(BiTreeNode*t,voidVisit(DataTypeitem))/*后序*/{if(t!=NULL) {PostOrder(t->leftChild,Visit); PostOrder(t->rightChild,Visit); Visit(t->data); }}編輯ppt二叉樹(shù)撤消操作函數(shù)二叉樹(shù)的撤消操作實(shí)際上是二叉樹(shù)遍歷操作的一個(gè)具體應(yīng)用。由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)允許有左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)，所以在釋放某個(gè)結(jié)點(diǎn)的存儲(chǔ)空間前必須先釋放該結(jié)點(diǎn)左孩子結(jié)點(diǎn)的存儲(chǔ)空間和右孩子結(jié)點(diǎn)的存儲(chǔ)空間，因此，二叉樹(shù)撤消操作必須是后序遍歷的具體應(yīng)用。撤消操作算法實(shí)現(xiàn)如下：編輯pptvoidDestroy(BiTreeNode**root){if((*root)!=NULL&&(*root)->leftChild!=NULL)Destroy(&(*root)->leftChild);

if((*root)!=NULL&&(*root)->rightChild!=NULL) Destroy(&(*root)->rightChild);

free(*root);}rootroot存在否？左子樹(shù)存在否？右子樹(shù)存在否？撤銷(xiāo)撤銷(xiāo)釋放根結(jié)點(diǎn)撤銷(xiāo)編輯ppt8.4.3二叉樹(shù)遍歷的應(yīng)用

1打印二叉樹(shù)把二叉樹(shù)逆時(shí)針旋轉(zhuǎn)900C，按照二叉樹(shù)的凹入表示法打印二叉樹(shù)?？砂汛撕瘮?shù)設(shè)計(jì)成遞歸函數(shù)。由于把二叉樹(shù)逆時(shí)針旋轉(zhuǎn)900C后，在屏幕上方的首先是右子樹(shù)，然后是根結(jié)點(diǎn)，最后是左子樹(shù)，所以打印二叉樹(shù)算法是一種特殊的中序遍歷算法。編輯pptvoidPrintBiTree(BiTreeNode*bt,intn){inti; if(bt==NULL)return; PrintBiTree(bt->rightChild,n+1);

PrintBiTree(bt->leftChild,n+1);}for(i=0;i<=n-1;i++)printf("");if(n>=0){printf("---");printf("%c\n",bt->data);}編輯pptACF∧0123∧3E2編輯ppt在二叉樹(shù)中查找數(shù)據(jù)元素操作的要求是：在bt為根結(jié)點(diǎn)指針的二叉樹(shù)中查找數(shù)據(jù)元素x，若查找到數(shù)據(jù)元素x時(shí)返回該結(jié)點(diǎn)的指針；若查找不到數(shù)據(jù)元素x時(shí)返回空指針。在二叉樹(shù)bt中查找數(shù)據(jù)元素x算法可設(shè)計(jì)成先序遍歷算法，此時(shí)查找結(jié)點(diǎn)的次序是：首先在根結(jié)點(diǎn)查找，然后在左子樹(shù)查找，最后在右子樹(shù)查找。但是，和常規(guī)遞歸算法不同的是，此算法當(dāng)一個(gè)分支上的結(jié)點(diǎn)比較完仍未查找到數(shù)據(jù)元素x時(shí)，要返回到該結(jié)點(diǎn)的雙親結(jié)點(diǎn)處繼續(xù)查找。因此，此算法是一個(gè)回溯算法。2查找數(shù)據(jù)元素編輯pptBiTreeNode*Search(BiTreeNode*bt,DataTypex){BiTreeNode*p;if(bt==NULL)returnNULL; if(_________________)returnbt;if(bt->leftChild!=NULL){p=__________(bt->leftChild,x); if(________________)returnp; }if(____________________!=NULL){p=Search(bt->rightChild,x); if(p!=NULL)returnp; }

returnNULL;}先序遍歷查找bt->data==xSearchp!=NULLbt->rightChild編輯ppt例8-2編寫(xiě)一個(gè)程序，首先建立如圖8-10（b）所示的帶頭結(jié)點(diǎn)的二叉鏈存儲(chǔ)結(jié)構(gòu)二叉樹(shù)，然后打印該二叉樹(shù)，最后輸出分別按照前序遍歷二叉樹(shù)次序、中序遍歷二叉樹(shù)次序和后序遍歷二叉樹(shù)次序訪問(wèn)各結(jié)點(diǎn)的序列信息。設(shè)計(jì)：輸出顯示函數(shù)設(shè)計(jì)：按照某種遍歷方法輸出顯示二叉樹(shù)各結(jié)點(diǎn)的信息，其實(shí)就是把上述各遍歷二叉樹(shù)函數(shù)中的Visit()函數(shù)設(shè)計(jì)成輸出顯示結(jié)點(diǎn)信息的函數(shù)。Visit()函數(shù)設(shè)計(jì)如下：voidVisit(DataTypeitem){printf("%c",item);}

3.應(yīng)用舉例

編輯ppt8.6哈夫曼樹(shù)1.哈夫曼樹(shù)的基本概念

從A結(jié)點(diǎn)到B結(jié)點(diǎn)所經(jīng)過(guò)的分支序列叫做從A結(jié)點(diǎn)到B結(jié)點(diǎn)的路徑；從A結(jié)點(diǎn)到B結(jié)點(diǎn)所經(jīng)過(guò)的分支個(gè)數(shù)叫做從A結(jié)點(diǎn)到B結(jié)點(diǎn)的路徑長(zhǎng)度；從二叉樹(shù)的根結(jié)點(diǎn)到二叉樹(shù)中所有葉結(jié)點(diǎn)的路徑長(zhǎng)度之和稱(chēng)作該二叉樹(shù)的路徑長(zhǎng)度。設(shè)二叉樹(shù)有n個(gè)帶權(quán)值的葉結(jié)點(diǎn)，定義從二叉樹(shù)的根結(jié)點(diǎn)到二叉樹(shù)中所有葉結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)葉結(jié)點(diǎn)權(quán)值的乘積之和稱(chēng)作該二叉樹(shù)的帶權(quán)路徑長(zhǎng)度（WPL），即：WPL=

其中，wi為第i個(gè)葉結(jié)點(diǎn)的權(quán)值，li為從根結(jié)點(diǎn)到第i個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度。編輯ppt1357713571355(a)(b)(c)(d)713下圖所示二叉樹(shù)帶權(quán)路徑長(zhǎng)度分別為:二叉樹(shù)的帶權(quán)路徑長(zhǎng)度？二叉樹(shù)的葉結(jié)點(diǎn)數(shù)和權(quán)值？編輯ppt（a）WPL=1×2+3×2+5×2+7×2=32（b）WPL=1×2+3×3+5×3+7×1=33（c）WPL=7×3+5×3+3×2+1×1=43（d）WPL=1×3+3×3+5×2+7×1=29具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)稱(chēng)作哈夫曼（Huffman）樹(shù)（或稱(chēng)最優(yōu)二叉樹(shù)）。圖（d）的二叉樹(shù)是一棵哈夫曼樹(shù)。定義：由給定的n個(gè)葉結(jié)點(diǎn)權(quán)值可以構(gòu)造很多棵形態(tài)不同的二叉樹(shù)，WPL值最小的二叉樹(shù)稱(chēng)為哈夫曼樹(shù)。要使一棵二叉樹(shù)的帶權(quán)路徑長(zhǎng)度WPL值最小，必須使權(quán)值越大的葉結(jié)點(diǎn)越靠近根結(jié)點(diǎn)。哈夫曼樹(shù)構(gòu)造算法為：編輯ppt（1）由給定的n個(gè)權(quán)值{w1,w2,…,wn}構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹(shù)，從而得到一個(gè)二叉樹(shù)森林F={T1,T2,…,Tn}。（2）在二叉樹(shù)森林F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹(shù)作為新的二叉樹(shù)的左右子樹(shù)構(gòu)造新的二叉樹(shù)，新的二叉樹(shù)的根結(jié)點(diǎn)權(quán)值為左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。（3）在二叉樹(shù)森林F中刪除作為新二叉樹(shù)左右子樹(shù)的兩棵二叉樹(shù)，將新二叉樹(shù)加入到二叉樹(shù)森林F中。（4）重復(fù)步驟（2）和（3），當(dāng)二叉樹(shù)森林F中只剩下一棵二叉樹(shù)時(shí)，這棵二叉樹(shù)就是所構(gòu)造的哈夫曼樹(shù)。編輯ppt2.哈夫曼編碼問(wèn)題

將傳送的文字轉(zhuǎn)換為二進(jìn)制字符0和1組成的二進(jìn)制串的過(guò)程為編碼。

例：假設(shè)要傳送的電文為ABACCDA，電文中只有A,B,C,D四種字符，若這四個(gè)字符采用表(a)所示的編碼方案，則電文的代碼為00010010101100，代碼總長(zhǎng)度為14。若這四個(gè)字符采用表(b)所示的編碼方案，則電文的代碼為0110010101110，代碼總長(zhǎng)度為13。字符編碼A00B01C10D11字符編碼A0B110C10D111（a）（b）編輯ppt

哈夫曼樹(shù)可用于構(gòu)造代碼總長(zhǎng)度最短的編碼方案。具體構(gòu)造方法如下：設(shè)需要編碼的字符集合為{d1,d2,…,dn}，各個(gè)字符在電文中出現(xiàn)的次數(shù)集合為{w1,w2,…,wn}，以d1,d2,…,dn作為葉結(jié)點(diǎn)，以w1,w2,…,wn作為各葉結(jié)點(diǎn)的權(quán)值構(gòu)造一棵二叉樹(shù)，規(guī)定哈夫曼樹(shù)中的左分支為0，右分支為1，則從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)所經(jīng)過(guò)的分支對(duì)應(yīng)的0和1組成的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼。代碼總長(zhǎng)度最短的不等長(zhǎng)編碼稱(chēng)之為哈夫曼編碼。不等長(zhǎng)編碼不允許存在前綴碼。前綴碼的一個(gè)例子如：A為01，B為010。如編碼存在前綴碼，則譯碼會(huì)出現(xiàn)二義性。問(wèn)題：為什么哈夫曼編碼一定不會(huì)出現(xiàn)前綴碼？編輯ppt3.哈夫曼編碼的軟件設(shè)計(jì)構(gòu)造哈夫曼樹(shù):方便的實(shí)現(xiàn)從雙親結(jié)點(diǎn)到左右孩子結(jié)點(diǎn)的操作;哈夫曼編碼:方便的實(shí)現(xiàn)從孩子結(jié)點(diǎn)到雙親結(jié)點(diǎn)的操作。設(shè)計(jì)哈夫曼樹(shù)的結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)為雙親孩子存儲(chǔ)結(jié)構(gòu)。采用仿真指針實(shí)現(xiàn)，每個(gè)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)為：

weightflagparentleftChildrightChild一、哈夫曼編碼的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)n個(gè)葉結(jié)點(diǎn)的Haffman樹(shù)總共有2n-1個(gè)結(jié)點(diǎn)，因此這樣的樹(shù)可以用一個(gè)長(zhǎng)度為2n-1的一維數(shù)組來(lái)管理結(jié)構(gòu)數(shù)組編輯ppt

從哈夫曼樹(shù)求葉結(jié)點(diǎn)的哈夫曼編碼實(shí)際上是從葉結(jié)點(diǎn)到根結(jié)點(diǎn)路徑分支的逐個(gè)遍歷，每經(jīng)過(guò)一個(gè)分支就得到一位哈夫曼編碼值。存放哈夫曼編碼的數(shù)據(jù)元素結(jié)構(gòu)為：

startBit[0]Bit[1]…Bit[MaxBit-1]weight編碼的起始位置例如start=1.編碼區(qū)該weight對(duì)應(yīng)字符的對(duì)應(yīng)碼字為：Bit[1],Bit[2],…,Bit[MaxBit-1],結(jié)構(gòu)變量結(jié)構(gòu)數(shù)組編輯ppt二、哈夫曼編碼的算法實(shí)現(xiàn)typedefstruct//哈夫曼樹(shù)的結(jié)點(diǎn)結(jié)構(gòu){intweight; //權(quán)值

intflag; //標(biāo)記

intparent; //雙親結(jié)點(diǎn)下標(biāo)

intleftChild; //左孩子下標(biāo)

intrightChild; //右孩子下標(biāo)}HaffNode;typedefstruct//存放哈夫曼編碼的數(shù)據(jù)元素結(jié)構(gòu){intbit[MaxN]; //數(shù)組

intstart; //編碼的起始下標(biāo)

intweight; //字符的權(quán)值}Code;HaffNode類(lèi)型的結(jié)構(gòu)數(shù)組;長(zhǎng)度為2n-1Code類(lèi)型的結(jié)構(gòu)數(shù)組;長(zhǎng)度為n編輯ppt初始化w0w2w1w3……Wn-12*n-10123……n-1nn+1n+2……n+3選擇最小值m1和次小值m2記錄最小值m1的位置x1和次小值m2的位置x2計(jì)算m1+m2這為第n個(gè)結(jié)點(diǎn)，也就是第1個(gè)非葉結(jié)點(diǎn)Wn第1個(gè)非葉結(jié)點(diǎn)第2個(gè)非葉結(jié)點(diǎn)從{w0,w1,……,wn-1}-{wx1,wx2}+{wn}里面選擇最小和次??；為了方便，對(duì)每個(gè)結(jié)點(diǎn)引入一個(gè)標(biāo)志flag，flag=0表示余下的，flag=1表示去除的。flag00000……0000……0重復(fù)前面的操作11對(duì)于給定的n個(gè)權(quán)值結(jié)構(gòu)數(shù)組haffTree[2*n-1];編輯ppt第一步：初始化具有2*n-1個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)haffTree[2*n-1];第二步：對(duì)n-1個(gè)非葉結(jié)點(diǎn)進(jìn)行循環(huán)生成每個(gè)非葉結(jié)點(diǎn)都是從haffTree的第0個(gè)元素開(kāi)始到最近加入的非葉結(jié)點(diǎn)注意尋找最小值和次最小值(條件是標(biāo)記為0)根據(jù)找到的最小值和次最小值生成非葉結(jié)點(diǎn)修改相應(yīng)的權(quán)值、父母、孩子、標(biāo)記的值編輯ppt哈夫曼樹(shù)構(gòu)造算法如下：voidHaffman(intweight[],intn,HaffNodehaffTree[])//建立葉結(jié)點(diǎn)個(gè)數(shù)為n權(quán)值為weight的哈夫曼樹(shù)haffTree{inti,j,m1,m2,x1,x2;

//哈夫曼樹(shù)haffTree初始化。n個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)共有2n-1個(gè)結(jié)點(diǎn)

for(inti=0;i<2*n-1;i++){if(i<n)haffTree[i].weight=weight[i]; elsehaffTree[i].weight=0;haffTree[i].parent=-1;haffTree[i].flag=0;haffTree[i].leftChild=-1;haffTree[i].rightChild=-1;}編輯ppt

//構(gòu)造哈夫曼樹(shù)haffTree的n-1個(gè)非葉結(jié)點(diǎn)

for(i=0;i<n-1;i++){m1=m2=MaxValue; x1=x2=0; for(j=0;j<n+i;j++) {if(haffTree[j].weight<m1&&haffTree[j].flag==0) {m2=m1; x2=x1; m1=haffTree[j].weight; x1=j; } elseif(haffTree[j].weight<m2&&haffTree[j].flag==0) { m2=haffTree[j].weight; x2=j; }}在0--n+i-1中尋找最小和次小編輯ppt

//將找出的兩棵權(quán)值最小的子樹(shù)合并為一棵子樹(shù)

haffTree[x1].parent=n+i; haffTree[x2].parent=n+i; haffTree[x1].flag=1; haffTree[x2].flag=1; haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight; haffTree[n+i].leftChild=x1; haffTree[n+i].rightChild=x2;}}編輯ppt1A3B5C7D4916輸入huffTree和葉節(jié)點(diǎn)數(shù)n001臨時(shí)記錄編碼實(shí)際編碼001第0個(gè)葉節(jié)點(diǎn)當(dāng)作孩子結(jié)點(diǎn)找該孩子結(jié)點(diǎn)的父母結(jié)點(diǎn)確定該孩子是父母結(jié)點(diǎn)的左還是右確定編碼找到的父母結(jié)點(diǎn)當(dāng)作新的孩子父母結(jié)點(diǎn)存在否？找該孩子結(jié)點(diǎn)的父母結(jié)點(diǎn)臨時(shí)編碼起始位臨時(shí)編碼起始位減少1編輯ppt1A3B5C7D4916輸入huffTree和葉節(jié)點(diǎn)數(shù)n第1個(gè)葉節(jié)點(diǎn)當(dāng)作孩子結(jié)點(diǎn)找該孩子結(jié)點(diǎn)的父母結(jié)點(diǎn)確定該孩子是父母結(jié)點(diǎn)的左還是右確定編碼找到的父母結(jié)點(diǎn)當(dāng)作新的孩子101臨時(shí)記錄編碼實(shí)際編碼101父母結(jié)點(diǎn)存在否？找該孩子結(jié)點(diǎn)的父母結(jié)點(diǎn)臨時(shí)編碼起始位臨時(shí)編碼起始位減少1編輯ppt哈夫曼編碼算法如下：voidHaffmanCode(HaffNodehaffTree[],intn,CodehaffCode[]){Code*cd=(Code*)malloc(sizeof(Code));inti,j,child,parent;

/*求n個(gè)葉結(jié)點(diǎn)的哈夫曼編碼*/for(i=0;i<n;i++) {cd->start=n-1; cd->weight=haffTree[i].weight; child=i; parent=haffTree[child].parent;

編輯ppt

/*由葉結(jié)點(diǎn)向上直到根結(jié)點(diǎn)*/ while(parent!=-1) {if(haffTree[parent].leftChild==child) cd->bit[cd->start]=0; else cd->bit[cd->start]=1; cd->start--; child=parent; parent=haffTree[child].parent; } for(j=cd->start+1;j<n;j++) haffCode[i].bit[j]=cd->bit[j]; haffCode[i].start=cd->start+1; haffCode[i].weight=cd->weight; }}編輯ppt

例：設(shè)有字符集{A,B,C,D}，各字符在電文中出現(xiàn)的次數(shù)集為{1,3,5,7}，則哈夫曼樹(shù)構(gòu)造過(guò)程如下圖所示：下標(biāo)weightleftChildrightChildparentflag01-1-1-1013-1-1-1025-1-1-1037-1-1-1040-1-1-1050-1-1-1060-1-1-10（a）編輯ppt下標(biāo)weightleftChildrightChildparentflag01-1-14113-1-14125-1-1-1037-1-1-104401-1050-1-1-1060-1-1-10（b）第一步的結(jié)果編輯ppt下標(biāo)weightleftChildrightChildparentflag01-1-14113-1-14125-1-15137-1-1-104401515942-1060-1-1-10（c）第二步的結(jié)果編輯ppt下標(biāo)weightleftChildrightChildparentflag01-1-14113-1-14125-1-15137-1-16144015159426161635-10（d）哈夫曼樹(shù)構(gòu)造結(jié)果編輯ppt0123bitstartweight

（e）哈夫曼編碼結(jié)果

10011

10113

1125

037編輯ppt例8-5設(shè)有字符集{A,B,C,D}，各字符在電文中出現(xiàn)的次數(shù)集為{1,3,5,7}，設(shè)計(jì)各字符的哈夫曼編碼。#include<stdio.h>#include<stdlib.h>#defineMaxValue10000 #defineMaxBit4 #defineMaxN100#include"Haffman.h"編輯pptvoidmain(void){inti,j,n=4;intweight[]={1,3,5,7};

HaffNode*myHaffTree=(HaffNode*)malloc(sizeof(HaffNode)*(2*n-1));Code*myHaffCode=(Code*)malloc(sizeof(Code)*n);if(n>MaxN){printf("給出的n越界，修改MaxN值!\n"); exit(0);}Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode);

/*輸出每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼*/for(i=0;i<n;i++){printf("Weight=%dCode=",myHaffCode[i].weight); for(j=myHaffCode[i].start;j<n;j++) printf("%d",myHaffCode[i].bit[j]); printf("\n");}}編輯ppt程序運(yùn)行輸出結(jié)果如下：Weight=1Code=100Weight=3Code=101Weight=5Code=11Weight=7Code=0

該結(jié)果和圖8-15所示的該問(wèn)題的人工設(shè)計(jì)的哈夫曼編碼方案完全吻合。

編輯ppt8.4.4.非遞歸的二叉樹(shù)遍歷算法

所有遞歸算法都可以借助堆棧轉(zhuǎn)換成循環(huán)結(jié)構(gòu)的非遞歸算法，通常有兩種方法：一種方法是形式化模擬轉(zhuǎn)換，另一種方法是根據(jù)要求解問(wèn)題的特點(diǎn)設(shè)計(jì)借助堆棧的循環(huán)結(jié)構(gòu)算法。非遞歸的二叉樹(shù)前序遍歷算法如下：（1）初始化設(shè)置一個(gè)堆棧；（2）把根結(jié)點(diǎn)指針入棧；（3）當(dāng)堆棧非空時(shí)，循環(huán)執(zhí)行步驟（3.a）到步驟（3.c）；（3.a）出棧取得一個(gè)結(jié)點(diǎn)指針，訪問(wèn)該結(jié)點(diǎn)；（3.b）若該結(jié)點(diǎn)的右子樹(shù)非空，則將該結(jié)點(diǎn)的右子樹(shù)指 針入棧；（3.c）若該結(jié)點(diǎn)的左子樹(shù)非空，則將該結(jié)點(diǎn)的左子樹(shù)指 針入棧；（4）結(jié)束。編輯ppt問(wèn)題：（1）這個(gè)算法和哪個(gè)算法相似？（2）為什么相似？（3）非遞歸的二叉樹(shù)前序遍歷算法有什么用途？編輯ppt8.5線索二叉樹(shù)

線索二叉樹(shù)是另一種分步遍歷二叉樹(shù)的方法。它既可以從前向后分步遍歷二叉樹(shù)，又可以從后向前分步遍歷二叉樹(shù)。

當(dāng)按某種規(guī)則遍歷二叉樹(shù)時(shí)，保存遍歷時(shí)得到的結(jié)點(diǎn)的后繼結(jié)點(diǎn)信息和前驅(qū)結(jié)點(diǎn)信息的最常用的方法是建立線索二叉樹(shù)。對(duì)二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)分析可知，在有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中必定存在n+1個(gè)空鏈域。

編輯ppt

規(guī)定：當(dāng)某結(jié)點(diǎn)的左指針為空時(shí)，令該指針指向按某種方法遍歷二叉樹(shù)時(shí)得到的該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；當(dāng)某結(jié)點(diǎn)的右指針為空時(shí)，令該指針指向按某種方法遍歷二叉樹(shù)時(shí)得到的該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。僅僅這樣做會(huì)使我們不能區(qū)分左指針指向的結(jié)點(diǎn)到底是左孩子結(jié)點(diǎn)還是前驅(qū)結(jié)點(diǎn)，右指針指向的結(jié)點(diǎn)到底是右孩子結(jié)點(diǎn)還是后繼結(jié)點(diǎn)。因此我們?cè)僭诮Y(jié)點(diǎn)中增加兩個(gè)線索標(biāo)志位來(lái)區(qū)分這兩種情況。編輯ppt每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)就如下所示：leftThreadleftChilddatarightChildrightThread

結(jié)點(diǎn)中指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針?lè)Q為線索。在二叉樹(shù)的結(jié)點(diǎn)上加上線索的二叉樹(shù)稱(chēng)作線索二叉樹(shù)。對(duì)二叉樹(shù)以某種方法（如前序、中序或后序方法）遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程稱(chēng)作按該方法對(duì)二叉樹(shù)進(jìn)行的線索化。

線索標(biāo)志位定義如下：編輯pptADGECF(a)B010A00B10C01D01E11F11G1(b)010A00B10C01D01E11F11G1(d)010A00B10C01D01E11F11G1(c)rootrootroot線索二叉樹(shù)編輯ppt

一旦建立了某種方式的線索二叉樹(shù)后，用戶(hù)程序就可以像操作雙向鏈表一樣操作該線索二叉樹(shù)。例如，一旦建立了中序線索二叉樹(shù)后，用戶(hù)程序就可以設(shè)計(jì)一個(gè)正向循環(huán)結(jié)構(gòu)遍歷該二叉樹(shù)的所有結(jié)點(diǎn)，循環(huán)初始定位在中序線索二叉樹(shù)的第一個(gè)結(jié)點(diǎn)位置，每次循環(huán)使指針指向當(dāng)前結(jié)點(diǎn)的中序遍歷的后繼結(jié)點(diǎn)位置，當(dāng)指針指向中序線索二叉樹(shù)的最后一個(gè)結(jié)點(diǎn)位置后循環(huán)過(guò)程結(jié)束；或者用戶(hù)程序可以設(shè)計(jì)一個(gè)反向循環(huán)結(jié)構(gòu)遍歷該二叉樹(shù)的所有結(jié)點(diǎn)，循環(huán)初始定位在中序線索二叉樹(shù)的最后一個(gè)結(jié)點(diǎn)位置，每次循環(huán)使指針指向當(dāng)前結(jié)點(diǎn)的中序遍歷的前驅(qū)結(jié)點(diǎn)位置，當(dāng)指針指向中序線索二叉樹(shù)的第一個(gè)結(jié)點(diǎn)位置前循環(huán)過(guò)程結(jié)束。編輯ppt這種算法設(shè)計(jì)要求分別設(shè)計(jì)三個(gè)函數(shù)：First()：定位在第一個(gè)結(jié)點(diǎn)位置；Next()：移動(dòng)到下一個(gè)結(jié)點(diǎn)位置；End()：是否已經(jīng)到最后下一個(gè)結(jié)點(diǎn)位置；當(dāng)然，還需要一個(gè)根據(jù)二叉樹(shù)構(gòu)造線索二叉樹(shù)的函數(shù)。編輯ppttypedefstruct{ThreadBiNode*root;ThreadBiNode*current;intnextComplete;}ThreadBiTree;voidThreadInitiate(ThreadBiTree*tree,ThreadBiNode*root){tree->root=root;tree->current=root;if(root==NULL)tree->nextComplete=1;else tree->nextComplete=0;}編輯pptvoidFirst(ThreadBiTree*tree){tree->current=tree->root;while(tree->current->leftThread==0 tree->current=tree->current->leftChild;

if(tree->current==tree->root)tree->nextComplete=1;elsetree->nextComplete=0;}

編輯pptvoidNext(ThreadBiTree*tree){ThreadBiNode*p=tree->current->rightChild;if(tree->nextComplete==1) return;if(tree->current->rightThread==0)while(p->leftThread==0)p=p->leftChild;tree->current=p;if(tree->current==tree->root)tree->nextComplete=1;}

intEndOfNext(ThreadBiTree*tree){returntree->nextComplete;}編輯ppt例8-3編寫(xiě)一個(gè)程序，首先建立如圖8-10（a）所示的不帶頭結(jié)點(diǎn)的二叉樹(shù)，然后中序線索化該二叉樹(shù)，最后用循環(huán)結(jié)構(gòu)輸出該中序線索化二叉樹(shù)各結(jié)點(diǎn)的序列信息。編輯pptvoidmain(void){ThreadBiNode*root;ThreadBiTreetree;

MakeCharTree(&root);CreatInThread(&root);

printf("二叉樹(shù)中序正向遍歷序列為：");ThreadInitiate(&tree,root); /*循環(huán)初始化*/for(First(&tree);!EndOfNext(&tree);Next(&tree))printf("%c",tree.current->data);}編輯ppt8.7等價(jià)問(wèn)題1．等價(jià)關(guān)系和等價(jià)類(lèi)若集合X上的關(guān)系R是自反的、對(duì)稱(chēng)的和傳遞的，則稱(chēng)關(guān)系R是集合X上的等價(jià)關(guān)系。設(shè)關(guān)系R為定義在集合X上的二元關(guān)系，若對(duì)于每一個(gè)x∈X，都有(x,x)∈R，則稱(chēng)R是自反的。例如，相等關(guān)系就是自反關(guān)系。設(shè)關(guān)系R為定義在集合X上的二元關(guān)系，若對(duì)于任意的x,y∈X，若當(dāng)(x,y)∈R時(shí)，有(y,x)∈R，則稱(chēng)R是對(duì)稱(chēng)的。例如，相等關(guān)系就是對(duì)稱(chēng)關(guān)系。編輯ppt

等價(jià)關(guān)系的實(shí)質(zhì)是將集合中的元素分類(lèi)。若關(guān)系R是集合X上的一個(gè)等價(jià)關(guān)系，則可以按R將集合X劃分成若干互不相交的子集X1,X2,X3,…，這些子集的并X1∪X2∪X3∪…為集合X，則這些子集便稱(chēng)為集合X的關(guān)于R的等價(jià)類(lèi)。

設(shè)關(guān)系R為定義在集合X上的二元關(guān)系，如果對(duì)于任意的x,y,z∈X，若當(dāng)(x,y)∈R且(y,z)∈R時(shí)，有(x,z)∈R，則稱(chēng)關(guān)系R是傳遞的。例如，設(shè)集合X={1,2,3}，關(guān)系R={(1,2),(2,3),(1,3)}，則關(guān)系R是傳遞的。另外，相等關(guān)系也是傳遞關(guān)系。編輯ppt2．等價(jià)類(lèi)的應(yīng)用許多應(yīng)用問(wèn)題可以歸結(jié)為按給定的等價(jià)關(guān)系劃分某集合為等價(jià)類(lèi)，通常稱(chēng)這類(lèi)問(wèn)題為等價(jià)問(wèn)題。例如，要測(cè)試一個(gè)軟件是否存在問(wèn)題，這個(gè)軟件所有允許的輸入數(shù)據(jù)構(gòu)成了集合，這個(gè)集合中的元素通常很多。我們把軟件所有允許的輸入數(shù)據(jù)域劃分成若干子集合，然后從每一個(gè)子集合中選取少數(shù)具有代表性的數(shù)據(jù)作為測(cè)試用例。這樣的測(cè)試用例設(shè)計(jì)方法可以有效地避免大量的冗余測(cè)試。這種方法是一種常用的軟件黑盒測(cè)試用例設(shè)計(jì)方法。

編輯ppt3．確定等價(jià)類(lèi)的并查算法并查（UNION/FIND）算法是確定等價(jià)類(lèi)的有效算法。并查算法思想是：（1）令有n個(gè)元素的集合X中的每個(gè)元素各自構(gòu)成一個(gè)只含單個(gè)元素的子集X1,X2,X3,…,Xn；（2）重復(fù)讀入m個(gè)等價(jià)對(duì)(x,y)。對(duì)于每個(gè)讀入的等價(jià)對(duì)(x,y)，設(shè)x∈Xi，y∈Xj，如果Xi＝Xj，則不做任何操作；如果Xi≠Xj，則將Xj并入Xi，并將Xj置為空（或?qū)i并入Xj，并將Xi置為空）。。

編輯ppt

則上述算法執(zhí)行完后，子集合X1,X2,X3,…,Xn中所有非空子集合即為X的關(guān)于等價(jià)關(guān)系R的等價(jià)類(lèi)。上述算法之所以稱(chēng)為并查算法，是因?yàn)樵撍惴ㄖ饕刹⒉僮骱筒椴僮鹘M成。查操作完成判定某個(gè)元素所