數(shù)據(jù)結構

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

終端結點

分支結點：度不為0的結點孩子結點：樹中一個結點的子樹的根結點雙親結點：若樹中某結點有孩子結點，則這個結點就稱作它的孩子結點的雙親結點兄弟結點：具有相同的雙親結點的結點樹的度：樹中所有結點的度的最大值結點的層次：從根結點到樹中某結點所經路徑上的分支數(shù)樹的深度：樹中所有結點的層次的最大值無序樹：樹中任意一個結點的各孩子結點之間的次序構成無關緊要的樹有序樹：樹中任意一個結點的各孩子結點有嚴格排列次序的樹森林：m（m≥0）棵樹的集合2.樹的表示方法(1)直觀表示法(2)形式化表示法(3)凹入表示法T=（D，R）DF=D1∪D2∪…∪Dm

（1≤i,j≤m,Di∩Dj=￠）R={<Root,ri>,i=1,2,…,n-1}ABCDEFGHIJKL3.樹的抽象數(shù)據(jù)類型數(shù)據(jù)集合:

樹的結點集合，每個結點由數(shù)據(jù)元素和構造數(shù)據(jù)元素之間關系的指針組成。操作集合:

（1）創(chuàng)建MakeTree(T)

（2）撤消DestroyTree(T)

（3）雙親結點Parent(T,curr)

（4）左孩子結點LeftChild(T,curr)

（5）右兄弟結點RightSibling(T,curr)

（6）遍歷樹Traverse(T,Visit())4.樹的存儲結構

樹的結點之間的邏輯關系主要有雙親-孩子關系，兄弟關系。因此，從結點之間的邏輯關系分，樹的存儲結構主要有：雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法四種組合。指針有常規(guī)指針和仿真指針4H2G1F1E1D0C0B-1AI4dataparent012345678ABDEFHICG(1)雙親表示法(a)一棵樹（b)仿真指針的雙親表示法存儲結構樹及其使用仿真指針的雙親表示法(2)孩子表示法常規(guī)指針的孩子表示法rootBA∧CDEFGHI∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧雙親孩子表示法存儲結構(3)雙親孩子表示法∧4H2G1F1E1D0C0B-1AI4dataparenthead012345678∧∧∧∧childnext∧87∧∧∧123456(4)孩子兄弟表示法常規(guī)指針的孩子兄弟表示法root∧BCDEFGHI∧∧∧∧∧∧∧∧∧A8.2二叉樹一、二叉樹：是n(n≥0)個結點的有限集合。n=0的樹稱為空二叉樹；n>0的二叉樹由一個根結點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。邏輯結構：一對二（1:2）基本特征:①每個結點最多只有兩棵子樹（不存在度大于2的結點）；②左子樹和右子樹次序不能顛倒。所以下面是兩棵不同的樹

注意：二叉樹不是有序樹1.二叉樹的定義BACEDFGBACEDFG二、滿二叉樹：在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子結點都在同一層上，這樣的二叉樹稱為滿二叉樹。三、完全二叉樹：如果一棵深度為k，有n個結點的二叉樹中各結點能夠與深度為k的順序編號的滿二叉樹從0到n-1標號的結點相對應的二叉樹稱為完全二叉樹。如下圖所示BACEDFGHIJKLMNO(a)滿二叉樹BACEDFGHIJ(b)完全二叉樹問題:一個高度為h的完全二叉樹最多有多少個結點?最少有多少個結點?數(shù)據(jù)集合：二叉樹的結點集合，每個結點由數(shù)據(jù)元素和構造數(shù)據(jù)元素之間關系的指針組成。操作集合：（1）創(chuàng)建MakeTree(T)（2）撤消DestroyTree(T)（3）左插入結點InsertLeftNode(curr,x)（4）右插入結點InsertRightNode(curr,x)（5）左刪除子樹DeleteLeftTree(curr)（6）右刪除子樹DeleteRightTree(curr)（7）遍歷二叉樹Traverse(T,Visit())2.二叉樹抽象數(shù)據(jù)類型3.二叉樹的性質性質1在一棵非空二叉樹的第i層上至多有2i個結點（i≥0）。性質2深度為k的二叉樹至多有2k+1-1個結點。說明：深度k=-1，表示沒有一個結點；深度k=0，表示只有一個根結點。性質3

對于一棵非空的二叉樹，如果葉結點個數(shù)為n0，度為2的結點數(shù)為n2，則有n0=n2+1。證明：設n為二叉樹的結點總數(shù)，n1為二叉樹中度為1的結點個數(shù)，則有：n=n0+n1+n2

另外，在二叉樹中，除根結點外的所有結點都有一個惟一的進入分支，設M為二叉樹中所有結點的進入分支數(shù)，則有： M=n-1

從二叉樹的結構可知，二叉樹的所有進入分支是由度為1的結點和度為2的結點發(fā)出的，每個度為1的結點發(fā)出一個分支，每個度為2的結點發(fā)出兩個分支，所以又有：

M=n1+2×n2

因此有：n-1=n1+2×n2

再把n=n0+n1+n2代入，則可以得到n0=n2+1。性質4具有n個結點的完全二叉樹的深度k為大于或等于lb(n+1)-1的最小整數(shù)。證明：由性質2和完全二叉樹的定義可知，對于有n個結點的深度為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ù)?？珊唽憺閗=

lb(n+1)-1

。例如，

2.0

=2，

2.1

=3。若結點個數(shù)n=0，則有深度k=-1，滿足k=

lb(0+1)-1

=-1；若結點個數(shù)n=1，則有深度k=0，滿足k=

lb(1+1)-1

=0；若結點個數(shù)n=2，則有深度k=1，滿足k=

lb(2+1)-1

=

0.xx

=1；若結點個數(shù)n=3，則有深度k=1，滿足k=

lb(3+1)-1

=1。

性質5對于一棵有n個結點的完全二叉樹，按照從上至下和從左至右的順序對所有結點從0開始順序編號,則對于序號為i的結點(0≤i<n),有：

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

(2)如果2i+1＜n，其左孩子是結點2i+1；如果2i+1≥n，則結點i無左孩子。

(3)如果2i＋2＜n，其右孩子是結點2i＋2；如果2i＋2≥n，則結點i無右孩子。8.3二叉樹的設計和實現(xiàn)8.3.1二叉樹的存儲結構二叉樹的存儲結構主要有三種：順序存儲結構、鏈式存儲結構和仿真指針存儲結構。1.二叉樹的順序存儲結構完全二叉樹的結點可按從上至下和從左至右的次序存儲在一維數(shù)組中，其結點之間的關系可由公式計算得到，這就是二叉樹的順序存儲結構。下面兩棵樹在數(shù)組中的存儲結構分別為：BACEDFGHIJKLMNOABCDONMLKJIHGFE12043576118109121314

對于一般的非完全二叉樹顯然不能直接使用二叉樹的順序存儲結構。可以首先在非完全二叉樹中增添一些并不存在的空結點使之變成完全二叉樹的形態(tài)，然后再用順序存儲結構存儲。

BACEDFGHIJABCDJIHGFE1204357689BACDEGFBACDEGF(a)一般二叉樹(b)完全二叉樹形態(tài)(c)在數(shù)組中的存儲形式ABC∧G∧∧F∧∧∧ED1204357611810912數(shù)組下標2.二叉樹的鏈式存儲結構

二叉樹的鏈式存儲結構是用指針建立二叉樹中結點之間的關系。二叉樹最常用的的鏈式存儲結構是二叉鏈。二叉鏈存儲結構的每個結點包含三個域，分別是數(shù)據(jù)域data、左孩子指針域leftChild和右孩子指針域rightChild。二叉鏈存儲結構中每個結點的圖示結構為：

rightChilddataleftChild

二叉鏈存儲結構的二叉樹也有不帶頭結點和帶頭結點兩種。帶頭結點的二叉鏈存儲結構的二叉樹見下圖(b)，不帶頭結點的二叉鏈存儲結構的二叉樹如下圖(a)所示。圖8-10二叉鏈存儲結構的二叉樹root∧A∧BC∧D∧E∧F∧G∧∧∧rootA∧BC∧D∧E∧F∧G∧∧∧(a)不帶頭結點的二叉樹(b)帶頭結點的二叉樹3.二叉樹的仿真指針二叉樹的仿真指針存儲結構是用數(shù)組存儲二叉樹中的結點，數(shù)組中每個結點除數(shù)據(jù)元素域外，再增加仿真指針域用于仿真常規(guī)指針建立二叉樹中結點之間的關系。二叉樹的仿真二叉鏈存儲結構8.3.2二叉鏈結構的二叉樹設計typedefstructNode{DataTypedata; structNode*leftChild; structNode*rightChild;}BiTreeNode;//初始化voidInitiate(BiTreeNode**root){*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));(*root)->leftChild=NULL;(*root)->rightChild=NULL;}//左子樹插入結點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; }//刪除左子樹BiTreeNode*DeleteLeftTree(BiTreeNode*curr){if(curr==NULL||curr->leftChild==NULL)returnNULL;

Destroy(&curr->leftChild);curr->leftChild=NULL;returncurr;}例8-1編寫一個建立如圖8-10（b）所示的帶頭結點的二叉鏈存儲結構二叉樹的程序。#include<stdlib.h>#include<stdio.h>typedefcharDataType;#include"Bitree.h“Voidmain(void){BiTreeNode*root,*p,*pp;

Initiate(&root);p=InsertLeftNode(root,'A');p=InsertLeftNode(p,'B');p=InsertLeftNode(p,'D');p=InsertRightNode(p,'G');p=InsertRightNode(root->leftChild,'C');InsertLeftNode(p,'E');InsertRightNode(pp,'F');}8.4二叉樹遍歷1.二叉樹遍歷的基本方法

從二叉樹的定義知，一棵二叉樹由三部分組成：根結點、左子樹和右子樹。若規(guī)定D,L,R分別代表“訪問根結點”、“遍歷根結點的左子樹”和“遍歷根結點的右子樹”，根據(jù)遍歷算法對訪問根結點處理的位置，稱下面三種遍歷算法分別為前序遍歷（DLR）、中序遍歷（LDR）和后序遍歷（LRD）。8.4.1二叉樹遍歷前序遍歷（DLR）遞歸算法為：若二叉樹為空則算法結束；否則：（1）訪問根結點；（2）前序遍歷根結點的左子樹；（3）前序遍歷根結點的右子樹。對于圖8-7（b）所示的二叉樹，前序遍歷訪問結點的次序為：ABDGCEF中序遍歷（LDR）遞歸算法為：若二叉樹為空則算法結束；否則：（1）中序遍歷根結點的左子樹；（2）訪問根結點；（3）中序遍歷根結點的右子樹。對于圖8-7（b）所示的二叉樹，中序遍歷訪問結點的次序為：DGBAECF后序遍歷（LRD）遞歸算法為：若二叉樹為空則算法結束；否則：（1）后序遍歷根結點的左子樹；（2）后序遍歷根結點的右子樹；（3）訪問根結點。對于圖8-7（b）所示的二叉樹，后序遍歷訪問結點的次序為：GDBEFCA

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

當對一個二叉樹用一種特定的遍歷方法來遍歷時，其遍歷序列一定是線性的，且是惟一的。8.4.2二叉鏈存儲結構下二叉樹遍歷的實現(xiàn)

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

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

為了通用性，把訪問操作設計成前序遍歷二叉樹函數(shù)的一個函數(shù)虛參Visit()。voidInOrder(BiTreeNode*t,voidVisit(DataTypeitem))//中序{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); }}二叉樹撤消操作函數(shù)二叉樹的撤消操作實際上是二叉樹遍歷操作的一個具體應用。由于二叉樹中每個結點允許有左孩子結點和右孩子結點，所以在釋放某個結點的存儲空間前必須先釋放該結點左孩子結點的存儲空間和右孩子結點的存儲空間，因此，二叉樹撤消操作必須是后序遍歷的具體應用。撤消操作算法實現(xiàn)如下：voidDestroy(BiTreeNode**root){if((*root)!=NULL&&(*root)->leftChild!=NULL)Destroy(&(*root)->leftChild);

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

free(*root);}8.4.3二叉樹遍歷的應用

1打印二叉樹把二叉樹逆時針旋轉900C，按照二叉樹的凹入表示法打印二叉樹?？砂汛撕瘮?shù)設計成遞歸函數(shù)。由于把二叉樹逆時針旋轉900C后，在屏幕上方的首先是右子樹，然后是根結點，最后是左子樹，所以打印二叉樹算法是一種特殊的中序遍歷算法。voidPrintBiTree(BiTreeNode*bt,intn){inti; if(bt==NULL)return; PrintBiTree(bt->rightChild,n+1); for(i=0;i<n-1;i++)printf(""); if(n>0) {printf("---"); printf("%c\n",bt->data); } PrintBiTree(bt->leftChild,n+1);}在二叉樹中查找數(shù)據(jù)元素操作的要求是：在bt為根結點指針的二叉樹中查找數(shù)據(jù)元素x，若查找到數(shù)據(jù)元素x時返回該結點的指針；若查找不到數(shù)據(jù)元素x時返回空指針。在二叉樹bt中查找數(shù)據(jù)元素x算法可設計成先序遍歷算法，此時查找結點的次序是：首先在根結點查找，然后在左子樹查找，最后在右子樹查找。但是，和常規(guī)遞歸算法不同的是，此算法當一個分支上的結點比較完仍未查找到數(shù)據(jù)元素x時，要返回到該結點的雙親結點處繼續(xù)查找。因此，此算法是一個回溯算法。2查找數(shù)據(jù)元素BiTreeNode*Search(BiTreeNode*bt,DataTypex){BiTreeNode*p;if(bt==NULL)returnNULL; if(bt->data==x)returnbt;if(bt->leftChild!=NULL){p=Search(bt->leftChild,x); if(p!=NULL)returnp; }if(bt->rightChild!=NULL){p=Search(bt->rightChild,x); if(p!=NULL)returnp; }

returnNULL;}例8-2編寫一個程序，首先建立如圖8-10（b）所示的帶頭結點的二叉鏈存儲結構二叉樹，然后打印該二叉樹，最后輸出分別按照前序遍歷二叉樹次序、中序遍歷二叉樹次序和后序遍歷二叉樹次序訪問各結點的序列信息。設計：輸出顯示函數(shù)設計：按照某種遍歷方法輸出顯示二叉樹各結點的信息，其實就是把上述各遍歷二叉樹函數(shù)中的Visit()函數(shù)設計成輸出顯示結點信息的函數(shù)。Visit()函數(shù)設計如下：voidVisit(DataTypeitem){printf("%c",item);}

3.應用舉例

8.4.4.非遞歸的二叉樹遍歷算法

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

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

當按某種規(guī)則遍歷二叉樹時，保存遍歷時得到的結點的后繼結點信息和前驅結點信息的最常用的方法是建立線索二叉樹。對二叉鏈存儲結構的二叉樹分析可知，在有n個結點的二叉樹中必定存在n+1個空鏈域。

規(guī)定：當某結點的左指針為空時，令該指針指向按某種方法遍歷二叉樹時得到的該結點的前驅結點；當某結點的右指針為空時，令該指針指向按某種方法遍歷二叉樹時得到的該結點的后繼結點。僅僅這樣做會使我們不能區(qū)分左指針指向的結點到底是左孩子結點還是前驅結點，右指針指向的結點到底是右孩子結點還是后繼結點。因此我們再在結點中增加兩個線索標志位來區(qū)分這兩種情況。每個結點的結構就如下所示：leftThreadleftChilddatarightChildrightThread

結點中指向前驅結點和后繼結點的指針稱為線索。在二叉樹的結點上加上線索的二叉樹稱作線索二叉樹。對二叉樹以某種方法（如前序、中序或后序方法）遍歷使其變?yōu)榫€索二叉樹的過程稱作按該方法對二叉樹進行的線索化。

線索標志位定義如下：ADGECF(a)B010A00B10C01D01E11F11G1(b)010A00B10C01D01E11F11G1(d)010A00B10C01D01E11F11G1(c)rootrootroot線索二叉樹b—中序c—前序d—后序

一旦建立了某種方式的線索二叉樹后，用戶程序就可以像操作雙向鏈表一樣操作該線索二叉樹。例如，一旦建立了中序線索二叉樹后，用戶程序就可以設計一個正向循環(huán)結構遍歷該二叉樹的所有結點，循環(huán)初始定位在中序線索二叉樹的第一個結點位置，每次循環(huán)使指針指向當前結點的中序遍歷的后繼結點位置，當指針指向中序線索二叉樹的最后一個結點位置后循環(huán)過程結束；或者用戶程序可以設計一個反向循環(huán)結構遍歷該二叉樹的所有結點，循環(huán)初始定位在中序線索二叉樹的最后一個結點位置，每次循環(huán)使指針指向當前結點的中序遍歷的前驅結點位置，當指針指向中序線索二叉樹的第一個結點位置前循環(huán)過程結束。這種算法設計要求分別設計三個函數(shù)：First()：定位在第一個結點位置；Next()：移動到下一個結點位置；End()：是否已經到最后下一個結點位置；當然，還需要一個根據(jù)二叉樹構造線索二叉樹的函數(shù)。typedefstruct{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;}voidFirst(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;}

voidNext(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;}例8-3編寫一個程序，首先建立如圖8-10（a）所示的不帶頭結點的二叉樹，然后中序線索化該二叉樹，最后用循環(huán)結構輸出該中序線索化二叉樹各結點的序列信息。voidmain(void){ThreadBiNode*root;ThreadBiTreetree;

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

printf("二叉樹中序正向遍歷序列為：");ThreadInitiate(&tree,root);//循環(huán)初始化

for(First(&tree);!EndOfNext(&tree);Next(&tree))printf("%c",tree.current->data);}8.6哈夫曼樹1.哈夫曼樹的基本概念

從A結點到B結點所經過的分支序列叫做從A結點到B結點的路徑；從A結點到B結點所經過的分支個數(shù)叫做從A結點到B結點的路徑長度；從二叉樹的根結點到二叉樹中所有葉結點的路徑長度之和稱作該二叉樹的路徑長度。設二叉樹有n個帶權值的葉結點，定義從二叉樹的根結點到二叉樹中所有葉結點的路徑長度與相應葉結點權值的乘積之和稱作該二叉樹的帶權路徑長度（WPL），即：WPL=

其中，wi為第i個葉結點的權值，li為從根結點到第i個葉結點的路徑長度。1357713571355(a)(b)(c)(d)713下圖所示二叉樹帶權路徑長度分別為:（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具有最小帶權路徑長度的二叉樹稱作哈夫曼（Huffman）樹（或稱最優(yōu)二叉樹）。圖（d）的二叉樹是一棵哈夫曼樹。定義：由給定的n個葉結點權值可以構造很多棵形態(tài)不同的二叉樹，WPL值最小的二叉樹稱為哈夫曼樹。要使一棵二叉樹的帶權路徑長度WPL值最小，必須使權值越大的葉結點越靠近根結點。哈夫曼樹構造算法為：（1）由給定的n個權值{w1,w2,…,wn}構造n棵只有根結點的二叉樹，從而得到一個二叉樹森林F={T1,T2,…,Tn}。（2）在二叉樹森林F中選取根結點的權值最小和次小的兩棵二叉樹作為新的二叉樹的左右子樹構造新的二叉樹，新的二叉樹的根結點權值為左右子樹根結點權值之和。（3）在二叉樹森林F中刪除作為新二叉樹左右子樹的兩棵二叉樹，將新二叉樹加入到二叉樹森林F中。（4）重復步驟（2）和（3），當二叉樹森林F中只剩下一棵二叉樹時，這棵二叉樹就是所構造的哈夫曼樹。2.哈夫曼編碼問題

將傳送的文字轉換為二進制字符0和1組成的二進制串的過程為編碼。

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

哈夫曼樹可用于構造代碼總長度最短的編碼方案。具體構造方法如下：設需要編碼的字符集合為{d1,d2,…,dn}，各個字符在電文中出現(xiàn)的次數(shù)集合為{w1,w2,…,wn}，以d1,d2,…,dn作為葉結點，以w1,w2,…,wn作為各葉結點的權值構造一棵二叉樹，規(guī)定哈夫曼樹中的左分支為0，右分支為1，則從根結點到每個葉結點所經過的分支對應的0和1組成的序列便為該結點對應字符的編碼。代碼總長度最短的不等長編碼稱之為哈夫曼編碼。不等長編碼不允許存在前綴碼。前綴碼的一個例子如：A為01，B為010。如編碼存在前綴碼，則譯碼會出現(xiàn)二義性。問題：為什么哈夫曼編碼一定不會出現(xiàn)前綴碼？3.哈夫曼編碼的軟件設計

為了在構造哈夫曼樹時能方便的實現(xiàn)從雙親結點到左右孩子結點的操作，在進行哈夫曼編碼時能方便的實現(xiàn)從孩子結點到雙親結點的操作。設計哈夫曼樹的結點存儲結構為雙親孩子存儲結構。采用仿真指針實現(xiàn)，每個結點的數(shù)據(jù)結構設計為：

weightflagparentleftChildrightChild一、哈夫曼編碼的數(shù)據(jù)結構設計

從哈夫曼樹求葉結點的哈夫曼編碼實際上是從葉結點到根結點路徑分支的逐個遍歷，每經過一個分支就得到一位哈夫曼編碼值。存放哈夫曼編碼的數(shù)據(jù)元素結構為：

startBit[0]Bit[1]…Bit[MaxBit-1]二、哈夫曼編碼的算法實現(xiàn)typedefstruct//哈夫曼樹的結點結構{intweight; //權值

intflag; //標記

intparent; //雙親結點下標

intleftChild; //左孩子下標

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

intstart; //編碼的起始下標

intweight; //字符的權值}Code;哈夫曼樹構造算法如下：voidHaffman(intweight[],intn,HaffNodehaffTree[])//建立葉結點個數(shù)為n權值為weight的哈夫曼樹haffTree{intj,m1,m2,x1,x2;

//哈夫曼樹haffTree初始化。n個葉結點的哈夫曼樹共有2n-1個結點

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;}

//構造哈夫曼樹haffTree的n-1個非葉結點

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; }}

//將找出的兩棵權值最小的子樹合并為一棵子樹

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;}}哈夫曼編碼算法如下：voidHaffmanCode(HaffNodehaffTree[],intn,CodehaffCode[]){Code*cd=(Code*)malloc(sizeof(Code));inti,j,child,parent;

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

//由葉結點向上直到根結點 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; }}

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

（e）哈夫曼編碼結果

10011

10113

1125

037例8-5設有字符集{A,B,C,D}，各字符在電文中出現(xiàn)的次數(shù)集為{1,3,5,7}，設計各字符的哈夫曼編碼。#include<stdio.h>#include<stdlib.h>#defineMaxValue10000 #defineMaxBit4 #defineMaxN100#include"Haffman.h"voidmain(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);

//輸出每個葉結點的哈夫曼編碼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");}}程序運行輸出結果如下：Weight=1Code=100Weight=3Code=101Weight=5Code=11Weight=7Code=0

該結果和圖8-15所示的該問題的人工設計的哈夫曼編碼方案完全吻合。

8.7并查集1．等價關系和等價類

設關系R為定義在集合X上的二元關系，若關系R是等價關系，則具備以下性質：①自反性：若對每個x∈X，有(x,x)∈R，則稱R具有自反性。②對稱性：若對任意x,y∈X，當(x,y)∈R時，有(y,x)∈R，則稱R是對稱的。③傳遞性：設x,y,z∈X，當(x,y)∈R且(y,z)∈R時，有(x,z)∈R，稱R具有傳遞性。許多問題可抽象為等價類問題。例如，為檢驗一個軟件是否存在缺陷，需要構建一個包含所有有效輸入數(shù)據(jù)的集合。這個集合中的元素往往數(shù)量龐大。一般，先將包含所有有效輸入數(shù)據(jù)的集合劃分為若干個子集，然后從每個子集中挑選出少量具有代表性的數(shù)據(jù)作為測試用例。這樣就可以有效減少不必要的重復測試，這是軟件黑盒測試中常用的一種測試用例設計策略。2.并查集的思想并查算法本質上就是確定等價類的有效算法，其運算過程可歸納如下：①令集合X中的每個元素各自構成一個只含單個元素的子集X1,X2,X3,…,Xn。②重復輸入m個等價對，進行以下處理：對于每個輸入的等價對(x,y)，設x∈Xi，y∈Xj：若Xi=Xj，即x與y屬于同一個集合，則不做任何操作；若Xi

Xj，即x與y屬于不同的集合，則將Xj并入Xi中。并查算法執(zhí)行的結果是形成若干個非空子集，這些非空子集即為集合X關于關系R的等價類。該算法主要由“合并操作”和“查找操作”組成：查找操作判定某個元素所在子集，然后進行兩個互不相交子集的合并操作。等價類可以采用樹結構表示。用一棵樹代表一個集合，如果兩個結點在同一棵樹中，則認為這兩個結點在同一個集合中。用樹結構表示的等價類，大多數(shù)情況下，其存儲方法采用雙親表示法。具體的存儲結構可以采用元素集合存儲在一個數(shù)組中，所有相同的等價類放在同一個根結點的樹中，樹用雙親表示法表示。例8-5設集合X={x|1≤x≤10，且x是整數(shù)}，R是X上的等價關系。

R={(1,3),(3,5),(3,7),(2,4),(4,6),(2,8)}求出集合X的關于R的等價類，并畫出存儲結構示意圖。說明：這里省略了類如(1,1)的自反關系、類如(3,1)的對稱關系以及類如(1,5)的部分傳遞關系。