樹(shù)的遍歷和哈夫曼樹(shù)

數(shù)據(jù)結(jié)構(gòu)北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系史晟輝shishenghui@shish@數(shù)據(jù)結(jié)構(gòu)

樹(shù)和森林的概念

二叉樹(shù)

二叉樹(shù)遍歷

二叉樹(shù)的計(jì)數(shù)

樹(shù)與森林

哈夫曼樹(shù)第六章樹(shù)與森林12/19/20242北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)樹(shù)和森林的概念樹(shù)的定義

樹(shù)是由n(n

0)個(gè)結(jié)點(diǎn)組成的有限集合。如果n=0，稱(chēng)為空樹(shù)；如果n>0，則

有一個(gè)特定的稱(chēng)之為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒(méi)有直接前驅(qū)；

除根以外的其它結(jié)點(diǎn)劃分為m(m

0)個(gè)互不相交的有限集合T0,T1,…,Tm-1，每個(gè)集合又是一棵樹(shù)，并且稱(chēng)之為根的子樹(shù)。12/19/20243北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)樹(shù)的特點(diǎn)每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。0層1層3層2層height=3ACGBDEFKLHMIJ12/19/20244北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)0層1層3層2層height=3結(jié)點(diǎn)結(jié)點(diǎn)的度分支結(jié)點(diǎn)葉結(jié)點(diǎn)子女雙親兄弟祖先子孫結(jié)點(diǎn)層次樹(shù)的度樹(shù)高度森林ACGBDEFKLHMIJ12/19/20245北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)(BinaryTree)二叉樹(shù)的定義二叉樹(shù)的五種不同形態(tài)

一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的、互不相交的二叉樹(shù)組成。LLRR12/19/20246北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)性質(zhì)1

若二叉樹(shù)的層次從0開(kāi)始,則在二叉樹(shù)的第i層最多有2i個(gè)結(jié)點(diǎn)。(i

0)[證明用數(shù)學(xué)歸納法]性質(zhì)2

高度為h的二叉樹(shù)最多有2h+1-1個(gè)結(jié)點(diǎn)。(h

-1)[證明用求等比級(jí)數(shù)前k項(xiàng)和的公式]20+21+22+…+2h=2h+1-1二叉樹(shù)的性質(zhì)12/19/20247北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)性質(zhì)3

對(duì)任何一棵二叉樹(shù),如果其葉結(jié)點(diǎn)有n0個(gè),度為2的非葉結(jié)點(diǎn)有n2個(gè),則有

n0＝n2＋1證明：若設(shè)度為1的結(jié)點(diǎn)有n1

個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為n，總邊數(shù)為e，則根據(jù)二叉樹(shù)的定義,總結(jié)點(diǎn)個(gè)數(shù)n=n0+n1+n2

總邊數(shù)e=2n2+n1總結(jié)點(diǎn)與總邊數(shù)的關(guān)系e=n

-1因此，n0=n2+112/19/20248北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)定義1

滿二叉樹(shù)(FullBinaryTree)

定義2

完全二叉樹(shù)(CompleteBinaryTree)

若設(shè)二叉樹(shù)的高度為h，則共有h+1層。除第h層外，其它各層(0

h-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹(shù)。12/19/20249北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)性質(zhì)4

具有n(n

0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為

log2(n+1)

-1證明：設(shè)完全二叉樹(shù)的高度為h，則有

2h

-1<n

2h+1

-1變形

2h<n+12h+1

取對(duì)數(shù)h<log2(n+1)h+1因此有l(wèi)og2(n+1)

=h+1

h=

log2(n+1)

-1上面h層結(jié)點(diǎn)數(shù)包括第h層的最大結(jié)點(diǎn)數(shù)12/19/202410北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)性質(zhì)5

如將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)0,1,2,…,n-1，則有以下關(guān)系：若i=0,則i無(wú)雙親若i>0,則i的雙親為

(i-1)/2

若2*i+1<n,則i的左子女為2*i+1，若2*i+2<n,則i的右子女為2*i+2

若i為偶數(shù),且i!=0,

則其左兄弟為i-1,若

i為奇數(shù),且i!=n-1,

則其右兄弟為i+1820137456912/19/202411北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)完全二叉樹(shù)一般二叉樹(shù)的順序表示的順序表示二叉樹(shù)的順序表示0012345678990123456789137894562012543678二叉樹(shù)的鏈表表示leftChilddatarightChilddataleftChildrightChild二叉鏈表12/19/202413北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的鏈表表示leftChilddataparentrightChildparentdataleftChildrightChild三叉鏈表12/19/202414北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)鏈表表示的示例

AAABBBCCCDDDFFFEEErootrootroot二叉樹(shù)二叉鏈表三叉鏈表12/19/202415北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)三叉鏈表的靜態(tài)結(jié)構(gòu)ABCDFErootdataparentleftChild

rightChild012345A

-11-1B023C1

-1-1D145E3-1-1F3-1-112/19/202416北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)typedefcharTreeData;//樹(shù)結(jié)點(diǎn)數(shù)據(jù)類(lèi)型typedef

structnode{//樹(shù)結(jié)點(diǎn)定義

TreeData

data;//結(jié)點(diǎn)數(shù)據(jù)域

structnode*leftChild,*rightchild;

//子女指針域}BinTreeNode;typedef

BinTreeNode*BinTree;

//樹(shù)定義，代表樹(shù)的根指針

二叉樹(shù)的定義12/19/202417北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)遍歷二叉樹(shù)遍歷的遞歸算法二叉樹(shù)遍歷的應(yīng)用二叉樹(shù)遍歷的非遞歸算法二叉樹(shù)遍歷

樹(shù)的遍歷就是按某種次序訪問(wèn)樹(shù)中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。設(shè)訪問(wèn)根結(jié)點(diǎn)記作V

遍歷根的左子樹(shù)記作L

遍歷根的右子樹(shù)記作

R

則可能的遍歷次序有

前序VLR

中序LVR

后序LRV中序遍歷二叉樹(shù)算法的框架是：若二叉樹(shù)為空，則空操作；否則中序遍歷左子樹(shù)(L)；訪問(wèn)根結(jié)點(diǎn)(V)；中序遍歷右子樹(shù)(R)。中序遍歷(InorderTraversal)--/+*abcdef遍歷結(jié)果

a+b*c-d-e/f12/19/202420北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)int

InTraverse(BiTreeT){

if(T==NULL)return0;InTraverse(T->lchild);Visit(T);InTraverse(T->rchild);return1;}二叉樹(shù)遞歸的中序遍歷算法12/19/202421北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)前序遍歷二叉樹(shù)算法的框架是：若二叉樹(shù)為空，則空操作；否則訪問(wèn)根結(jié)點(diǎn)(V)；前序遍歷左子樹(shù)(L)；前序遍歷右子樹(shù)(R)。前序遍歷(PreorderTraversal)--/+*abcdef遍歷結(jié)果

-+a*b-cd/ef12/19/202422北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)int

PreTraverse(BiTreeT){

if(T==NULL)return0;Visit(T);PreTraverse(T->lchild);PreTraverse(T->rchild);return1;}二叉樹(shù)遞歸的前序遍歷算法12/19/202423北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)后序遍歷二叉樹(shù)算法的框架是：若二叉樹(shù)為空，則空操作；否則后序遍歷左子樹(shù)(L)；后序遍歷右子樹(shù)(R)；訪問(wèn)根結(jié)點(diǎn)(V)。后序遍歷(PostorderTraversal)--/+*abcdef遍歷結(jié)果

abcd-*+ef/-12/19/202424北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)int

SucTraverse(BiTreeT){

if(T==NULL)return0;SucTraverse(T->lchild);SucTraverse(T->rchild);Visit(T);return1;}二叉樹(shù)遞歸的后序遍歷算法12/19/202425北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)遍歷中序遍歷結(jié)果：

a+b*c-d-e/f前序遍歷結(jié)果：-+a*b-cd/ef后序遍歷結(jié)果：abcd-*+ef/---/+*abcdef12/19/202426北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)遍歷的應(yīng)用二叉樹(shù)建立的遞歸算法刪除二叉樹(shù)的遞歸算法計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)的遞歸算法求二叉樹(shù)高度的遞歸算法將一棵以二叉鏈表存儲(chǔ)的二叉樹(shù)按順序方式存儲(chǔ)到一維數(shù)組中從完全二叉樹(shù)的順序表示轉(zhuǎn)換為二叉鏈表表示12/19/202427北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)遍歷的應(yīng)用二叉樹(shù)建立的遞歸算法ABCGDEF12/19/202428北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)遍歷的應(yīng)用以遞歸方式建立二叉樹(shù)。輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹(shù)結(jié)點(diǎn)前序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸,此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整數(shù)序列空結(jié)點(diǎn)。二叉樹(shù)建立的遞歸算法12/19/202429北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)如圖所示的二叉樹(shù)的前序遍歷順序?yàn)锳BC@@DE@G@@F@@@ABCGDEF@@@@@@@@12/19/202430北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)

voidCrt_BinTree(ifstream&in,BinTreeNode*&T){

TreeDatax;if(!in.eof()){in>>x;//讀入根結(jié)點(diǎn)的值

if(x!=RefValue){T=newBinTreeNode;//建立根結(jié)點(diǎn)

if(T==NULL){

cerr<<“存儲(chǔ)分配錯(cuò)!”<<endl;exit(1);}T->data=x;

Crt_BinTree(in,T->leftChild);

Crt_BinTree(in,T->rightChild);}elseT=NULL;//封閉葉結(jié)點(diǎn)

}}12/19/202431北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)刪除二叉樹(shù)的遞歸算法voiddestroy(BinTreeNode*T){

if(T!=NULL){destroy(T->leftChild);destroy(T->rightChild);

deleteT;

}}12/19/202432北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)int

Count(BinTreeNode*T){

if(T==NULL)return0;

else

return1+Count(T->leftChild)+Count(T->rightChild);}計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)的遞歸算法12/19/202433北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)intHeight(BinTreeNode*T){if(T==NULL)return

-1;

else{

int

m=

Height(T->leftChild);

int

n=

Height(T->rightChild

));return(m>n)?m+1:n+1;

}

求二叉樹(shù)高度的遞歸算法12/19/202434北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)將一棵以二叉鏈表存儲(chǔ)的二叉樹(shù)按順序方式存儲(chǔ)到一維數(shù)組中voidLink2Array(BinTreeNode*T,TreeDataC[],intk){

if(T!=NULL){C[k]=T->data;Link2Array(T->leftChild,C,2*k+1);Link2Array(T->rightChild,C,2*k+2);}}主程序調(diào)用方式

create(T,C,0);12/19/202435北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)從完全二叉樹(shù)的順序表示轉(zhuǎn)換為二叉鏈表表示voidArray2Link(

TreeDataT[],intn,inti,BinTreeNode*&

ptr){//將用T[n]

順序存儲(chǔ)的完全二叉樹(shù),以i為根//的子樹(shù)轉(zhuǎn)換成用二叉鏈表表示的以

ptr

為//根的完全二叉樹(shù)。利用引用型參數(shù)ptr

將//形參的值帶回實(shí)參。

if(i>=n)

ptr=NULL;

else{

ptr=new

BinTreeNode;//建立根結(jié)點(diǎn)

ptr->data=

T[i];Array2Link(T,n,2*i+1,ptr->leftChild);

Array2Link(T,n,2*i+2,ptr->rightChild);

}}12/19/202436北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)遍歷的非遞歸算法12/19/202437北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)int

PreTraverse(BiTreeT){if(T==NULL)return0;StackS;InitStack(S);Push(S,T);while(!Empty(S)){T=Top(S);Pop(S);

Visit(T);if(T->rchild!=NULL)Push(S,T->rchild);if(T->lchild!=NULL)Push(S,T->lchild);}DestroyStack(S);return1;}前序遍歷的非遞歸算法12/19/202438北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)中序遍歷的非遞歸算法int

InTraverse(BiTreeT){StackS;InitStack(S);while(T!=NULL||!Empty(S)){

while(T!=NULL){Push(S,T);T=T->lchild;}T=Top(S);Pop(S);

Visit(T);T=T->rchild;}DestroyStack(S);return1;}12/19/202439北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的計(jì)數(shù)例,前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},求構(gòu)造的二叉樹(shù)。由二叉樹(shù)的前序序列和中序序列可唯一地確定一棵二叉樹(shù)?

由二叉樹(shù)的后序序列和中序序列可唯一地確定一棵二叉樹(shù)?

由二叉樹(shù)的前序序列和后序序列可唯一地確定一棵二叉樹(shù)?由二叉樹(shù)的前序序列和中序序列可唯一地確定一棵二叉樹(shù)。由二叉樹(shù)的后序序列和中序序列可唯一地確定一棵二叉樹(shù)。由二叉樹(shù)的前序序列和后序序列不可唯一地確定一棵二叉樹(shù)。前序序列{ABHFDECKG}中序序列{HBDFAEKCG}EKCGABHDFEKCGABHFDKCGEABHFDEABHFDCKGHBDFEKCGAEKCGABHDF樹(shù)的存儲(chǔ)表示樹(shù)與森林dataparentABCDEFG-10001130123456

dataparentCGABDEF

雙親表示12/19/202442北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)用雙親表示實(shí)現(xiàn)的樹(shù)定義#defineMaxSize //最大結(jié)點(diǎn)個(gè)數(shù)typedefchar

TreeData;//結(jié)點(diǎn)數(shù)據(jù)typedef

struct{//樹(shù)結(jié)點(diǎn)定義

TreeDatadata;//結(jié)點(diǎn)數(shù)據(jù)域

intparent;//結(jié)點(diǎn)雙親域}TreeNode;typedef

TreeNode

Tree[MaxSize];//樹(shù)12/19/202443北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)CGABDEF

等數(shù)量的鏈域表示法ABCDEFG

data

child1child2child3childd12/19/202444北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)

datafirstChildnextSiblingGABCDEFABCDGFE

左子女-右兄弟表示法12/19/202445北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)typedefchar

TreeData;typedef

struct

node{

TreeDatadata;

structnode*firstChild,*nextSibling;}TreeNode;typedef

TreeNode*

Tree;用左子女-右兄弟表示實(shí)現(xiàn)的樹(shù)定義12/19/202446北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)CGEHT1T2T3AFBDIJKAFGHKT1T2T3BCDEIJBACEDKHIJGF3

棵樹(shù)的森林各棵樹(shù)的二叉樹(shù)表示森林的二叉樹(shù)表示森林與二叉樹(shù)的對(duì)應(yīng)關(guān)系12/19/202447北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)樹(shù)的遍歷深度優(yōu)先遍歷先根次序遍歷后根次序遍歷廣度優(yōu)先遍歷CGABDEFABCEDGF12/19/202448北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)樹(shù)的先根次序遍歷當(dāng)樹(shù)非空時(shí)訪問(wèn)根結(jié)點(diǎn)依次先根遍歷根的各棵子樹(shù)ABCEDGFCGABDEF樹(shù)先根遍歷ABEFCDG對(duì)應(yīng)二叉樹(shù)前序遍歷

ABEFCDG12/19/202449北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)樹(shù)的后根次序遍歷當(dāng)樹(shù)非空時(shí)依次后根遍歷根的各棵子樹(shù)訪問(wèn)根結(jié)點(diǎn)ABCEDGFCGABDEF樹(shù)后根遍歷EFBCGDA對(duì)應(yīng)二叉樹(shù)中序遍歷

EFBCGDA12/19/202450北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)按廣度優(yōu)先次序遍歷樹(shù)的結(jié)果

ABCDEFG廣度優(yōu)先遍歷算法樹(shù)的廣度優(yōu)先(層次次序)遍歷ABCEDGFCGABDEF12/19/202451北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)int

LevelTraverse(BiTreeT){if(T==NULL)return0;QueueQ;InitQueue(Q);EnQueue(Q,T);while(!Empty(Q)){T=Top(Q);DeQueue(Q);

Visit(T);if(T->lchild!=NULL)EnQueue(Q,T->lchild);if(T->rchild!=NULL)EnQueue(Q,T->rchild);}DestroyQueue(Q);return1;}12/19/202452北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)哈夫曼樹(shù)(HuffmanTree)路徑長(zhǎng)度(PathLength)

兩個(gè)結(jié)點(diǎn)之間的路徑長(zhǎng)度PL是連接兩結(jié)點(diǎn)的路徑上的分支數(shù)。樹(shù)的外部路徑長(zhǎng)度是各葉結(jié)點(diǎn)(外結(jié)點(diǎn))到根結(jié)點(diǎn)的路徑長(zhǎng)度之和EPL。樹(shù)的內(nèi)部路徑長(zhǎng)度是各非葉結(jié)點(diǎn)(內(nèi)結(jié)點(diǎn))到根結(jié)點(diǎn)的路徑長(zhǎng)度之和IPL。

樹(shù)的路徑長(zhǎng)度PL=EPL+IPL12/19/202453北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)3673411224556788樹(shù)的外部路徑長(zhǎng)度EPL=3*1+2*3=9樹(shù)的外部路徑長(zhǎng)度EPL=1*1+2*1+3*1+4*1=10

n個(gè)結(jié)點(diǎn)的二叉樹(shù)的路徑長(zhǎng)度不小于下述數(shù)列前n項(xiàng)的和，即12/19/202454北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)其路徑長(zhǎng)度最小者為帶權(quán)路徑長(zhǎng)度

(WeightedPathLength,WPL)擴(kuò)充二叉樹(shù)的帶權(quán)(外部)路徑長(zhǎng)度是樹(shù)的各葉結(jié)點(diǎn)所帶的權(quán)值

wi

與該結(jié)點(diǎn)到根的路徑長(zhǎng)度

li

的乘積的和。12/19/202455北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)具有不同帶權(quán)(外部)路徑長(zhǎng)度的擴(kuò)充二叉樹(shù)WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2=367*3=464*3=35帶權(quán)(外部)路徑長(zhǎng)度達(dá)到最小22244455577712/19/202456北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)哈夫曼樹(shù)帶權(quán)路徑長(zhǎng)度達(dá)到最小的擴(kuò)充二叉樹(shù)即為霍夫曼樹(shù)。在霍夫曼樹(shù)中，權(quán)值大的結(jié)點(diǎn)離根最近。哈夫曼算法

(1)由給定的

n

個(gè)權(quán)值{w0,w1,w2,…,wn-1}，構(gòu)造具有n

棵擴(kuò)充二叉樹(shù)的森林F={T0,T1,T2,…,Tn-1

}，其中每棵擴(kuò)充二叉樹(shù)Ti只有一個(gè)帶權(quán)值wi

的根結(jié)點(diǎn),其左、右子樹(shù)均為空。

12/19/202457北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)

(2)

重復(fù)以下步驟,直到F

中僅剩下一棵樹(shù)為止：①在F

中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹(shù),做為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)。置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。②在F

中刪去這兩棵二叉樹(shù)。③把新的二叉樹(shù)加入F。

哈夫曼樹(shù)的構(gòu)造過(guò)程12/19/202458北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)F:{7}{5}{2}{4}F:{7}{5}{6}7524初始合并{2}{4}F:{7}{11}752475246611合并{5}{6}F:{18}5合并{5}{6}2746111812/19/202459北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)const

intn=20;constint

m=2*n-1;

typedef

struct{

floatweight;

intparent,leftChild,rightChild;}HTNode;typedef

HTNode

HuffmanTree[m];哈夫曼樹(shù)的定義12/19/202460北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)5274WeightparentleftChild

rightChild7-1-1

-15-1-1

-12-1-1

-14-1-1

-1

-1-1

-1

-1-1

-1

-1-1

-1012345612/19/202461北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)52746WeightparentleftChild

rightChild

7-1-1

-15-1-1

-12-1-1

-14-1-1

-16-1-1

-1

-1-1

-1

-1-1

-10123456p1p24423i12/19/202462北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)5274611WeightparentleftChild

rightChild

7-1-1

-15-1-1

-124-1-144-1-16-12311-1-1

-1

-1-1

-10123456p1p25514i12/19/202463北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)5274611WeightparentleftChild

rightChild

7-1-1

-155-1-124-1-144-1-1652311-11418-1-1

-10123456p1p26605i1812/19/202464北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)建立哈夫曼樹(shù)的算法voidCreateHuffmanTree(HuffmanTreeT,

float

fr[]){

for(inti=0;i<n;i++)T[i].weight=fr[i];

for(i=0;i<m;i++){T[i].parent=-1;

T[i].leftChild=-1;

T[i].rightChild=-1;

}for(i=n;i<m;i++){

12/19/202465北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)

intmin1=min2=MaxNum;

intpos1,pos2;

for(intj=0;j<i;j++)

if(T[j].parent==-1)

if(T[j].weight<min1)

{pos2=pos1;min2=min1;pos1=j;min1=T[j].weight;}elseif(T[j].weight<min2)

{pos2=j;min2=T[j].weight;}

T[i].leftChild=pos1;

T[i].rightChild=pos2;12/19/202466北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)T[i].weight=T[pos1].weight+T[pos2].weight;T[pos1].parent=T[pos2].parent=i;}}最佳判定樹(shù)考試成績(jī)分布表

12/19/202467北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)判定樹(shù)不及格及格中良優(yōu)<60?<70?<80?<90?0.100.150.250.350.15≥≥≥≥<<<<WPL=0.10*1+0.15*2+0.25*3+0.35*4+0.15*4=3.1512/19/202468北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)最佳判定樹(shù)不及格及格中良優(yōu)<60?<70?<80?<90?0.100.150.250.350.15≥≥≥≥<<<<WPL=0.10*3+0.15*3+0.25*2+0.35*2+0.15*2=0.3+0.45+0.5+0.7+0.3=2.2512/19/202469北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼主要用途是實(shí)現(xiàn)數(shù)據(jù)壓縮。

設(shè)給出一段報(bào)文：

CASTCASTSATATATAS