樹的遍歷和哈夫曼樹

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

樹和森林的概念

二叉樹

二叉樹遍歷

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

樹與森林

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

樹是由n(n

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

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

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

0)個(gè)互不相交的有限集合T0,T1,…,Tm-1，每個(gè)集合又是一棵樹，并且稱之為根的子樹。12/19/20243北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)樹的特點(diǎn)每棵子樹的根結(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)層次樹的度樹高度森林ACGBDEFKLHMIJ12/19/20245北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹(BinaryTree)二叉樹的定義二叉樹的五種不同形態(tài)

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

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

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

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

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

對(duì)任何一棵二叉樹,如果其葉結(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ù)二叉樹的定義,總結(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

滿二叉樹(FullBinaryTree)

定義2

完全二叉樹(CompleteBinaryTree)

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

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

具有n(n

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

log2(n+1)

-1證明：設(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)的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)0,1,2,…,n-1，則有以下關(guān)系：若i=0,則i無雙親若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)完全二叉樹一般二叉樹的順序表示的順序表示二叉樹的順序表示0012345678990123456789137894562012543678二叉樹的鏈表表示leftChilddatarightChilddataleftChildrightChild二叉鏈表12/19/202413北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹的鏈表表示leftChilddataparentrightChildparentdataleftChildrightChild三叉鏈表12/19/202414北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹鏈表表示的示例

AAABBBCCCDDDFFFEEErootrootroot二叉樹二叉鏈表三叉鏈表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;//樹結(jié)點(diǎn)數(shù)據(jù)類型typedef

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

TreeData

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

structnode*leftChild,*rightchild;

//子女指針域}BinTreeNode;typedef

BinTreeNode*BinTree;

//樹定義，代表樹的根指針

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

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

遍歷根的左子樹記作L

遍歷根的右子樹記作

R

則可能的遍歷次序有

前序VLR

中序LVR

后序LRV中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)；訪問根結(jié)點(diǎn)(V)；中序遍歷右子樹(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;}二叉樹遞歸的中序遍歷算法12/19/202421北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)前序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則訪問根結(jié)點(diǎn)(V)；前序遍歷左子樹(L)；前序遍歷右子樹(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;}二叉樹遞歸的前序遍歷算法12/19/202423北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)后序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結(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;}二叉樹遞歸的后序遍歷算法12/19/202425北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹遍歷中序遍歷結(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)二叉樹遍歷的應(yīng)用二叉樹建立的遞歸算法刪除二叉樹的遞歸算法計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)的遞歸算法求二叉樹高度的遞歸算法將一棵以二叉鏈表存儲(chǔ)的二叉樹按順序方式存儲(chǔ)到一維數(shù)組中從完全二叉樹的順序表示轉(zhuǎn)換為二叉鏈表表示12/19/202427北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹遍歷的應(yīng)用二叉樹建立的遞歸算法ABCGDEF12/19/202428北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)二叉樹遍歷的應(yīng)用以遞歸方式建立二叉樹。輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹結(jié)點(diǎn)前序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸,此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整數(shù)序列空結(jié)點(diǎn)。二叉樹建立的遞歸算法12/19/202429北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)如圖所示的二叉樹的前序遍歷順序?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)刪除二叉樹的遞歸算法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ì)算二叉樹結(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;

}

求二叉樹高度的遞歸算法12/19/202434北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)將一棵以二叉鏈表存儲(chǔ)的二叉樹按順序方式存儲(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)從完全二叉樹的順序表示轉(zhuǎn)換為二叉鏈表表示voidArray2Link(

TreeDataT[],intn,inti,BinTreeNode*&

ptr){//將用T[n]

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

ptr

為//根的完全二叉樹。利用引用型參數(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)二叉樹的計(jì)數(shù)例,前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},求構(gòu)造的二叉樹。由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹?

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

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

dataparentCGABDEF

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

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

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

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

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

TreeNode

Tree[MaxSize];//樹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)的樹定義12/19/202446北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)CGEHT1T2T3AFBDIJKAFGHKT1T2T3BCDEIJBACEDKHIJGF3

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

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

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

ABCDEFG廣度優(yōu)先遍歷算法樹的廣度優(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)哈夫曼樹(HuffmanTree)路徑長(zhǎng)度(PathLength)

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

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

n個(gè)結(jié)點(diǎn)的二叉樹的路徑長(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ò)充二叉樹的帶權(quán)(外部)路徑長(zhǎng)度是樹的各葉結(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ò)充二叉樹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)哈夫曼樹帶權(quán)路徑長(zhǎng)度達(dá)到最小的擴(kuò)充二叉樹即為霍夫曼樹。在霍夫曼樹中，權(quán)值大的結(jié)點(diǎn)離根最近。哈夫曼算法

(1)由給定的

n

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

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

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

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

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

(2)

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

中僅剩下一棵樹為止：①在F

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

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

哈夫曼樹的構(gòu)造過程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];哈夫曼樹的定義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)建立哈夫曼樹的算法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;}}最佳判定樹考試成績(jī)分布表

12/19/202467北京化工大學(xué)信息學(xué)院數(shù)據(jù)結(jié)構(gòu)判定樹不及格及格中良優(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)最佳判定樹不及格及格中良優(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