《數(shù)據(jù)結(jié)構(gòu)與算法》第5章 樹型結(jié)構(gòu)

第5章樹型結(jié)構(gòu)

5.1樹

5.2二叉樹5.3樹、森林與二叉樹的關(guān)系5.1.1樹的基本概念樹 一棵樹（tree）T是由一個(gè)或一個(gè)以上的結(jié)點(diǎn)組成的有限集，其中有一個(gè)特定的結(jié)點(diǎn)R稱為樹T的根結(jié)點(diǎn)。在集合中除根結(jié)點(diǎn)R外，其余的結(jié)點(diǎn)可被劃分為n個(gè)不相交的子集T1、T2、…、Tn，其中每個(gè)子集都是樹，并且其相應(yīng)的根結(jié)點(diǎn)R1、R2、…、Rn是R的子結(jié)點(diǎn)。子集Ti

（i=1,2,…,n）稱為樹T的子樹（subtree）。

注意：定義中規(guī)定一棵樹至少要有一個(gè)結(jié)點(diǎn)，若集合中只有一個(gè)結(jié)點(diǎn)，那么它就是只有根結(jié)點(diǎn)而沒有任何子樹的樹。樹的圖形表示法如圖5.2就表示一棵含有A、B、C、D、E、F、G、H、I、J共10個(gè)結(jié)點(diǎn)的樹。其中A為根結(jié)點(diǎn)，{B、E、F}，{C、G}和{D、H、I、J}構(gòu)成根結(jié)點(diǎn)A的三棵子樹，B、C、D分別是這三棵子樹的根。圖5.1樹的圖形表示樹的凹入表示法這種表示法適合于將樹型結(jié)構(gòu)按行顯示在屏幕上或打印在紙上?？s入最少的結(jié)點(diǎn)表示樹根（如結(jié)點(diǎn)A），它的各子樹的根結(jié)點(diǎn)縮入多些而且要對(duì)齊在同一列上（如結(jié)點(diǎn)B、C、D）。各結(jié)點(diǎn)后面的陰影部分表示可以放與該結(jié)點(diǎn)有關(guān)的信息。圖5.2樹的凹入表示法術(shù)語結(jié)點(diǎn)的度

結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)；葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）

樹中度為0的結(jié)點(diǎn)；分支結(jié)點(diǎn)

樹中度不為0的結(jié)點(diǎn)，也即樹中除葉結(jié)點(diǎn)之外的所有結(jié)點(diǎn)；術(shù)語結(jié)點(diǎn)的孩子和雙親

結(jié)點(diǎn)的子樹的根稱為結(jié)點(diǎn)的孩子；反過來，該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親；兄弟結(jié)點(diǎn) 同一個(gè)雙親的孩子彼此稱為兄弟結(jié)點(diǎn)；結(jié)點(diǎn)的層次

樹的根結(jié)點(diǎn)為第一層，根的孩子為第二層，依此類推。術(shù)語樹的深度（高度）

樹中結(jié)點(diǎn)的最大層次數(shù)。例如圖5.2所示的樹的深度為3，因?yàn)镋、F、G、H、I、J等結(jié)點(diǎn)都在第三層，而沒有第四層的結(jié)點(diǎn)。森林

m(m≥0)棵互不相交的樹的集合。對(duì)樹中每個(gè)結(jié)點(diǎn)來說，其子樹的集合即為森林。如在圖5.2所示的樹中，將根結(jié)點(diǎn)A砍掉，其三棵子樹就構(gòu)成一個(gè)含三棵樹的森林。5.1.2樹的抽象數(shù)據(jù)類型

與線性表的定義類似，我們先給出樹中結(jié)點(diǎn)GTNode的定義，然后再定義樹的類GenTree：classGTNode{

public:

GTNode(constELEM);

~GTNode();

ELEMvalue();

bool

isLeaf();

GTNode*parent();

GTNode*leftmost_child();

GTNode*right_sibling();

voidsetValue(ELEM);

voidinsert_first(GTNode*n);

voidinsert_next(GTNode*n);

voidremove_first();

voidremove_next();

};classGenTree{

public:

GenTree();

~GenTree();

voidclear();

GTNode*root();

voidnewroot(ELEM,GTNode*,GTNode*);

};5.2.1二叉樹的定義及其主要特性二叉樹（binarytree） 由節(jié)點(diǎn)（node）的有限集合組成，這個(gè)集合或者為空，或者由一個(gè)根結(jié)點(diǎn)以及兩棵不相交的、分別稱為這個(gè)根的左子樹和右子樹的二叉樹組成。這兩棵樹的根稱為此二叉樹根結(jié)點(diǎn)的子結(jié)點(diǎn)。根據(jù)左子樹及右子樹存在的不同狀態(tài)，二叉樹可以有五種基本形態(tài)，如圖5.4所示。

(a)(b)(c)(d)(e)圖5.3二叉樹的五種基本形態(tài)

(a)空二叉樹(b)僅有根結(jié)點(diǎn)的二叉樹(c)右子樹為空的二叉樹(d)左子樹為空的二叉樹(e)左右子樹俱全的二叉樹二叉樹的性質(zhì)性質(zhì)1

在二叉樹第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)。性質(zhì)2

深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。性質(zhì)3

對(duì)任何一棵二叉樹T，設(shè)n0、n2分別是葉結(jié)點(diǎn)的個(gè)數(shù)和度為2的結(jié)點(diǎn)的個(gè)數(shù)，則有n0=n2+1。 以上三條性質(zhì)是一般二叉樹所共有的。下面我們先定義兩種特殊的二叉樹，然后指出它們特有的性質(zhì)。滿二叉樹完全二叉樹圖5.4特殊的二叉樹術(shù)語滿二叉樹 一棵深度為k的二叉樹若有2k-1個(gè)結(jié)點(diǎn)，則此種二叉樹稱為滿二叉樹。

完全二叉樹(順序二叉樹)

我們可以對(duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，約定從根結(jié)點(diǎn)開始按層由左向右給出編號(hào)1，2，3，…。在進(jìn)行這樣的編號(hào)后，從編號(hào)為1的結(jié)點(diǎn)開始，由連續(xù)編號(hào)的任意多個(gè)結(jié)點(diǎn)組成的二叉樹稱為完全二叉樹。二叉樹的性質(zhì)性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為+1。性質(zhì)5

對(duì)于一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹，其任何一個(gè)編號(hào)為i的結(jié)點(diǎn)（1≤i≤n），都有以下結(jié)果：

(1)若i=1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無雙親； 若i>1，則結(jié)點(diǎn)i的雙親是結(jié)點(diǎn)。

(2)若2i≤n，則結(jié)點(diǎn)i的左孩子是2i； 若2i>n，則結(jié)點(diǎn)i無左孩子。

(3)若2i+1≤n，則結(jié)點(diǎn)i的右孩子是2i+1； 若2i+1>n，則結(jié)點(diǎn)i無右孩子。5.2.2二叉樹的實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu) 對(duì)于完全二叉樹（包括滿二叉樹），由于它有很好的性質(zhì)，可用一維數(shù)組依次存儲(chǔ)它的各結(jié)點(diǎn)。根據(jù)性質(zhì)5，已知任一結(jié)點(diǎn)的編號(hào)i以后，可以很方便地求出它的雙親結(jié)點(diǎn)和左右孩子結(jié)點(diǎn)的位置。這種存儲(chǔ)方式既不浪費(fèi)空間，又便于有關(guān)的運(yùn)算。 但是，對(duì)于一般二叉樹，如圖5.6所示的二叉樹，若用順序存儲(chǔ)則很不合理了。12345678910(a)完全二叉樹1234567(b)一般二叉樹圖5.5二叉樹的順序存儲(chǔ)結(jié)構(gòu)圖5.6一棵非完全二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)于一般二叉樹，根據(jù)它的定義，最適合使用一種二叉鏈表結(jié)構(gòu)（非線性鏈表）來存儲(chǔ)它。在這種鏈表中，每個(gè)結(jié)點(diǎn)至少包含三個(gè)域，即：數(shù)據(jù)域和左、右指針域，二叉樹結(jié)點(diǎn)類的定義如下：classBinNode{ //二叉樹結(jié)點(diǎn)類public: BELEMelement; //該結(jié)點(diǎn)的值

BinNode*left; //指向左孩子的指針

BinNode*right; //指向右孩子的指針

//以下是兩個(gè)構(gòu)造函數(shù)

BinNode(){left=right=NULL;}

BinNode(BELEMe,BinNode*l=NULL,BinNode*r =NULL)

{element=e;left=l;right=r;}

~BinNode(){} //析構(gòu)函數(shù)

BinNode*leftchild()const{returnleft;}

BinNode*rightchild()const{returnright;}

BELEMvalue()const{returnelement；}；

voidsetValue(BELEMval){element=val;}

bool

isLeaf()const //如果是葉結(jié)點(diǎn)則返回TRUE

{return(left==NULL)&&(right==NULL);}

void*operatornew(size_t);

voidoperatordelete(void*);

};用二叉鏈表實(shí)現(xiàn)二叉樹表達(dá)式樹將線性表示的代數(shù)式非線性化，變成一個(gè)樹型結(jié)構(gòu)，在這種樹型結(jié)構(gòu)中，更能明確表示代數(shù)式的計(jì)算過程。我們可用一棵二叉樹表示這種代數(shù)式，在分支結(jié)點(diǎn)上存儲(chǔ)運(yùn)算符，在葉結(jié)點(diǎn)上存儲(chǔ)操作數(shù)。圖5.8代數(shù)式(4x*(2x+a))-c)的表達(dá)式樹表達(dá)式樹的實(shí)現(xiàn)enum

Nodetype{leaf,internal}; //使用聯(lián)合實(shí)現(xiàn)分支結(jié)點(diǎn)與葉結(jié)點(diǎn)的不同定義

classVarBinNode{

public:

Nodetype

mytype;

union{

struct{

VarBinNode*left; //左孩子

VarBinNode*right; //右孩子

Operatoropx; //

}intl;

Operandvar; //葉結(jié)點(diǎn)上只存一個(gè)值

}；

VarBinNode(constOperand&val) //構(gòu)造函數(shù)：葉結(jié)點(diǎn)

{mytype=leaf;var=val;}

//構(gòu)造函數(shù)：分支結(jié)點(diǎn)

VarBinNode(constOperator&op,VarBinNode*l,VarBinNode*r){

mytype=internal;intl.opx=op;intl.left=l;intl.right=r;}

bool

isLeaf(){returnmytype==leaf;}

VarBinNode*leftchild(){returnintl.left;}

VarBinNode*rightchild(){returnintl.right;}

};

//使用類繼承和虛函數(shù)實(shí)現(xiàn)不同的分支結(jié)點(diǎn)與葉結(jié)點(diǎn)

classVarBinNode{ //結(jié)點(diǎn)的基類

public:

virtualbool

isLeaf()=0;

};

classLeafNode:publicVarBinNode{ //葉結(jié)點(diǎn)子類

private：

Operandvar; //操作數(shù)的值

public:

LeafNode(constOperand&val){var=val;} //構(gòu)造函數(shù)

bool

isLeaf(){returnTRUE;} //

Operand&value(){returnvar;} //返回結(jié)點(diǎn)的值

}；classIntlNode:publicVarBinNode{ //分支結(jié)點(diǎn)子類

private:

VarBinNode*left; //左孩子

VarBinNode*right; //右孩子

Operandopx;

public:

IntlNode(constOperator&op,VarBinNode*l,VarBinNode*r)

{opx=op;left=l;right=r;} //構(gòu)造函數(shù)

bool

isLeaf(){FALSE;}//

VarBinNode*leftchild(){returnleft;} //左孩子

VarBinNode*rightchild(){returnright;} //右孩子

Operator&value(){returnopx;} //結(jié)點(diǎn)的值（運(yùn)算符）

}；

voidtraverse(VarBinNode*rt){

if(rt==NULL)return;

if(rt->isLeaf())

cout<<“Leaf:“<<((LeafNode*)rt)->value()<<“\n”;

else{

cout<<“Internal:“<<((IntlNode*)rt)->value()<<“\n”;

traverse(((IntlNode*)rt)->leftchild());

traverse(((IntlNode*)rt)->rightchild());

}

}5.2.3二叉樹的遍歷遍歷 對(duì)樹中每個(gè)結(jié)點(diǎn)都訪問到而且只訪問一次。 對(duì)二叉樹的遍歷也可以相應(yīng)地分解為三項(xiàng)“子任務(wù)”：(1)訪問根結(jié)點(diǎn)；(2)遍歷左子樹（即依次訪問左子樹上的全部結(jié)點(diǎn)）；(3)遍歷右子樹（即依次訪問右子樹上的全部結(jié)點(diǎn)）；

遍歷算法先序(根)遍歷若二叉樹為空，則返回；否則依次執(zhí)行以下操作：

(1)訪問根結(jié)點(diǎn)；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。中序(根)遍歷若二叉樹為空，則返回；否則依次執(zhí)行以下操作：

(1)中序遍歷左子樹；

(2)訪問根結(jié)點(diǎn)；

(3)中序遍歷右子樹。后序(根)遍歷若二叉樹為空，則返回；否則依次執(zhí)行以下操作：

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點(diǎn)。例：圖5.7(b)二叉樹的先、中、后序遍歷先序：ABDECFG中序：DBEACGF后序：DEBGFCA遍歷算法voidpreorder(BinNode*rt) //rt是樹或子樹的根

{

if(rt==NULL)return; //當(dāng)子樹為空時(shí)返回

visit(rt); //訪問根結(jié)點(diǎn)

preorder(rt->leftchild());//依先序遍歷左子樹

preorder(rt->rightchild());//依先序遍歷右子樹

}

voidinorder(BinNode*rt) //rt是樹或子樹的根

{

if(rt==NULL)return; //當(dāng)子樹為空時(shí)返回

inorder(rt->leftchild()); //依中序遍歷左子樹

visit(rt); //訪問根結(jié)點(diǎn)

inorder(rt->rightchild());//依中序遍歷右子樹

}

voidpostorder(BinNode*rt) //rt是樹或子樹的根

{

if(rt==NULL)return; //當(dāng)子樹為空時(shí)返回

postorder(rt->leftchild());//依中序遍歷左子樹

postorder(rt->rightchild());//依中序遍歷右子樹

visit(rt); //訪問根結(jié)點(diǎn)

}5.3.1樹的存儲(chǔ)結(jié)構(gòu)父節(jié)點(diǎn)表示法 除根結(jié)點(diǎn)外的每個(gè)結(jié)點(diǎn)都有一個(gè)指向其雙親結(jié)點(diǎn)的指針，而不要求指向孩子結(jié)點(diǎn)的指針。用一維數(shù)組來存儲(chǔ)樹的有關(guān)信息。在數(shù)組中，每個(gè)數(shù)組元素對(duì)應(yīng)樹的一個(gè)結(jié)點(diǎn)，它包含兩個(gè)域：一個(gè)是數(shù)據(jù)域（data），存放該結(jié)點(diǎn)所包含的數(shù)據(jù)；一個(gè)是指針域（parent），指向該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的位置（整數(shù)）。缺點(diǎn)：求某結(jié)點(diǎn)的孩子結(jié)點(diǎn)（如果有的話）比較困難，因?yàn)檫@需要從頭到尾查一遍才能找到。(a)一棵樹結(jié)點(diǎn)序號(hào)dataparent1d102d213d314d425d526d637d758d859d95(b)樹的父節(jié)點(diǎn)表示法圖5.9樹的父節(jié)點(diǎn)表示法示例孩子表示法

把每個(gè)結(jié)點(diǎn)的孩子排列起來，構(gòu)成一個(gè)單鏈表。每個(gè)結(jié)點(diǎn)只要掌握了這個(gè)單鏈表的表頭，就可以找到它的全部孩子。孩子-雙親表示法 在樹的孩子表示法中，在每個(gè)結(jié)點(diǎn)中除了data、link外，再加上一個(gè)parent域，以指明它的雙親結(jié)點(diǎn)的位置。

圖5.10圖5.9(a)樹的孩子

（雙親）表示法例：孩子-兄弟表示法(二叉鏈表表示法)

以二叉鏈表的形式作為樹的存儲(chǔ)結(jié)構(gòu)。鏈表中每個(gè)結(jié)點(diǎn)設(shè)兩個(gè)指針域，一個(gè)指針指向結(jié)點(diǎn)的第一個(gè)孩子（按照樹的定義，結(jié)點(diǎn)的孩子是沒有次序的，但在具體存儲(chǔ)時(shí)可以規(guī)定哪個(gè)孩子是第一個(gè)，哪個(gè)是第二個(gè)，等等），另一個(gè)指針指向本結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)。例：圖5.11圖5.9(a)樹的孩子-兄弟表示法5.3.2森林與二叉樹的轉(zhuǎn)換 樹和二叉樹都可以用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)。同一個(gè)二叉鏈表，若按樹的存儲(chǔ)結(jié)構(gòu)來解釋，可以還原為樹。若按二叉樹的存儲(chǔ)結(jié)構(gòu)來解釋，可以還原為二叉樹。

注意一個(gè)特點(diǎn)：一棵樹所對(duì)應(yīng)的二叉樹的根結(jié)點(diǎn)永遠(yuǎn)沒有右子樹。圖5.12圖5.9(a)樹對(duì)應(yīng)的二叉樹規(guī)則1.森林轉(zhuǎn)換成二叉樹 設(shè)F={T1,T2,…,Tm}是森林，則可按如下規(guī)則轉(zhuǎn)換為一棵二叉樹B=(root,LB,RB)：

(1)若F為空（m=0），則B為空樹；

(2)若F非空（m≠0），則森林中T1的根作為二叉樹B的根root；T1中各子樹組成的森林F1={T11,T12,…,T1s}轉(zhuǎn)換成的二叉樹作為B的左子樹LB；森林F’={T2,T3,…,Tm}轉(zhuǎn)換成的二叉樹作為B的右子樹RB。圖5.13森林與二叉樹的轉(zhuǎn)換示例規(guī)則2.二叉樹轉(zhuǎn)換成森林 設(shè)B=(root，LB，RB)是一棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林F={T1,T2,…,Tm} (1)若B為空，則F為空；

(2)若B非空，則B的根root作為F中第一棵樹T1的根；B的左子樹LB轉(zhuǎn)換成的森林作為T1的各子樹；B的右子樹RB轉(zhuǎn)換成的森林作為F中的T2，T3

，…，Tm。5.3.3樹和森林的遍歷樹的遍歷 根據(jù)樹的定義，對(duì)樹的遍歷可以有以下幾種方法：先序（根）遍歷

先訪問樹的根結(jié)點(diǎn)，再先序遍歷根結(jié)點(diǎn)的各棵子樹。后序（根）遍歷

若樹的根結(jié)點(diǎn)有子樹，則先后序遍歷各棵子樹，然后再訪問根結(jié)點(diǎn)；否則（根結(jié)點(diǎn)無子樹），只訪問根結(jié)點(diǎn)。

例：先序遍歷：G、H、I、J后序遍歷：H、J、I、G森林的遍歷

對(duì)森林的遍歷也有以下兩種方法：先序遍歷森林

若森林非空，則按下述規(guī)則遍歷之：

1、訪問森林中第一棵樹的根結(jié)點(diǎn)；

2、先序遍歷第一棵樹根結(jié)點(diǎn)的各子樹組成的 森林；

3、先序遍歷森林中除第一棵樹之外其余的樹 組成的森林。后序遍歷森林

若森林非空，則按下述規(guī)則遍歷之：

1、后序遍歷森林中第一棵樹根結(jié)點(diǎn)的各子樹 組成的森林；

2、訪問森林中第一棵樹的根結(jié)點(diǎn)；

3、后序遍歷森林中除第一棵樹之外其余的樹 組成的森林。例：先序遍歷：A、B、C、D、E、F、G、H、I、J后序遍歷：B、C、D、A、F、E、H、J、I、G5.3.4哈夫曼樹和哈夫曼編碼哈夫曼樹 哈夫曼樹是一類帶權(quán)路徑長(zhǎng)度最短的樹。例：如果我們要求將學(xué)生的學(xué)習(xí)成績(jī)由百分制轉(zhuǎn)換為五級(jí)分制，只需用下面的條件語句實(shí)現(xiàn)即可。

if(a<60)

b=‘E’; //60分以下成績(jī)?yōu)椴患案?/p>

elseif(a<70)

b=‘D’; //60至69分成績(jī)?yōu)榧案?/p>

elseif(a<80)

b=‘C’; //70至79分成績(jī)?yōu)橹械?/p>

elseif(a<90)

b=‘B’; //80至89分成績(jī)?yōu)榱己?/p>

elseb=‘A’; //90分以上成績(jī)?yōu)閮?yōu)秀（c）圖5.14百分制轉(zhuǎn)換為五級(jí)分制的判定樹 算法的效率依賴于學(xué)生成績(jī)的分布。假設(shè)有一批學(xué)生成績(jī)的分布如下表所示： 以二叉樹的觀點(diǎn)來看，將判斷框看成樹的分支結(jié)點(diǎn)，判斷結(jié)果看成樹的葉結(jié)點(diǎn)（用方框表示）。一個(gè)百分制成績(jī)轉(zhuǎn)換為相應(yīng)的五級(jí)分制成績(jī)的過程，就是在判定樹中從根結(jié)點(diǎn)“走”到葉結(jié)點(diǎn)的過程，所用的判斷次數(shù)就是葉結(jié)點(diǎn)所在的層數(shù)減1。分?jǐn)?shù)0~5960~6970~7980~8990~100比例515403010路徑長(zhǎng)度 葉結(jié)點(diǎn)所在的層數(shù)減1，即這條路徑中所含的邊數(shù)。帶權(quán)路徑長(zhǎng)度

葉結(jié)點(diǎn)的路徑長(zhǎng)度與該葉結(jié)點(diǎn)所帶權(quán)值的乘積。例如在圖5.16(b)中，結(jié)點(diǎn)“優(yōu)秀”（設(shè)其權(quán)值為10）的帶權(quán)路徑長(zhǎng)度為40樹的帶權(quán)路徑長(zhǎng)度

樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為：

其中n為葉結(jié)點(diǎn)數(shù)目，wk為第k個(gè)葉結(jié)點(diǎn)的權(quán)值，lk為第k個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度。哈夫曼樹的定義 設(shè)有n個(gè)權(quán)值{w1，w2，…,wn

}，構(gòu)造具有n個(gè)結(jié)點(diǎn)的二叉樹，每個(gè)葉結(jié)點(diǎn)帶有一個(gè)權(quán)值wi

。在所有這樣的二叉樹中，帶權(quán)路徑長(zhǎng)度WPL最小的一棵二叉樹稱為哈夫曼樹。哈夫曼（Huffman）算法

(1)根據(jù)給定的n個(gè)權(quán)值{w1，w2，…，wn}(n≥2)，構(gòu)成n棵二叉樹的集合F={T1，T2，…，Tn}，其中每棵二叉樹Ti只有一個(gè)根結(jié)點(diǎn)，它帶有權(quán)值wi(i

=1，2，…，n)。

(2)在F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹作為左右子樹，構(gòu)造一棵新的二叉樹，并且置新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左右子樹根結(jié)點(diǎn)的權(quán)值之和。然后從F中刪去原來的兩棵樹，加入這棵新構(gòu)成的樹。

(3)重復(fù)第(2)步，直到F中只有一棵樹為止，這棵樹就是哈夫曼樹。圖5.15哈夫曼樹的構(gòu)造過程示意圖哈夫曼編碼例：設(shè)某一文本中只含有4種字符A、B、C、D，它們出現(xiàn)的次數(shù)分別為7、5、2、4，則構(gòu)成的哈夫曼樹如圖5.16。圖5.16哈夫曼編碼示例 我們約定：對(duì)于一切分支結(jié)點(diǎn)，其左分支標(biāo)以0，右分支標(biāo)以1。這樣標(biāo)記以后，將從根到葉的路徑上標(biāo)記的0和1依次收集起來，就得到葉結(jié)點(diǎn)對(duì)應(yīng)字符的具體編碼。 這種編碼的特性保證了譯碼時(shí)的唯一性，例如文本’ABACBDA’編碼為‘0100110101110’，在譯碼時(shí)根據(jù)編碼表從短到長(zhǎng)進(jìn)行匹配，肯定能唯一地譯為原來的文本。哈夫曼樹類的說明

classLettFreq{ //

private:

charlett; //一個(gè)字母

intfreq; //該字母出現(xiàn)的頻率

public:

LettFreq(intf,charl=‘\0’) //構(gòu)造函數(shù)

{freq=f;lett=l;}

~LettFreq(){} //析構(gòu)函數(shù)

intweight(){returnfreq;} //返回權(quán)值

charletter(){returnlett;} /