數(shù)據(jù)結(jié)構(gòu)第08章.ppt

1、第8章 樹和二叉樹,樹 二叉樹 二叉樹設(shè)計 二叉樹遍歷 線索二叉樹 哈夫曼樹 等價問題 樹與二叉樹的轉(zhuǎn)換 樹的遍歷,主要知識點,8.1 樹,1.樹的定義,樹是由n(n0)個結(jié)點組成的有限集合T。n=0的樹稱為空樹；對n0的樹，有:(1)僅有一個特殊的結(jié)點稱為根結(jié)點，根結(jié)點沒有前驅(qū)結(jié)點；(2)當(dāng)n1時，除根結(jié)點外其余的結(jié)點分為m(m0)個互不相交的有限集合T1,T2，Tm，其中每個集合Ti本身又是一棵結(jié)構(gòu)和樹類似的子樹。,注：樹的定義具有遞歸性，即“樹中還有樹”。,若干術(shù)語,結(jié)點：由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之 間關(guān)系的指針組成,結(jié)點的度：結(jié)點所擁有的子樹的個數(shù),葉結(jié)點：度為0的結(jié)點，也稱作 終端結(jié)

2、點,分支結(jié)點：度不為0的結(jié)點,孩子結(jié)點：樹中一個結(jié)點的子樹的根結(jié)點,雙親結(jié)點：若樹中某結(jié)點有孩子結(jié)點，則這個結(jié)點就 稱作它的孩子結(jié)點的雙親結(jié)點,兄弟結(jié)點：具有相同的雙親結(jié)點的結(jié)點,樹的度：樹中所有結(jié)點的度的最大值,結(jié)點的層次：從根結(jié)點到樹中某結(jié)點所經(jīng)路徑上的分支數(shù),樹的深度：樹中所有結(jié)點的層次的最大值,無序樹：樹中任意一個結(jié)點的各孩子結(jié)點之間的次序 構(gòu)成無關(guān)緊要的樹,有序樹：樹中任意一個結(jié)點的各孩子結(jié)點有嚴(yán)格排列 次序的樹,森林：m（m0）棵樹的集合,2.樹的表示方法,(1)直觀表示法,(2)形式化表示法,(3)凹入表示法,T=（D，R） DF = D1D2Dm （1i,jm, DiDj=）

3、R=, i=1,2,n-1,A,B,C,D,E,F,G,H,I,J,K,L,3.樹的抽象數(shù)據(jù)類型,數(shù)據(jù)集合: 樹的結(jié)點集合，每個結(jié)點由數(shù)據(jù)元素和構(gòu)造數(shù) 據(jù)元素之間關(guān)系的指針組成。 操作集合: （1）創(chuàng)建MakeTree(T) （2）撤消DestroyTree(T) （3）雙親結(jié)點Parent(T, curr) （4）左孩子結(jié)點LeftChild(T, curr) （5）右兄弟結(jié)點RightSibling(T, curr) （6）遍歷樹Traverse(T, Visit(),4.樹的存儲結(jié)構(gòu),樹的結(jié)點之間的邏輯關(guān)系主要有雙親-孩子關(guān)系，兄弟關(guān)系。因此，從結(jié)點之間的邏輯關(guān)系分，樹的存儲結(jié)構(gòu)主要有：

4、雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法四種組合。 指針有常規(guī)指針和仿真指針,(1)雙親表示法,(a)一棵樹,（b)仿真指針的雙親表示法存儲結(jié)構(gòu),樹及其使用仿真指針的雙親表示法,(2)孩子表示法,雙親孩子表示法存儲結(jié)構(gòu),(3)雙親孩子表示法,(4)孩子兄弟表示法,常規(guī)指針的孩子兄弟表示法,8.2 二叉樹,一、二叉樹：是n(n0)個結(jié)點的有限集合。n=0的樹稱為空二叉樹；n0的二叉樹由一個根結(jié)點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成 。 邏輯結(jié)構(gòu)： 一對二（1:2） 基本特征: 每個結(jié)點最多只有兩棵子樹（不存在度大于2的結(jié)點）； 左子樹和右子樹次序不能顛倒。所以下面

5、是兩棵不同的樹,1.二叉樹的定義,二、滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點都存在左 子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的 二叉樹稱為滿二叉樹。 三、完全二叉樹：如果一棵深度為k，有n個結(jié)點的二叉樹中各 結(jié)點能夠與深度為k的順序編號的滿二叉樹從1到n標(biāo)號的 結(jié)點相對應(yīng)的二叉樹稱為完全二叉樹。如下圖所示,(a)滿二叉樹,(b)完全二叉樹,問題:一個高度為h的完全二叉樹最多有多少個結(jié)點?最少有多少個結(jié)點?,數(shù)據(jù)集合：二叉樹的結(jié)點集合，每個結(jié)點由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成。 操作集合： （1）創(chuàng)建MakeTree(T) （2）撤消DestroyTree(T) （3）左

6、插入結(jié)點InsertLeftNode(curr, x) （4）右插入結(jié)點InsertRightNode(curr, x) （5）左刪除子樹DeleteLeftTree(curr) （6）右刪除子樹DeleteRightTree(curr) （7）遍歷二叉樹Traverse(T, Visit(),2.二叉樹抽象數(shù)據(jù)類型,3.二叉樹的性質(zhì),性質(zhì)1 在一棵非空二叉樹的第i層上至多有2i個結(jié)點（i0）。,性質(zhì)2 深度為k的二叉樹至多有2k+1-1個結(jié)點。 說明：深度k=-1，表示沒有一個結(jié)點；深度k=0，表示只有一個根結(jié)點。,性質(zhì)3 對于一棵非空的二叉樹，如果葉結(jié)點個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則

7、有 n0= n2+1。 證明：設(shè)n為二叉樹的結(jié)點總數(shù)，n1為二叉樹中度為1的結(jié)點個數(shù)，則有： n = n0 + n1 + n2 另外，在二叉樹中，除根結(jié)點外的所有結(jié)點都有一個惟一的進(jìn)入分支，設(shè)M為二叉樹中所有結(jié)點的進(jìn)入分支數(shù)，則有： M = n - 1 從二叉樹的結(jié)構(gòu)可知，二叉樹的所有進(jìn)入分支是由度為1的結(jié)點和度為2的結(jié)點發(fā)出的，每個度為1的結(jié)點發(fā)出一個分支，每個度為2的結(jié)點發(fā)出兩個分支，所以又有： M = n1 + 2 n2 因此有： n - 1 = n1 + 2 n2 再把 n=n0+n1+n2 代入，則可以得到 n0 = n2 + 1。,性質(zhì)4 具有n個結(jié)點的完全二叉樹的深度k為大于或等

8、于lb(n+1)-1的最小整數(shù)。 證明：由性質(zhì)2和完全二叉樹的定義可知，對于有n個結(jié)點的深度為k的完全二叉樹有：2k-1 n 2k+1-1 移項有：2k n+1 2k+1 對不等式求對數(shù)，有：k lb(n+1) k+1 因為lb(n+1)介于k和k+1之間且大于k，而二叉樹的深度又只能是整數(shù)，所以必有k為大于或等于lb(n+1)-1的最小整數(shù)。 可簡寫為k=lb(n+1)-1。例如，2.0=2，2.1=3。 若結(jié)點個數(shù)n=0，則有深度k=-1，滿足k=lb(0+1)-1=-1； 若結(jié)點個數(shù)n=1，則有深度k=0，滿足k=lb(1+1)-1=0； 若結(jié)點個數(shù)n=2，則有深度k=1，滿足k=lb(

9、2+1)-1 =0.xx =1； 若結(jié)點個數(shù)n=3，則有深度k=1，滿足k=lb(3+1)-1=1。,性質(zhì)5 對于一棵有n個結(jié)點的完全二叉樹，按照從上至下和從左至右的順序?qū)λ薪Y(jié)點從0開始順序編號,則對于序號為i的結(jié)點(0i 0，則其雙親是結(jié)點(i-1)/2(“/”表示整除） ；如果i=0，則結(jié)點i是根結(jié)點，無雙親。 (2)如果2i+1n ，其左孩子是結(jié)點2i+1；如果2i+1n，則結(jié)點i無左孩子。 (3)如果2i2n，其右孩子是結(jié)點2i2；如果2i2n，則結(jié)點i無右孩子。,8.3.1二叉樹的存儲結(jié)構(gòu) 二叉樹的存儲結(jié)構(gòu)主要有三種：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié) 構(gòu)和仿真指針存儲結(jié)構(gòu)。 1. 二叉樹的

10、順序存儲結(jié)構(gòu) 完全二叉樹的結(jié)點可按從上至下和從左至右的次序存儲在一維數(shù)組中，其結(jié)點之間的關(guān)系可由公式計算得到，這就是二叉樹的順序存儲結(jié)構(gòu)。下面兩棵樹在數(shù)組中的存儲結(jié)構(gòu)分別為：,8.3二叉樹的設(shè)計和實現(xiàn),對于一般的非完全二叉樹顯然不能直接使用二叉樹的順序存儲結(jié)構(gòu)?？梢允紫仍诜峭耆鏄渲性鎏硪恍┎⒉淮嬖诘目战Y(jié)點使之變成完全二叉樹的形態(tài)，然后再用順序存儲結(jié)構(gòu)存儲。,(a)一般二叉樹,(b)完全二叉樹形態(tài),(c) 在數(shù)組中的存儲形式,2. 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu) 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用指針建立二叉樹中結(jié)點之間的關(guān)系。二叉樹最常用的的鏈?zhǔn)酱鎯Y(jié)構(gòu)是二叉鏈。二叉鏈存儲結(jié)構(gòu)的每個結(jié)點包含三個域，分別是數(shù)據(jù)

11、域data、左孩子指針域leftChild和右孩子指針域rightChild。二叉鏈存儲結(jié)構(gòu)中每個結(jié)點的圖示結(jié)構(gòu)為：,二叉鏈存儲結(jié)構(gòu)的二叉樹也有不帶頭結(jié)點和帶頭結(jié)點兩種。帶頭結(jié)點的二叉鏈存儲結(jié)構(gòu)的二叉樹見下圖(b)，不帶頭結(jié)點的二叉鏈存儲結(jié)構(gòu)的二叉樹如下圖(a)所示。,圖8-10 二叉鏈存儲結(jié)構(gòu)的二叉樹,(a)不帶頭結(jié)點的二叉樹,(b)帶頭結(jié)點的二叉樹,3.二叉樹的仿真指針 二叉樹的仿真指針存儲結(jié)構(gòu)是用數(shù)組存儲二叉樹中的結(jié)點，數(shù)組中每個結(jié)點除數(shù)據(jù)元素域外，再增加仿真指針域用于仿真常規(guī)指針建立二叉樹中結(jié)點之間的關(guān)系。,二叉樹的仿真二叉鏈存儲結(jié)構(gòu),8.3.2二叉鏈結(jié)構(gòu)的二叉樹設(shè)計,typedef

12、struct Node DataType data; struct Node *leftChild; struct Node *rightChild; BiTreeNode; /*初始化*/ void Initiate(BiTreeNode *root) *root = (BiTreeNode *)malloc(sizeof(BiTreeNode); (*root)-leftChild = NULL; (*root)-rightChild = NULL; ,/*左子樹插入結(jié)點*/ BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x)

13、BiTreeNode *s, *t; if(curr = NULL) return NULL; t = curr-leftChild; s = (BiTreeNode *)malloc(sizeof(BiTreeNode); s-data = x; s-leftChild = t; s-rightChild = NULL; curr-leftChild = s; return curr-leftChild; ,/*刪除左子樹*/ BiTreeNode *DeleteLeftTree(BiTreeNode *curr) if(curr = NULL | curr-leftChild = NULL

14、) return NULL; Destroy( ,例8-1 編寫一個建立如圖8-10（b）所示的帶頭結(jié)點的二叉鏈存儲結(jié)構(gòu)二叉樹的程序。 #include #include typedef char DataType; #include Bitree.h“ Void main(void) BiTreeNode *root, *p, *pp; Initiate( ,8.4 二叉樹遍歷,1.二叉樹遍歷的基本方法,從二叉樹的定義知，一棵二叉樹由三部分組成：根結(jié)點、左子樹和右子樹。若規(guī)定D,L,R分別代表“訪問根結(jié)點”、“遍歷根結(jié)點的左子樹”和“遍歷根結(jié)點的右子樹”，根據(jù)遍歷算法對訪問根結(jié)點處理的位置，

15、稱下面三種遍歷算法分別為前序遍歷（DLR）、中序遍歷（LDR）和后序遍歷（LRD）。,8.4.1 二叉樹遍歷,前序遍歷（DLR）遞歸算法為： 若二叉樹為空則算法結(jié)束；否則： （1）訪問根結(jié)點； （2）前序遍歷根結(jié)點的左子樹； （3）前序遍歷根結(jié)點的右子樹。 對于圖8-7（b）所示的二叉樹，前序遍歷訪問結(jié)點的次序為： A B D G C E F,中序遍歷（LDR）遞歸算法為： 若二叉樹為空則算法結(jié)束；否則： （1）中序遍歷根結(jié)點的左子樹； （2）訪問根結(jié)點； （3）中序遍歷根結(jié)點的右子樹。 對于圖8-7（b）所示的二叉樹，中序遍歷訪問結(jié)點的次序為： D G B A E C F,后序遍歷（LRD）

16、遞歸算法為： 若二叉樹為空則算法結(jié)束；否則： （1）后序遍歷根結(jié)點的左子樹； （2）后序遍歷根結(jié)點的右子樹； （3）訪問根結(jié)點。 對于圖8-7（b）所示的二叉樹，后序遍歷訪問結(jié)點的次序為： G D B E F C A,此外，二叉樹還有層序遍歷。層序遍歷的要求是：按二叉樹的層序次序（即從根結(jié)點層至葉結(jié)點層），同一層中按先左子樹再右子樹的次序遍歷二叉樹。 它的特點是，在所有未被訪問結(jié)點的集合中，排列在已訪問結(jié)點集合中最前面結(jié)點的左子樹的根結(jié)點將最先被訪問，然后是該結(jié)點的右子樹的根結(jié)點。這樣，如果把已訪問的結(jié)點放在一個隊列中，那么，所有未被訪問結(jié)點的訪問次序就可以由存放在隊列中的已訪問結(jié)點的出隊列次

17、序決定。因此可以借助隊列實現(xiàn)二叉樹的層序遍歷。,二叉樹的層序遍歷算法如下： （1）初始化設(shè)置一個隊列； （2）把根結(jié)點指針入隊列； （3）當(dāng)隊列非空時，循環(huán)執(zhí)行步驟（3.a）到步驟（3.c）； （3.a）出隊列取得一個結(jié)點指針，訪問該結(jié)點； （3.b）若該結(jié)點的左子樹非空，則將該結(jié)點的左子樹指針入隊列； （3.c）若該結(jié)點的右子樹非空，則將該結(jié)點的右子樹指針入隊列； （4）結(jié)束。,2.二叉樹的遍歷方法和二叉樹的結(jié)構(gòu) 二叉樹是非線性結(jié)構(gòu)，每個結(jié)點會有零個、一個或兩個孩子結(jié)點，一個二叉樹的遍歷序列不能決定一棵二叉樹，但某些不同的遍歷序列組合可以惟一確定一棵二叉樹?？梢宰C明，給定一棵二叉樹的前序遍歷

18、序列和中序遍歷序列可以惟一確定一棵二叉樹的結(jié)構(gòu)。,當(dāng)對一個二叉樹用一種特定的遍歷方法來遍歷時，其遍歷序列一定是線性的，且是惟一的。,8.4.2 二叉鏈存儲結(jié)構(gòu)下二叉樹遍歷的實現(xiàn) void PreOrder(BiTreeNode *t, void Visit(DataType item) /*前序遍歷二叉樹t，訪問操作為Visit()函數(shù)*/ if(t != NULL) Visit(t-data); PreOrder(t-leftChild, Visit); PreOrder(t-rightChild, Visit); 為了通用性，把訪問操作設(shè)計成前序遍歷二叉樹函數(shù)的一個函數(shù)虛參 Visit()

19、。,void InOrder(BiTreeNode *t, void Visit(DataType item) /*中序遍歷二叉樹t */ if(t != NULL) InOrder(t-leftChild, Visit); Visit(t-data); InOrder(t-rightChild, Visit); void PostOrder(BiTreeNode *t, void Visit(DataType item) /*后序遍歷二叉樹t */ if(t != NULL) PostOrder(t-leftChild, Visit); PostOrder(t-rightChild, Vis

20、it); Visit(t-data); ,二叉樹撤消操作函數(shù),二叉樹的撤消操作實際上是二叉樹遍歷操作的一個具體應(yīng)用。由于二叉樹中每個結(jié)點允許有左孩子結(jié)點和右孩子結(jié)點，所以在釋放某個結(jié)點的存儲空間前必須先釋放該結(jié)點左孩子結(jié)點的存儲空間和右孩子結(jié)點的存儲空間，因此，二叉樹撤消操作必須是后序遍歷的具體應(yīng)用。撤消操作算法實現(xiàn)如下：,void Destroy(BiTreeNode *root) if(*root) != NULL ,8.4.3 二叉樹遍歷的應(yīng)用,1 打印二叉樹 把二叉樹逆時針旋轉(zhuǎn)900C，按照二叉樹的凹入表示法打印二叉樹。可把此函數(shù)設(shè)計成遞歸函數(shù)。由于把二叉樹逆時針旋轉(zhuǎn)900C后，在屏幕

21、上方的首先是右子樹，然后是根結(jié)點，最后是左子樹，所以打印二叉樹算法是一種特殊的中序遍歷算法。,void PrintBiTree(BiTreeNode *bt, int n) int i; if(bt = NULL) return; PrintBiTree(bt-rightChild, n+1); for(i = 0; i 0) printf(-); printf(%cn, bt-data); PrintBiTree(bt-leftChild, n+1); ,在二叉樹中查找數(shù)據(jù)元素操作的要求是：在bt為根結(jié)點指針的二叉樹中查找數(shù)據(jù)元素x，若查找到數(shù)據(jù)元素x時返回該結(jié)點的指針；若查找不到數(shù)據(jù)元素x

22、時返回空指針。 在二叉樹bt中查找數(shù)據(jù)元素x算法可設(shè)計成先序遍歷算法，此時查找結(jié)點的次序是：首先在根結(jié)點查找，然后在左子樹查找，最后在右子樹查找。但是，和常規(guī)遞歸算法不同的是，此算法當(dāng)一個分支上的結(jié)點比較完仍未查找到數(shù)據(jù)元素x時，要返回到該結(jié)點的雙親結(jié)點處繼續(xù)查找。因此，此算法是一個回溯算法 。,2 查找數(shù)據(jù)元素,BiTreeNode *Search(BiTreeNode *bt, DataType x) BiTreeNode *p; if(bt = NULL) return NULL; if(bt-data = x) return bt; if(bt-leftChild != NULL) p

23、 = Search(bt-leftChild, x); if(p != NULL) return p; if(bt-rightChild != NULL) p = Search(bt-rightChild, x); if(p != NULL) return p; return NULL; ,例8-2 編寫一個程序，首先建立如圖8-10（b）所示的帶頭結(jié)點的二叉鏈存儲結(jié)構(gòu)二叉樹，然后打印該二叉樹，最后輸出分別按照前序遍歷二叉樹次序、中序遍歷二叉樹次序和后序遍歷二叉樹次序訪問各結(jié)點的序列信息。 設(shè)計： 輸出顯示函數(shù)設(shè)計：按照某種遍歷方法輸出顯示二叉樹各結(jié)點的信息，其實就是把上述各遍歷二叉樹函數(shù)中的

24、Visit()函數(shù)設(shè)計成輸出顯示結(jié)點信息的函數(shù)。Visit()函數(shù)設(shè)計如下： void Visit(DataType item) printf(%c , item); ,3.應(yīng)用舉例,8.4.4.非遞歸的二叉樹遍歷算法,所有遞歸算法都可以借助堆棧轉(zhuǎn)換成循環(huán)結(jié)構(gòu)的非遞歸算法，通常有兩種方法：一種方法是形式化模擬轉(zhuǎn)換，另一種方法是根據(jù)要求解問題的特點設(shè)計借助堆棧的循環(huán)結(jié)構(gòu)算法。,非遞歸的二叉樹前序遍歷算法如下： （1）初始化設(shè)置一個堆棧； （2）把根結(jié)點指針入棧； （3）當(dāng)堆棧非空時，循環(huán)執(zhí)行步驟（3.a）到步驟（3.c）； （3.a）出棧取得一個結(jié)點指針，訪問該結(jié)點；,（3.b）若該結(jié)點的右子樹

25、非空，則將該結(jié)點的右子樹指針入棧； （3.c）若該結(jié)點的左子樹非空，則將該結(jié)點的左子樹指針入棧； （4）結(jié)束。 問題： （1）這個算法和哪個算法相似？ （2）為什么相似？ （3）非遞歸的二叉樹前序遍歷算法有什么用途？,8.5 線索二叉樹,線索二叉樹是另一種分步遍歷二叉樹的方法。它既可以從前向后分步遍歷二叉樹，又可以從后向前分步遍歷二叉樹。,當(dāng)按某種規(guī)則遍歷二叉樹時，保存遍歷時得到的結(jié)點的后繼結(jié)點信息和前驅(qū)結(jié)點信息的最常用的方法是建立線索二叉樹。 對二叉鏈存儲結(jié)構(gòu)的二叉樹分析可知，在有n個結(jié)點的二叉樹中必定存在n+1個空鏈域。,規(guī)定：當(dāng)某結(jié)點的左指針為空時，令該指針指向按某種方法遍歷二叉樹時得到

26、的該結(jié)點的前驅(qū)結(jié)點；當(dāng)某結(jié)點的右指針為空時，令該指針指向按某種方法遍歷二叉樹時得到的該結(jié)點的后繼結(jié)點。僅僅這樣做會使我們不能區(qū)分左指針指向的結(jié)點到底是左孩子結(jié)點還是前驅(qū)結(jié)點，右指針指向的結(jié)點到底是右孩子結(jié)點還是后繼結(jié)點。因此我們再在結(jié)點中增加兩個線索標(biāo)志位來區(qū)分這兩種情況。線索標(biāo)志位定義如下：,每個結(jié)點的結(jié)構(gòu)就如下所示：,結(jié)點中指向前驅(qū)結(jié)點和后繼結(jié)點的指針稱為線索。在二叉樹的結(jié)點上加上線索的二叉樹稱作線索二叉樹。對二叉樹以某種方法（如前序、中序或后序方法）遍歷使其變?yōu)榫€索二叉樹的過程稱作按該方法對二叉樹進(jìn)行的線索化。,線索二叉樹,一旦建立了某種方式的線索二叉樹后，用戶程序就可以像操作雙向鏈表一

27、樣操作該線索二叉樹。 例如，一旦建立了中序線索二叉樹后，用戶程序就可以設(shè)計一個正向循環(huán)結(jié)構(gòu)遍歷該二叉樹的所有結(jié)點，循環(huán)初始定位在中序線索二叉樹的第一個結(jié)點位置，每次循環(huán)使指針指向當(dāng)前結(jié)點的中序遍歷的后繼結(jié)點位置，當(dāng)指針指向中序線索二叉樹的最后一個結(jié)點位置后循環(huán)過程結(jié)束；或者用戶程序可以設(shè)計一個反向循環(huán)結(jié)構(gòu)遍歷該二叉樹的所有結(jié)點，循環(huán)初始定位在中序線索二叉樹的最后一個結(jié)點位置，每次循環(huán)使指針指向當(dāng)前結(jié)點的中序遍歷的前驅(qū)結(jié)點位置，當(dāng)指針指向中序線索二叉樹的第一個結(jié)點位置前循環(huán)過程結(jié)束。,這種算法設(shè)計要求分別設(shè)計三個函數(shù)： First()：定位在第一個結(jié)點位置； Next()：移動到下一個結(jié)點位置；

28、 End()：是否已經(jīng)到最后下一個結(jié)點位置； 當(dāng)然，還需要一個根據(jù)二叉樹構(gòu)造線索二叉樹的函數(shù)。,typedef struct ThreadBiNode *root; ThreadBiNode *current; int nextComplete; ThreadBiTree; void ThreadInitiate(ThreadBiTree *tree, ThreadBiNode *root) tree-root = root; tree-current = root; if(root = NULL) tree-nextComplete = 1; else tree-nextComplete =

29、 0; ,void First(ThreadBiTree *tree) tree-current = tree-root; while(tree-current-leftThread = 0 tree-current = tree-current-leftChild; if(tree-current = tree-root) tree-nextComplete = 1; else tree-nextComplete = 0; ,void Next(ThreadBiTree *tree) ThreadBiNode *p = tree-current-rightChild; if(tree-nex

30、tComplete = 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; int EndOfNext(ThreadBiTree *tree) return tree-nextComplete; ,例8-3 編寫一個程序，首先建立如圖8-10（a）所示的不帶頭結(jié)點的二叉樹，然后中序線索化該二叉樹，最后用循環(huán)結(jié)構(gòu)輸出該中序線索化二叉樹各結(jié)點的序

31、列信息。,void main(void) ThreadBiNode *root; ThreadBiTree tree; MakeCharTree( ,8.6 哈夫曼樹,1.哈夫曼樹的基本概念,從A結(jié)點到B結(jié)點所經(jīng)過的分支序列叫做從A結(jié)點到B結(jié)點的路徑；從A結(jié)點到B結(jié)點所經(jīng)過的分支個數(shù)叫做從A結(jié)點到B結(jié)點的路徑長度；從二叉樹的根結(jié)點到二叉樹中所有葉結(jié)點的路徑長度之和稱作該二叉樹的路徑長度。設(shè)二叉樹有n個帶權(quán)值的葉結(jié)點，定義從二叉樹的根結(jié)點到二叉樹中所有葉結(jié)點的路徑長度與相應(yīng)葉結(jié)點權(quán)值的乘積之和稱作該二叉樹的帶權(quán)路徑長度（WPL），即：,WPL =,其中，wi為第i個葉結(jié)點的權(quán)值，li為從根結(jié)點到

32、第i個葉結(jié)點的路徑長度。,下圖所示二叉樹帶權(quán)路徑長度分別為:,（a）WPL = 12+32+52+72 = 32 （b）WPL = 12+33+53+71 = 33 （c）WPL = 73+53+32+11 = 43 （d）WPL = 13+33+52+71 = 29,具有最小帶權(quán)路徑長度的二叉樹稱作哈夫曼（Huffman）樹（或稱最優(yōu)二叉樹）。圖（d）的二叉樹是一棵哈夫曼樹。,定義：由給定的n個葉結(jié)點權(quán)值可以構(gòu)造很多棵形態(tài)不同的二叉樹，WPL值最小的二叉樹稱為哈夫曼樹。 要使一棵二叉樹的帶權(quán)路徑長度WPL值最小，必須使權(quán)值越大的葉結(jié)點越靠近根結(jié)點。哈夫曼樹構(gòu)造算法為：,（1）由給定的n個權(quán)值

33、w1,w2,wn構(gòu)造n棵只有根結(jié)點的二叉樹，從而得到一個二叉樹森林F=T1,T2,Tn。 （2）在二叉樹森林F中選取根結(jié)點的權(quán)值最小和次小的兩棵二叉樹作為新的二叉樹的左右子樹構(gòu)造新的二叉樹，新的二叉樹的根結(jié)點權(quán)值為左右子樹根結(jié)點權(quán)值之和。 （3）在二叉樹森林F中刪除作為新二叉樹左右子樹的兩棵二叉樹，將新二叉樹加入到二叉樹森林F中。 （4）重復(fù)步驟（2）和（3），當(dāng)二叉樹森林F中只剩下一棵二叉樹時，這棵二叉樹就是所構(gòu)造的哈夫曼樹。,2.哈夫曼編碼問題,將傳送的文字轉(zhuǎn)換為二進(jìn)制字符0和1組成的二進(jìn)制串的過程為編碼。,例：假設(shè)要傳送的電文為ABACCDA，電文中只有A,B,C,D四種字符，若這四個字

34、符采用表(a)所示的編碼方案，則電文的代碼為00 01 00 10 10 11 00，代碼總長度為14。若這四個字符采用表(b)所示的編碼方案，則電文的代碼為0 110 0 10 10 111 0，代碼總長度為13。,（a）,（b）,哈夫曼樹可用于構(gòu)造代碼總長度最短的編碼方案。具體構(gòu)造方法如下：設(shè)需要編碼的字符集合為d1,d2,dn，各個字符在電文中出現(xiàn)的次數(shù)集合為w1,w2,wn，以d1,d2,dn作為葉結(jié)點，以w1,w2,wn作為各葉結(jié)點的權(quán)值構(gòu)造一棵二叉樹，規(guī)定哈夫曼樹中的左分支為0，右分支為1，則從根結(jié)點到每個葉結(jié)點所經(jīng)過的分支對應(yīng)的0和1組成的序列便為該結(jié)點對應(yīng)字符的編碼。代碼總長度

35、最短的不等長編碼稱之為哈夫曼編碼。 不等長編碼不允許存在前綴碼。前綴碼的一個例子如：A為01，B為010。如編碼存在前綴碼，則譯碼會出現(xiàn)二義性。 問題：為什么哈夫曼編碼一定不會出現(xiàn)前綴碼？,3.哈夫曼編碼的軟件設(shè)計,為了在構(gòu)造哈夫曼樹時能方便的實現(xiàn)從雙親結(jié)點到左右孩子結(jié)點的操作，在進(jìn)行哈夫曼編碼時能方便的實現(xiàn)從孩子結(jié)點到雙親結(jié)點的操作。設(shè)計哈夫曼樹的結(jié)點存儲結(jié)構(gòu)為雙親孩子存儲結(jié)構(gòu)。采用仿真指針實現(xiàn)，每個結(jié)點的數(shù)據(jù)結(jié)構(gòu)設(shè)計為：,一、哈夫曼編碼的數(shù)據(jù)結(jié)構(gòu)設(shè)計,從哈夫曼樹求葉結(jié)點的哈夫曼編碼實際上是從葉結(jié)點到根結(jié)點路徑分支的逐個遍歷，每經(jīng)過一個分支就得到一位哈夫曼編碼值。存放哈夫曼編碼的數(shù)據(jù)元素結(jié)構(gòu)

36、為：,二、哈夫曼編碼的算法實現(xiàn),typedef struct /哈夫曼樹的結(jié)點結(jié)構(gòu) int weight; /權(quán)值 int flag;/標(biāo)記 int parent; /雙親結(jié)點下標(biāo) int leftChild;/左孩子下標(biāo) int rightChild;/右孩子下標(biāo) HaffNode; typedef struct /存放哈夫曼編碼的數(shù)據(jù)元素結(jié)構(gòu) int bitMaxN;/數(shù)組 int start; /編碼的起始下標(biāo) int weight; /字符的權(quán)值 Code;,哈夫曼樹構(gòu)造算法如下： void Haffman(int weight, int n, HaffNode haffTree) /

37、建立葉結(jié)點個數(shù)為n權(quán)值為weight的哈夫曼樹haffTree int j, m1, m2, x1, x2; /哈夫曼樹haffTree初始化。n個葉結(jié)點的哈夫曼樹共有2n-1個結(jié)點 for(int i = 0; i 2 * n - 1 ; i+) if(i n) haffTreei.weight = weighti; else haffTreei.weight = 0; haffTreei.parent = -1; haffTreei.flag = 0; haffTreei.leftChild = -1; haffTreei.rightChild = -1; ,/構(gòu)造哈夫曼樹haffTree

38、的n-1個非葉結(jié)點 for(i = 0;i n-1;i+) m1 = m2 = MaxValue; x1 = x2 = 0; for(j = 0; j n+i;j+) if(haffTreej.weight m1 ,/將找出的兩棵權(quán)值最小的子樹合并為一棵子樹 haffTreex1.parent = n+i; haffTreex2.parent = n+i; haffTreex1.flag = 1; haffTreex2.flag = 1; haffTreen+i.weight = haffTreex1.weight+haffTreex2.weight; haffTreen+i.leftChil

39、d = x1; haffTreen+i.rightChild = x2; ,哈夫曼編碼算法如下： void HaffmanCode(HaffNode haffTree, int n, Code haffCode) Code *cd = (Code *)malloc(sizeof(Code); int i, j, child, parent; /*求n個葉結(jié)點的哈夫曼編碼*/ for(i = 0; i start = n-1; cd-weight = haffTreei.weight; child = i; parent = haffTreechild.parent;,/*由葉結(jié)點向上直到根結(jié)點

40、*/ while(parent != -1) if(haffTreeparent.leftChild = child) cd-bitcd-start = 0; else cd-bitcd-start = 1; cd-start-; child = parent; parent = haffTreechild.parent; for(j = cd-start+1; j bitj; haffCodei.start = cd-start + 1; haffCodei.weight = cd-weight; ,例：設(shè)有字符集A, B, C, D，各字符在電文中出現(xiàn)的次數(shù)集為1, 3, 5, 7，則哈夫

41、曼樹構(gòu)造過程如下圖所示：,（a）,（b）第一步的結(jié)果,（c）第二步的結(jié)果,（d）哈夫曼樹構(gòu)造結(jié)果,0 1 2 3 bit start weight （e）哈夫曼編碼結(jié)果,例8-5 設(shè)有字符集A, B, C, D，各字符在電文中出現(xiàn)的次數(shù)集為1, 3, 5, 7，設(shè)計各字符的哈夫曼編碼。 #include #include #define MaxValue 10000 #define MaxBit 4 #define MaxN 100 #include Haffman.h,void main(void) int i, j, n = 4; int weight = 1,3,5,7; HaffNod

42、e *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); /*輸出每個葉結(jié)點的哈夫曼編碼*/ for(i = 0; i n; i+) printf(Weight = %d Code = , myHa

43、ffCodei.weight); for(j = myHaffCodei.start; j n; j+) printf(%d, myHaffCodei.bitj); printf(n); ,程序運行輸出結(jié)果如下： Weight = 1 Code = 100 Weight = 3 Code = 101 Weight = 5 Code = 11 Weight = 7 Code = 0 該結(jié)果和圖8-15所示的該問題的人工設(shè)計的哈夫曼編碼方案完全吻合。,8.7 等價問題,1等價關(guān)系和等價類 若集合X上的關(guān)系R是自反的、對稱的和傳遞的，則稱關(guān)系R是集合X上的等價關(guān)系。 設(shè)關(guān)系R為定義在集合X上的二元關(guān)

44、系，若對于每一個xX，都有(x,x)R，則稱R是自反的。例如，相等關(guān)系就是自反關(guān)系。 設(shè)關(guān)系R為定義在集合X上的二元關(guān)系，若對于任意的x,yX，若當(dāng)(x,y)R時，有(y,x)R，則稱R是對稱的。例如，相等關(guān)系就是對稱關(guān)系。,等價關(guān)系的實質(zhì)是將集合中的元素分類。 若關(guān)系R是集合X上的一個等價關(guān)系，則可以按R將集合X劃分成若干互不相交的子集X1,X2,X3,，這些子集的并X1X2X3為集合X，則這些子集便稱為集合X的關(guān)于R的等價類。,設(shè)關(guān)系R為定義在集合X上的二元關(guān)系，如果對于任意的x,y,zX，若當(dāng)(x,y)R且(y,z)R時，有(x,z)R，則稱關(guān)系R是傳遞的。例如，設(shè)集合X=1,2,3，關(guān)系R=(1,2),(2,3),(1,3)，則關(guān)系R是傳遞的。另外，相等關(guān)系也是傳遞關(guān)系。,2等價類的應(yīng)用 許多應(yīng)用問題可以歸結(jié)為按給定的等價關(guān)系劃分某集合為等價類，通常稱這類問題為等價問題。 例如，要測試一個軟件是否存在問題，這個軟件所有允許的輸入數(shù)據(jù)構(gòu)成了集合，這個集合中的元素通常很多。我們把軟件所有允許的輸入數(shù)據(jù)域劃分成若干子集合，然后從每一個子集合中選取少數(shù)具有代表性的數(shù)據(jù)作為測試用例。這樣的測試用例設(shè)計方法可以有效地避免大量的冗余測試。這種方法是一種常用的軟件黑盒測試用例設(shè)計方法。,3確定等