《數(shù)據(jù)結(jié)構(gòu)實用教程(C語言版)》第5章樹.ppt

,數(shù)據(jù)結(jié)構(gòu)實用教程（C語言版） 中國水利水電出版社,第5章 樹,本章中主要介紹下列內(nèi)容： 樹的邏輯定義和存儲結(jié)構(gòu) 二叉樹的邏輯定義、存儲結(jié)構(gòu) 二叉樹的基本操作算法 樹和二叉樹的轉(zhuǎn)換 哈夫曼樹及其應(yīng)用,本章目錄,結(jié)束,5.1 樹,5.1.1 樹的定義 5.1.2 樹的表示方法 5.1.3 樹的基本術(shù)語 5.1.4 樹的存儲結(jié)構(gòu),返回到總目錄,5.1.1 樹的定義,樹是n（n0）個結(jié)點的有限集合。當(dāng)n=0時稱為空樹。當(dāng)n0時，是非空樹，它滿足以下兩個條件： （1）有且僅有一個稱為根的結(jié)點； （2）其余結(jié)點分為m（m0）個互不相交的非空集合T1，T2，Tm，其中每個集合本身又是一棵樹，稱為根的子樹。,返回到本節(jié)目錄,樹的二元組表示法,樹可用二元組來表示。其中，D為結(jié)點集合，R為邊的集合。一棵樹T如圖5-1所示，則它的二元組表示方法為： T=（D,R） D=A,B,C,D,E,F,G,H R=,圖5-1 樹的邏輯結(jié)構(gòu)圖,返回到本節(jié)目錄,5.1.2樹的表示方法,樹的邏輯結(jié)構(gòu)表示有樹形表示法，文氏圖表示法，凹入表示法和廣義表表示法等。 1樹形表示法 這是樹的最基本的表示，使用一棵倒置的樹表示樹結(jié)構(gòu)。圖5-1就是采用這種方法。 2文氏表示法 使用集合以及集合的包含關(guān)系描述樹結(jié)構(gòu)。圖5-2（a）就是圖5-1的樹的文氏圖表示法。 3凹入表示法 使用線段的伸縮關(guān)系描述樹的結(jié)構(gòu)。圖5-2（b）就是圖5-1的樹的凹入表示法。 4廣義表表示法 將樹的根結(jié)點寫在括號的左邊，除根結(jié)點外的其余結(jié)點寫在括號內(nèi)并用逗號間隔來描述樹的結(jié)構(gòu)。圖5-2（c）就是圖5-1的樹的廣義表表示法。,返回到本節(jié)目錄,樹的三種表示方法,(a)文氏圖表示法 (b)凹入圖表示法 (c)廣義表表示法 圖5-2 樹的其它表示方法,返回到本節(jié)目錄,5.1.3樹的基本術(shù)語,1結(jié)點 樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。 2結(jié)點的度 結(jié)點所擁有的分支數(shù)目或后繼結(jié)點個數(shù)稱為該結(jié)點的度（Degree）。例如圖5-1所示的樹中結(jié)點A的度為3，結(jié)點C的度為2，結(jié)點E的度為0。 3樹的度 樹中各結(jié)點度的最大值稱為該樹的度。例如圖5-1所示的樹的度為3。 4葉子（終端結(jié)點） 度為零的結(jié)點稱為葉子結(jié)點。例如圖5-1所示的樹中結(jié)點E、G、H、I為葉子結(jié)點。,返回到本節(jié)目錄,5.1.3樹的基本術(shù)語,5分支結(jié)點 度不為零的結(jié)點稱為分支結(jié)點。例如圖5-1所示的樹中的A、B、C、D、F都是分支結(jié)點。 6孩子結(jié)點 一個結(jié)點的后繼稱為該結(jié)點的孩子結(jié)點。例如圖5-1所示的樹中A的孩子結(jié)點為B、C、D。 7雙親結(jié)點 一個結(jié)點稱其為其后繼結(jié)點的雙親結(jié)點。例如圖5-1所示的樹中A是B、C、D的雙親結(jié)點，C是F、G的雙親。 8兄弟結(jié)點 同一雙親結(jié)點下的孩子結(jié)點互稱為兄弟結(jié)點。例如圖5-1所示的樹中B、C、D互為兄弟結(jié)點， F、G互為兄弟結(jié)點，但不同雙親的兩個同層結(jié)點不互為兄弟結(jié)點，如G和H不互為兄弟結(jié)點。,返回到本節(jié)目錄,5.1.3樹的基本術(shù)語,9堂兄弟 雙親互為兄弟的兩個結(jié)點互稱為堂兄弟。例如圖5-1所示的樹中G和H就互為堂兄弟。 10子孫結(jié)點 一個結(jié)點的所有子樹中的結(jié)點稱之為該結(jié)點的子孫結(jié)點。例如圖5-1所示的樹中A的子孫為B、C、D、E、F、G、H、I。 11祖先結(jié)點 從樹根結(jié)點到達(dá)一個結(jié)點的路徑上的所有結(jié)點稱為該結(jié)點的祖先結(jié)點。例如圖5-1所示的樹中E的祖先結(jié)點為A和B（包括其雙親結(jié)點B）。,返回到本節(jié)目錄,5.1.3樹的基本術(shù)語,12層數(shù) 樹的根結(jié)點的層數(shù)為1，其余結(jié)點的層數(shù)等于它雙親結(jié)點的層數(shù)加1。例如圖5-1所示的樹中A的層數(shù)為1，B、C、D的層數(shù)為2，E、F、G、H的層數(shù)為3，I的層數(shù)為4。 13樹的深度 樹中結(jié)點的最大層數(shù)稱為樹的深度（或高度）。例如圖5-1所示的樹中的深度為4。 14有序樹和無序樹 如果一棵樹中的結(jié)點的各子樹從左到右是有次序的，即若交換了某結(jié)點各子樹的相對位置，則構(gòu)成了不同的樹，稱這樣的樹為有序樹，反之，則為無序樹。 15森林 m（m0）棵互不相交樹的集合稱為森林。,返回到本節(jié)目錄,5.1.4 樹的存儲結(jié)構(gòu),1.雙親表示法 用一個一維數(shù)組存儲樹中的各個結(jié)點，數(shù)組元素是一個結(jié)構(gòu)體型數(shù)據(jù)，包含兩個域：data域和parent域，分別表示結(jié)點的數(shù)據(jù)值和其雙親結(jié)點在數(shù)組中的下標(biāo)。其類型定義如下： typedef struct ElemType data; /*結(jié)點的數(shù)據(jù)域，ElemType可以是任意類型*/ int parent; /*結(jié)點存儲其雙親的數(shù)組下標(biāo)值*/ ParTypeMaxSize;,返回到本節(jié)目錄,1.雙親表示法示例,圖5-1中給出的樹，可以用圖5-3來存儲表示。其中，規(guī)定數(shù)組下標(biāo)為0的位置存儲的是根結(jié)點，設(shè)根結(jié)點的parent域為-1。,圖5-3 圖5-1中樹的雙親表示法,返回到本節(jié)目錄,5.1.4 樹的存儲結(jié)構(gòu),2.孩子表示法 將每個結(jié)點的孩子結(jié)點構(gòu)成一個單鏈表，稱之為孩子鏈表。n個結(jié)點的樹有n個這樣的孩子鏈表。為了方便起見，我們將每個結(jié)點存放在一個順序表中，順序表的每個元素有兩個域：一個是存放該結(jié)點的數(shù)據(jù)值；另一個是存放該結(jié)點的第一個孩子的地址。孩子結(jié)點也有兩個域：一個域是存放該孩子結(jié)點在順序表中的位置（數(shù)組下標(biāo)），另一個域是存放下一個孩子的地址。,返回到本節(jié)目錄,2.孩子表示法舉例,圖5-4是圖5-1所示樹的孩子表示法。其中，規(guī)定表頭下標(biāo)為0的位置存放根結(jié)點。,圖5-4 圖5-1樹的孩子表示法,返回到本節(jié)目錄,5.1.4 樹的存儲結(jié)構(gòu),3.孩子兄弟法 孩子兄弟法存儲結(jié)構(gòu)是一種二叉鏈表，鏈表中每個結(jié)點包括三個域：數(shù)據(jù)值和兩個指針，其中一個指針指向該結(jié)點的最左邊第一個孩子，而另一個指針則指向該結(jié)點的下一個兄弟。每個結(jié)點的類型定義如下： typedef struct node2 ElemType data; /*數(shù)據(jù)域*/ Struct node2 *child,*brother; /*其第一個孩子和其右邊兄弟的地址*/ CBNodeType; /*孩子兄弟結(jié)點類型*/,返回到本節(jié)目錄,圖5-5是圖5-1所示樹的孩子兄弟表示法的存儲結(jié)構(gòu)。其中T指向樹的根結(jié)點。,圖5-5 圖5-1樹的孩子兄弟表示法,返回到本節(jié)目錄,5.2 二叉樹,5.2.1 二叉樹的定義 5.2.2 二叉樹的性質(zhì) 5.2.3 二叉樹的存儲結(jié)構(gòu) 5.2.4 二叉樹的基本運算,返回到總目錄,5.2.1 二叉樹的定義,1二叉樹的定義 二叉樹（Binary Tree）是有n（n0）個結(jié)點的有限集合。 （1）該集合或者為空（n=0）； （2）或者由一個根結(jié)點及兩個不相交的分別稱為左子樹和右子樹組成的非空樹； （3）左子樹和右子樹同樣又都是二叉樹。,返回到本節(jié)目錄,5.2.1 二叉樹的定義,2二叉樹的形態(tài) 二叉樹歸納起來有五種形態(tài)，如圖5-7所示。,(a)空二叉樹 (b)只有一個根結(jié)點 (c)右子樹為空 (d)左子樹為空 (e)左、右子樹非空 圖5-7 二叉樹的五種形態(tài),返回到本節(jié)目錄,5.2.2 二叉樹的性質(zhì),性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點（i1）。 性質(zhì)2：深度為k的二叉樹中至多有2k -1個結(jié)點。 性質(zhì)3：對任意一棵二叉樹T，如果其葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則有n0=n2+1。,返回到本節(jié)目錄,5.2.2 二叉樹的性質(zhì),下面介紹兩種特殊的二叉樹。 （1）滿二叉樹 一棵深度為k，且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。圖5-9（a）所示是一棵深度為4的滿二叉樹，其特點是每一層上的結(jié)點都具有最大的結(jié)點數(shù)。 （2）完全二叉樹 在一棵二叉樹中，除最后一層外，若其它層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)的若干個結(jié)點，則稱此二叉樹為完全二叉樹。據(jù)此得知滿二叉樹是完全二叉樹的特例。圖5-9（b）是一棵深度為4 的完全二叉樹。,返回到本節(jié)目錄,滿二叉樹和完全二叉樹示例,(a)一棵滿二叉樹 (b)一棵完全二叉樹 圖5-9 一棵滿二叉樹和一棵完全二叉樹示意圖,返回到本節(jié)目錄,5.2.2 二叉樹的性質(zhì),性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為。 性質(zhì)5：如果一棵有n個結(jié)點的完全二叉樹（其深度為）的結(jié)點按層次（從第1層到第層，每層從左到右。則對任一結(jié)點i(1in)有： （1）如果i=1，結(jié)點i是根結(jié)點，無雙親；如果i1，則其雙親結(jié)點是結(jié)點i/2。 （2）如果2in，則結(jié)點i無左孩子，該結(jié)點為葉子結(jié)點；否則其左孩子是結(jié)點2i。 （3）如果2i+1n，則結(jié)點i無右孩子，該結(jié)點為葉子結(jié)點；否則其左孩子是結(jié)點2i+1。,返回到本節(jié)目錄,5.2.3 二叉樹的存儲結(jié)構(gòu),1順序存儲結(jié)構(gòu) 順序存儲一棵二叉樹時，先對該二叉樹中的各結(jié)點進行編號，然后以各結(jié)點的編號為下標(biāo)，把各結(jié)點的值存到一維數(shù)組中。 其編號過程為：首先，把樹的根結(jié)點的編號定為1，然后按照層次從上到下，從左到右的順序?qū)γ恳唤Y(jié)點進行編號。當(dāng)一個結(jié)點的雙親結(jié)點的編號為i時，若它是左孩子，則編號為2i，若它是右孩子，則編號為2i+1。如圖5-10(a)所示的二叉樹（各結(jié)點上方的數(shù)字就是該結(jié)點的編號）對應(yīng)的順序存儲結(jié)構(gòu)為圖5-10(b)所示。,返回到本節(jié)目錄,順序存儲的二叉樹示例,一棵帶編號的二叉樹,(b)對應(yīng)的順序存儲結(jié)構(gòu) 圖5-10 一棵二叉樹及其順序存儲結(jié)構(gòu),返回到本節(jié)目錄,5.2.3 二叉樹的存儲結(jié)構(gòu),2鏈?zhǔn)酱鎯Y(jié)構(gòu) 對于一般的二叉樹，通常采用二叉鏈表示。鏈表中的每個結(jié)點包含兩個指針，分別指向該結(jié)點的左孩子和右孩子。在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，結(jié)點的類型定義如下： Typedef struct tnode ElemType data; /*數(shù)據(jù)域*/ struct tnode *lchild,*rchild; /*左、右孩子指針域*/ BTNode; /*二叉樹結(jié)點存儲類型*/ 其中，data域中存入結(jié)點的數(shù)據(jù)值，lchild和rchild分別表示左指針域和右指針域，分別存儲其左、右孩子結(jié)點的地址。,返回到本節(jié)目錄,圖5-11 二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu),如圖5-10的二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)如圖5-11所示。,返回到本節(jié)目錄,5.2.4 二叉樹的基本運算,二叉樹的常用運算有以下幾種： （1）bt=CreateBTree(str):根據(jù)二叉樹的廣義表表示法str建立二叉樹bt。 （2）BTHeight(bt)：求一棵二叉樹bt的高度。 （3）NodeCount(bt)：求一棵二叉樹bt的結(jié)點個數(shù)。 （4）LeafCount(bt): 求一棵二叉樹bt的葉子結(jié)點個數(shù)。 （5）DispBTree(bt):以廣義表表示法輸出一棵二叉樹bt。,返回到本節(jié)目錄,5.3 二叉樹的建立和遍歷,5.3.1 二叉樹的建立和輸出 5.3.2 二叉樹的遍歷 5.3.3 由遍歷序列恢復(fù)二叉樹,返回到總目錄,5.3.1 二叉樹的建立和輸出,1二叉樹的建立 二叉樹的建立是二叉樹的重要運算之一，我們介紹的方法是：用字符ch掃描用廣義表表示法輸入的二叉樹的字符串str。分以下幾種情況： （1）若ch=(，則將前面剛創(chuàng)建的結(jié)點作為雙親結(jié)點進棧，并置k=1，表示其后創(chuàng)建的結(jié)點將作為這個結(jié)點的左孩子結(jié)點。 （2）若ch=)，表示棧中結(jié)點的左右孩子結(jié)點處理完畢，退棧。 （3）若ch=,，表示要創(chuàng)建一個結(jié)點，并根據(jù)k值建立它與棧中結(jié)點之間的聯(lián)系，當(dāng)k=1時，表示這個結(jié)點作為棧中結(jié)點的左孩子結(jié)點，當(dāng)k=2時，表示這個結(jié)點作為棧中結(jié)點的右孩子結(jié)點。如此循環(huán)直到str處理完畢。算法中使用一個棧st保存雙親結(jié)點，top為其棧頂指針，k指定其后處理的結(jié)點是雙親結(jié)點（保存在棧中）的左孩子結(jié)點（k=1）還是右孩子結(jié)點（k=2）。,返回到本節(jié)目錄,1二叉樹的建立,（1）二叉樹的存儲結(jié)構(gòu)及相關(guān)類型的定義如下： #define NULL 0 /*定義空指針為0*/ #define MaxSize 100 /*樹的最大元素個數(shù)為100*/ typedef char ElemType; /*重定義char為ElemType類型 */ typedef struct tnode ElemType data; /*數(shù)據(jù)域*/ struct tnode *lchild,*rchild; /*左、右孩子指針*/ BTNode; /*二叉樹結(jié)點類型*/,返回到本節(jié)目錄,1二叉樹的建立算法,（2）二叉樹的建立對應(yīng)的算法如算法5.1所示。 算法5.1 BTNode *CreateBTree(char *str) BTNode *bt,*stMaxSize,*p=NULL; int top=-1,k,j=0; char ch; bt=NULL; ch=strj; while(ch!=0) switch (ch) case (:top+; /*若是左括號，則先入棧*/ sttop=p; k=1; break; case ):top-;break; /*若是右括號，則出棧*/,返回到本節(jié)目錄,1二叉樹的建立算法,case ,:k=2;break; /*若是逗號，則有右子樹*/ default : /*若是其它字符，則生成新的二叉樹結(jié)點*/ p=(BTNode *)malloc(sizeof(BTNode); p-data=ch; p-lchild=p-rchild=NULL; if(bt=NULL) bt=p; else switch(k) case 1:sttop-lchild=p;break; case 2:sttop-rchild=p;break; j+; ch=strj; return(bt); ,返回到本節(jié)目錄,5.3.1 二叉樹的建立和輸出,2用廣義表表示法輸出二叉樹 其過程是：對于非空二叉樹bt，先輸出其元素值，當(dāng)存在左孩子結(jié)點或右孩子結(jié)點時，輸出一個(符號，然后遞歸處理左子樹，輸出一個,符號，遞歸處理右子樹，最后輸出一個)。對應(yīng)的算法如算法5.2。,返回到本節(jié)目錄,2用廣義表表示法輸出二叉樹,算法5.2 void DispBTree(BTNode *bt) if (bt!=NULL) printf(“%c“,bt-data); if(bt-lchild!=NULL) printf(“(“); DispBTree(bt-lchild); if(bt-rchild!=NULL) printf(“,“); DispBTree(bt-rchild); printf(“)“); ,返回到本節(jié)目錄,5.3.2 二叉樹的遍歷,一棵二叉樹由根結(jié)點（D）、根結(jié)點的左子樹（L）和根結(jié)點的右子樹（R）三部分組成。 一般限定先左后右的次序，那么只有三種遍歷：DLR（根左右）、LDR（左根右）、LRD（左右根）。我們將這三種遍歷方法稱作前（根）序遍歷，中（根）遍歷和后（根）序遍歷。 也可以對二叉樹的每個層次的各結(jié)點按從左至右進行遍歷（按層次遍歷），下面我們分別介紹這幾種遍歷方法。,返回到本節(jié)目錄,1.前（根）序遍歷二叉樹（DLR）,有些教材稱為先（根）序遍歷。若二叉樹為空，遍歷結(jié)束。否則依次執(zhí)行以下操作： （1）訪問根結(jié)點； （2）前序遍歷根結(jié)點的左子樹； （3）前序遍歷根結(jié)點的右子樹。 前序遍歷的遞歸算法如算法5.3所示。 以圖5-10為例，進行前序遍歷的輸出序列為：ABDCEGF。,返回到本節(jié)目錄,前序遍歷的遞歸算法,算法5.3 void PreOrder(BTNode *bt) /* 前序遍歷二叉樹BT*/ if(bt=NULL) return; /* 遞歸調(diào)用的結(jié)束條件*/ else printf(“%c“,bt-data); /* 輸出結(jié)點的數(shù)據(jù)域*/ PreOrder(bt-lchild); /*前序遞歸遍歷左子樹*/ PreOrder(bt-rchild); /* 前序遞歸遍歷右子樹*/ ,返回到本節(jié)目錄,2.中（根）序遍歷二叉樹（LDR）,若二叉樹為空，遍歷結(jié)束。否則依次執(zhí)行以下操作： （1）中序遍歷根結(jié)點的左子樹； （2）訪問根結(jié)點； （3）中序遍歷根結(jié)點的右子樹。 中序遍歷的遞歸算法如算法5.4所示。 以圖5-10為例，進行中序遍歷的輸出序列為：DBAGECF。,返回到本節(jié)目錄,中序遍歷的遞歸算法,算法5.4 void InOrder(BTNode *bt) /*中序遍歷二叉樹BT*/ if(bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/ else InOrder(bt-lchild); /* 中序遞歸遍歷左子樹*/ printf(“%c“,bt-data); /*輸出結(jié)點的數(shù)據(jù)域*/ InOrder(bt-rchild); /* 中序遞歸遍歷右子樹*/ ,返回到本節(jié)目錄,3后（根）序遍歷二叉樹（LRD）,若二叉樹為空，遍歷結(jié)束。否則依次執(zhí)行以下操作： （1）后序遍歷根結(jié)點的左子樹； （2）后序遍歷根結(jié)點的右子樹。 （3）訪問根結(jié)點； 后序遍歷的遞歸算法如算法5.5所示。 以圖5-10為例，進行后序遍歷的輸出序列為：DBGEFCA。,返回到本節(jié)目錄,后序遍歷的遞歸算法,算法5.5 void PostOrder(BTNode *bt) /*后序遍歷二叉樹BT*/ if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/ else PostOrder(bt-lchild); /*后序遞歸遍歷左子樹*/ PostOrder(bt-rchild); /*后序遞歸遍歷右子樹*/ printf(“%c“,bt-data); /*輸出結(jié)點的數(shù)據(jù)域*/ ,返回到本節(jié)目錄,4層次遍歷二叉樹,在進行層次遍歷時，對某一層的結(jié)點訪問完后，再按照它們的訪問次序?qū)Ω鱾€結(jié)點的左、右孩子順序訪問，這樣一層一層進行，先訪問的結(jié)點其左、右孩子也要先訪問。這樣的操作與隊列的原則比較符合，所以可以用一個環(huán)形隊列qu來實現(xiàn)。 層次遍歷過程是先將根結(jié)點進隊，在隊不空時循環(huán)；從隊列中出列一個結(jié)點*p，訪問它；若它有左孩子結(jié)點，將左孩子結(jié)點進隊；若它有右孩子結(jié)點，將右孩子結(jié)點進隊，直到隊空為止。算法如算法5.6所示。 以圖5-10為例，進行按層次遍歷的輸出序列為：ABCDEFG。,返回到本節(jié)目錄,層次遍歷的算法,算法5.6 void LevelOrder(BTNode *bt) BTNode *p; BTNode *quMaxSize; /*定義循環(huán)隊列，存放結(jié)點指針*/ int front,rear; /*定義隊頭隊尾指針*/ front=rear=-1; /*空隊*/ rear+; qurear=bt; /*根結(jié)點指針進入隊列*/,返回到本節(jié)目錄,層次遍歷的算法,while(front!=rear) /*隊列不空時*/ front=(front+1)%MaxSize; p=qufront; /*隊頭出隊列*/ printf(“%c“,p-data); if(p-lchild!=NULL) /*有左孩子時將其進隊*/ rear=(rear+1)%MaxSize; qurear=p-lchild; if(p-rchild!=NULL) /*有右孩子時將其進隊*/ rear=(rear+1)%MaxSize; qurear=p-rchild; ,返回到本節(jié)目錄,5.3.3 由遍歷序列恢復(fù)二叉樹,1由前序和中序恢復(fù)二叉樹 （1）根據(jù)前序序列確定樹的根（第一個結(jié)點），根據(jù)中序序列確定左子樹和右子樹； （2）分別找出左子樹和右子樹的根結(jié)點，并把左、右子樹的根結(jié)點聯(lián)到雙親結(jié)點上去； （3）再對左子樹和右子樹按此法找根結(jié)點和左、右子樹，直到子樹只剩下1個結(jié)點或2個結(jié)點或空為止。,返回到本節(jié)目錄,5.3.3 由遍歷序列恢復(fù)二叉樹,2由中序和后序恢復(fù)二叉樹 由二叉樹的后序序列和中序序列也可唯一地確定一棵二叉樹。其方法為： （1）根據(jù)后序序列找出根結(jié)點（最后一個），根據(jù)中序序列確定左、右子樹； （2）分別找出左子樹和右子樹的根結(jié)點，并把左、右子樹的根結(jié)點聯(lián)到雙親（parent）結(jié)點上去； （3）再對左子樹和右子樹按此法找根結(jié)點和左、右子樹，直到子樹只剩下1個結(jié)點或2個結(jié)點或空為止。,返回到本節(jié)目錄,5.4 樹、森林與二叉樹的轉(zhuǎn)換,5.4.1 樹、森林轉(zhuǎn)換為二叉樹 5.4.2 二叉樹還原為樹、森林,返回到總目錄,5.4.1 樹、森林轉(zhuǎn)換為二叉樹,1樹轉(zhuǎn)換成二叉樹 將一棵樹轉(zhuǎn)換成二叉樹的過程如下： （1）加線：樹中所有相鄰兄弟之間加一條連線。 （2）抹線：對樹中的每個結(jié)點，只保留它與第一個孩子結(jié)點之間的連線，刪除它與其它孩子結(jié)點之間的連線。 （3）旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將整棵樹順時針旋轉(zhuǎn)45，使之成為二叉樹。,返回到本節(jié)目錄,【例5.3】將圖5-15（a）所示的樹轉(zhuǎn)換成二叉樹。,轉(zhuǎn)換過程如圖5-15(b)、(c)、(d)所示。,（a）原始樹 （b）相鄰兄弟之間加連線（虛線）,（c）刪除與雙親結(jié)點的連線 (d)轉(zhuǎn)換之后的二叉樹 圖5-15 一棵樹轉(zhuǎn)換成二叉樹的過程,返回到本節(jié)目錄,2森林轉(zhuǎn)換為二叉樹,將森林轉(zhuǎn)換為二叉樹的過程如下： （1）將森林中的每一棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。 （2）第一棵二叉樹保持不動，從第二棵二叉樹開始，依次把后一棵二叉樹作為前一棵二叉樹根結(jié)點的右子樹，直到把最后一棵二叉樹作為其前一棵二叉樹的右子樹為止。此時所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。,返回到本節(jié)目錄,【例5.4】將圖5-16（a）所示的森林轉(zhuǎn)換成二叉樹。,解：轉(zhuǎn)換的過程如圖5-16（b）5-16（e）所示。,（a）森林 （b）相鄰兄弟加連線（虛線）,（c）刪除與雙親結(jié)點的連線 （d）每棵樹轉(zhuǎn)換成二叉樹,返回到本節(jié)目錄,【例5.4】,（e）所有的二叉樹連接成一棵二叉樹 圖5-16 森林轉(zhuǎn)換成二叉樹的過程,返回到本節(jié)目錄,5.4.2 二叉樹還原為樹、森林,1二叉樹還原為樹 二叉樹還原為樹的過程如下： （1）加線：如果某結(jié)點的左孩子有右子樹，在該結(jié)點和其左孩子的右子樹的右分支上各結(jié)點間加線。 （2）抹線：抹掉各結(jié)點的右子樹的右分支取上的連線。 （3）旋轉(zhuǎn)整理得到樹。,返回到本節(jié)目錄,5.4.2 二叉樹還原為樹、森林,2二叉樹還原為森林 二叉樹還原為森林的過程如下： （1）連線：若某結(jié)點是其雙親的左孩子，則把該結(jié)點的右孩子、右孩子的右孩子、都與該結(jié)點的雙親結(jié)點用連線連起來。 （2）抹線：刪除原二叉樹中原來雙親結(jié)點與右孩子結(jié)點的連線。 （3）整理由（1）、（2）兩步所得到的樹或森林，使之結(jié)構(gòu)層次分明。,返回到本節(jié)目錄,5.5 哈夫曼樹,5.5.1相關(guān)概念和哈夫曼樹的定義 5.5.2 哈夫曼樹的構(gòu)造方法 5.5.3 哈夫曼編碼,返回到總目錄,5.5.1相關(guān)概念和哈夫曼樹的定義,1路徑 樹中一個結(jié)點與另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑。樹中不是每對結(jié)點之間都有路徑，如兄弟結(jié)點之間就無路徑，而從根結(jié)點到樹中任一結(jié)點都存在一條路徑。 2路徑長度 樹中路徑上的分支數(shù)目。 3樹的路徑長度 根結(jié)點到樹中每個結(jié)點的路徑長度之和。 4結(jié)點的權(quán)值 所謂權(quán)值是人們根據(jù)需要為每個葉子結(jié)點賦予的一個數(shù)值。,返回到本節(jié)目錄,5結(jié)點的帶權(quán)路徑長度 是指從樹根到該結(jié)點之間的路徑長度與結(jié)點的權(quán)值的乘積。 6樹的帶權(quán)路徑長度 樹中所有葉子結(jié)點的權(quán)值乘以該結(jié)點的路徑長度之和。用公式可以表示為： 其中，wk為第k個葉子結(jié)點的權(quán)值， lk 是從根結(jié)點到第k個葉子結(jié)點的路徑長度。 7哈夫曼樹 哈夫曼樹又稱為最優(yōu)二叉樹。它是n個帶權(quán)值的葉子結(jié)點所構(gòu)成的所有二叉樹中帶權(quán)路徑長度WPL最小的二叉樹。,返回到本節(jié)目錄,求不同二叉樹的WPL,如圖5-19（a）、（b）、（c）所示的三棵二叉樹，它們的帶權(quán)路徑長度分別為： （a）WPL=22+32+42+62=30 （b）WPL=23+33+42+61=29 （c）WPL=43+63+32+21=38,（a） （b） （c） 圖5-19 相同葉子結(jié)點所構(gòu)成的不同帶權(quán)路徑長度的二叉樹,返回到本節(jié)目錄,5.5.2 哈夫曼樹的構(gòu)造方法,下面介紹哈夫曼樹的構(gòu)造方法，步驟如下： （1）將給定的n個權(quán)值w1,w2,.,wn作為n個根結(jié)點的權(quán)值構(gòu)造一個具有n棵二叉樹的森林T1,T2,.,Tn，其中每棵二叉樹只有一個根結(jié)點； （2）在森林中選取兩棵樹根結(jié)點的權(quán)值最小的二叉樹作為左右子樹構(gòu)造一棵新二叉樹，新二叉樹的根結(jié)點的權(quán)值為原來兩棵樹根結(jié)點的權(quán)值之和； （3）在森林中，將上面選擇的這兩棵根結(jié)點的權(quán)值最小的二叉樹從森林中刪除，并將最新構(gòu)造的二叉樹加入到森林中； （4）重復(fù)上面（2）和（3），直到森林中只有一棵二叉樹為止。這棵二叉樹就是哈夫曼樹。,返回到本節(jié)目錄,【例5.7】假設(shè)有一組權(quán)值2,3,7,8,12,9,6,19，下面我們將利用這組權(quán)值演示構(gòu)造哈夫曼樹的過程。 解：第一步：以這8個權(quán)值作為根結(jié)點的權(quán)值構(gòu)造具有8棵樹的森林。,第二步：從中選擇兩個根的權(quán)值最小的樹2、3作為左右子樹構(gòu)造一棵新樹，并將這兩棵樹從森林中刪除，并將新樹5添加進去。,返回到本節(jié)目錄,第三步：重復(fù)第二步過程，直到森林中只有一棵樹為止 選擇5、6，將11放回。,選擇7、8，將15放回。,返回到本節(jié)目錄,選擇9、11，將20放回,選擇12、15，將27放回。,返回到本節(jié)目錄,選擇19、20，將39放回。,選擇27、39，最后森林中只有一棵樹，結(jié)束操作，這棵樹就是哈夫曼樹。,返回到本節(jié)目錄,為了實現(xiàn)構(gòu)造哈夫曼樹的算法，設(shè)計哈夫曼樹中每個結(jié)點類型如下： typedef struct char data; /*結(jié)點值*/ int weight; /*權(quán)值*/ int parent; /*雙親結(jié)點下標(biāo)*/ int lchild; /*左孩子結(jié)點下標(biāo)*/ int rchild; /*右孩子結(jié)點下標(biāo)*/ HTCode; /*哈夫曼樹結(jié)點類型*/,返回到本節(jié)目錄,用ht數(shù)組存放哈夫曼樹，對于具有n個葉子結(jié)點的哈夫曼樹，總共有2n-1個結(jié)點。其算法思路是：n個葉子結(jié)點只有data和weight域值，先將所有2n-1個結(jié)點的parent、lchild和rchild域置為-1。處理每個非葉子結(jié)點hti（存放在htnht2n-2中）：從ht0hti-2中找出根結(jié)點（即其parent域為-1）最小的兩個結(jié)點htlnode和htrnode，將它們作為hti的左右子樹，htlnode和htrnode雙親結(jié)點置為hti，并且hti.weight= htlnode.weight+htrnode.weight。如此這樣直到所有的n-1個非葉子結(jié)點處理完畢。構(gòu)造哈夫曼樹的算法如算法5.7。,返回到本節(jié)目錄,算法5.7 void CreateHT(HTCode ht,int n) int i,j,k,lnode,rnode; int min1,min2; for(i=0;i2*n-1;i+) /*將雙親、左、右孩子域置初值-1*/ hti.parent=hti.lchild=hti.rchild=-1; for(i=n;i2*n-1;i+) min1=min2=32767; /*兩個最小值置初值為系統(tǒng)最大值*/ lnode=rnode=-1;,返回到本節(jié)目錄,for(k=0;khtk.weight) min1=htk.weight; /*找出最小的權(quán)值*/ lnode=k; /*最小權(quán)值的結(jié)點下標(biāo)值*/ for(k=0;khtk.weight /*次最小權(quán)值的結(jié)點下標(biāo)值*/ ,返回到本節(jié)目錄,htlnode.parent=i;htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.lchild=lnode;hti.rchild=rnode; ,返回到本節(jié)目錄,5.5.3 哈夫曼編碼,1什么是哈夫編碼？ 在進行快速遠(yuǎn)距離的通信時，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進制字符0，1組成的二進制代碼，稱之為編碼。 如果在編碼時考慮字符出現(xiàn)的頻率，讓出現(xiàn)頻率高的字符采用盡可能短的編碼，出現(xiàn)頻率低的字符采用稍長的編碼，構(gòu)造一種不等長編碼，則電文的代碼就可能更短。哈夫曼編碼是一種用于構(gòu)造使電文的編碼總長最短的編碼方案。,返回到本節(jié)目錄,5.5.3 哈夫曼編碼,2生成哈夫曼編碼的方法 要設(shè)計長短不同的編碼，首先要做到不同字符的編碼不會混淆，即任一個字符的編碼都不是另一個字符的編碼的前綴（即不是另一個字符編碼的開頭一部分），滿足這個條件的編碼叫做前綴編碼。即前綴編碼是指所編碼的字符可以通過前綴唯一地正確識別并譯出。利用哈夫曼樹就可以方便的設(shè)計。,返回到本節(jié)目錄,2生成哈夫曼編碼的方法,（1）構(gòu)造哈夫曼樹 設(shè)需要編碼的字符集合為d1，d2，dn，它們在電文中出現(xiàn)的次數(shù)集合為w1，w2，wn，以d1，d2，dn作為葉子結(jié)點，w1，w2，wn作為它們的權(quán)值，構(gòu)造一棵哈夫曼樹。 （2）在哈夫曼樹上求葉結(jié)點的編碼。 規(guī)定哈夫曼樹中的左分支代表0，右分支代表1，則從根結(jié)點到每個葉子結(jié)點所經(jīng)過的路徑分支組成的0和1的序列便為該結(jié)點對應(yīng)字符的編碼。,返回到本節(jié)目錄,【例5.8】設(shè)有A，B，C，D，E，F(xiàn) 6個字符，其出現(xiàn)的頻度分別為0.06、0.02、0.04、0.03、0.07、0.12，試設(shè)計它們的哈夫曼編碼。 解：將所有頻度全部乘以100，得到各字符的權(quán)值6，2，4，3，7，12，根據(jù)這組權(quán)值構(gòu)造的哈夫曼樹如圖5-21所示。并設(shè)哈夫曼樹的每個左分支為0，右分支為1進行編碼.,返回到本節(jié)目錄,則得到各個字符的哈夫曼編碼為： A：00 B：1010 C：100 D：1011 E：01 F：11,圖5-21 哈夫曼編碼樹,返回到本節(jié)目錄,3.哈夫曼編碼的算法實現(xiàn),（1）設(shè)計哈夫曼編碼的數(shù)據(jù)類型如下： typedef struct char cdN; /*存放當(dāng)前結(jié)點的哈夫曼編碼*/ int start; /*start指向cd數(shù)組中的哈夫曼編碼最開始字符*/ HCode; /*哈夫曼編碼存放類型*/,返回到本節(jié)目錄,3.哈夫曼編碼的算法實現(xiàn),（2）生成哈夫曼編碼的算法 由于哈夫曼樹中的每個葉子結(jié)點的哈夫曼編碼長度不同，為此采用HCode類型變量的cdstartcdn存放當(dāng)前結(jié)點的哈夫曼編碼。只需對葉子結(jié)點求哈夫曼編碼。對于當(dāng)前葉子結(jié)點hti，先將對應(yīng)的哈夫曼編碼和hcdi的start域置初值n，找其雙親結(jié)點htf，若當(dāng)前結(jié)點是雙親結(jié)點的左孩子，則在hcdi的cd數(shù)組中添加1，將start域減1