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