1數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程(修訂版)配套課件2第6章二叉樹(shù)和樹(shù)

前面的章節(jié)主要討論的是線(xiàn)性結(jié)構(gòu)，二叉樹(shù)和樹(shù)屬于非線(xiàn)性的結(jié)構(gòu)。遍歷非線(xiàn)性結(jié)構(gòu)比線(xiàn)性結(jié)構(gòu)要麻煩。二叉樹(shù)及樹(shù)的遍歷技術(shù)是本章各種算法的核心，而且大多是以遞歸的形式表現(xiàn)的，閱讀和編寫(xiě)遞歸算法是學(xué)習(xí)本章的難點(diǎn)。講授本章課程大約需8課時(shí)。3

樹(shù)結(jié)構(gòu)的特點(diǎn)及基本術(shù)語(yǔ)

6.1二叉樹(shù)

6.2二叉樹(shù)的遍歷

6.3樹(shù)和森林

6.4樹(shù)的應(yīng)用4樹(shù)結(jié)構(gòu)的特點(diǎn)及基本術(shù)語(yǔ)

5線(xiàn)性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素

(無(wú)前驅(qū))

根結(jié)點(diǎn)

(無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素

(無(wú)后繼)多個(gè)葉子結(jié)點(diǎn)

(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)對(duì)比樹(shù)型結(jié)構(gòu)和線(xiàn)性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)6結(jié)點(diǎn):數(shù)據(jù)元素+若干指向子樹(shù)的分支結(jié)點(diǎn)的度:分支的個(gè)數(shù)樹(shù)的度:樹(shù)中所有結(jié)點(diǎn)的度的最大值葉子結(jié)點(diǎn):度為零的結(jié)點(diǎn)分支結(jié)點(diǎn):度大于零的結(jié)點(diǎn)DHIJM基本術(shù)語(yǔ)7(從根到結(jié)點(diǎn)的)路徑：孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)、堂兄弟祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)

由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL結(jié)點(diǎn)的層次:假設(shè)根結(jié)點(diǎn)的層次為1,第l

層的結(jié)點(diǎn)的子樹(shù)根結(jié)點(diǎn)的層次為l+1樹(shù)的深度：樹(shù)中葉子結(jié)點(diǎn)所在的最大層次層次-深度-高度，86.1二叉樹(shù)一、二叉樹(shù)的定義和基本術(shù)語(yǔ)二、二叉樹(shù)的幾個(gè)基本性質(zhì)三、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)9一、二叉樹(shù)的定義和基本術(shù)語(yǔ)

10

二叉樹(shù)的定義

二叉樹(shù)是n（n≥0）個(gè)元素的有限集，它或?yàn)榭諛?shù)，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的、互不交的二叉樹(shù)組成。根結(jié)點(diǎn)左子樹(shù)右子樹(shù)ABCDEFGHKLB11二叉樹(shù)可以表現(xiàn)出五種基本形態(tài)：空樹(shù)N只含根結(jié)點(diǎn)右子樹(shù)為空樹(shù)NL左子樹(shù)為空樹(shù)NR左右子樹(shù)均不為空樹(shù)NLR12

二叉樹(shù)的基本操作：

查找類(lèi)的操作

插入類(lèi)的操作

刪除類(lèi)的操作13Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T);InOrderTraverse(T);PostOrderTraverse(T);LevelOrderTraverse(T);查找類(lèi)的操作：14InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插入類(lèi)的操作：15ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);刪除類(lèi)的操作：16二、二叉樹(shù)的幾個(gè)基本性質(zhì)17

性質(zhì)1：

在二叉樹(shù)的第i

層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)。用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

層時(shí)，只有一個(gè)根結(jié)點(diǎn)：

2i-1=20=1；假設(shè)對(duì)所有的j，1≤j

i，命題成立；二叉樹(shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，則第i層的結(jié)點(diǎn)數(shù)=2i-22=2i-1

。18

性質(zhì)2：

深度為k

的二叉樹(shù)上至多含

2k-1

個(gè)結(jié)點(diǎn)（k≥1）。證明：

基于上一條性質(zhì)，深度為k的二叉樹(shù)上的結(jié)點(diǎn)數(shù)至多為

20+21+

+2k-1=2k-1

。19

性質(zhì)3：

對(duì)任何一棵二叉樹(shù)，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2

個(gè)度為

2

的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1。證明：設(shè)二叉樹(shù)上結(jié)點(diǎn)總數(shù)n=n0+n1+n2又二叉樹(shù)上分支總數(shù)b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。20兩類(lèi)特殊的二叉樹(shù)：滿(mǎn)二叉樹(shù)：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。完全二叉樹(shù)：樹(shù)中所含的n個(gè)結(jié)點(diǎn)和滿(mǎn)二叉樹(shù)中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。abcdefghij12345678910111213141521

性質(zhì)4：

具有n

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

log2n+1。證明：設(shè)完全二叉樹(shù)的深度為k則根據(jù)第二條性質(zhì)得2k-1≤n<2k

即k-1≤log2n<k

因?yàn)閗只能是整數(shù)，因此，k=log2n

+1。22

性質(zhì)5

：

若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下且從左至右進(jìn)行1

至n

的編號(hào)，則對(duì)完全二叉樹(shù)中任意一個(gè)編號(hào)為i

的結(jié)點(diǎn)：

(1)若i=1，則該結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)雙親，否則，編號(hào)為

i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)；

(2)若2i>n，則該結(jié)點(diǎn)無(wú)左孩子，

否則，編號(hào)為

2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；

(3)若2i+1>n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，

否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。23三、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

二叉樹(shù)順序存儲(chǔ)表示二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)表示24#defineMAX_TREE_SIZE100//二叉樹(shù)的最大結(jié)點(diǎn)數(shù)typedef

TElemTypeSqBiTree[MAX_TREE_SIZE];//0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTreebt;

二叉樹(shù)順序存儲(chǔ)表示25例如:

ABDCEF012345678910111213ABCDEF140132626

二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)表示1.二叉鏈表2．三叉鏈表3．線(xiàn)索鏈表27ADEBCFroot結(jié)點(diǎn)結(jié)構(gòu):1.二叉鏈表lchilddatarchild28typedefstruct

BiTNode

{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類(lèi)型描述如下:29rootADEBCF2．三叉鏈表parent

lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):30

typedefstruct

TriTNode

{

//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;

structTriTNode*lchild,*rchild;//左右孩子指針

struct

TriTNode

*parent;//雙親指針

}TriTNode,*TriTree;parentlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類(lèi)型描述如下:31（請(qǐng)見(jiàn)后面的線(xiàn)索二叉樹(shù)）3．線(xiàn)索鏈表326.2二叉樹(shù)遍歷一、問(wèn)題的提出二、遍歷算法描述三、遍歷算法應(yīng)用舉例四、線(xiàn)索二叉樹(shù)33

順著某一條搜索路徑巡訪二叉樹(shù)中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。一、問(wèn)題的提出“訪問(wèn)”的含義可以很廣，如：輸出結(jié)點(diǎn)的數(shù)據(jù)、判斷結(jié)構(gòu)信息等。34

“遍歷”是任何類(lèi)型均有的操作，對(duì)線(xiàn)性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹(shù)是非線(xiàn)性結(jié)構(gòu)，

每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問(wèn)題。35

對(duì)“二叉樹(shù)”而言，可以有三條搜索路徑：

1．先上后下的按層次遍歷；

2．先左（子樹(shù)）后右（子樹(shù)）的遍歷；

3．先右（子樹(shù)）后左（子樹(shù)）的遍歷。36先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法37若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）訪問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹(shù)；（3）先序遍歷右子樹(shù)。先（根）序的遍歷算法：ABCDFGEH38若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）中序遍歷左子樹(shù)；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷右子樹(shù)。中（根）序的遍歷算法：ABCDFGEH39若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）后序遍歷左子樹(shù)；（2）后序遍歷右子樹(shù)；（3）訪問(wèn)根結(jié)點(diǎn)。后（根）序的遍歷算法：ABCDFGEH40ABCDEFGHA前序遍歷：ABCDEFGHBDCEGHFB中序遍歷：DAGEHCFD后序遍歷：BGHEFCA二叉樹(shù)遍歷的輸出順序示例演示41NULLNULLNULLNULLNULLNULLNULLNULLNULLABCDEFGH先序遍歷：中序遍歷：后序遍歷：ABDBDCEGHFDAGEHCFBGHEFCA二叉樹(shù)遍歷過(guò)程的示例演示42二、遍歷算法描述

先序（前序）遍歷二叉樹(shù)的遞歸算法

中序遍歷二叉樹(shù)的遞歸算法

后序遍歷二叉樹(shù)的遞歸算法43先序遍歷二叉樹(shù)的遞歸算法voidpreorder(BiTreeT){

//

先序遍歷二叉樹(shù)

if(T==NULL)exit；

{

visit(T->data);//訪問(wèn)結(jié)點(diǎn)

preorder(T->lchild);//遍歷左子樹(shù)

preorder(T->rchild);//遍歷右子樹(shù)

}}44void

inorder(BiTreeT）{

//

中序遍歷二叉樹(shù)

if(T==NULL)exit；{

inorder(T->lchild);

//遍歷左子樹(shù)

visit(T->data);//訪問(wèn)結(jié)點(diǎn)

inorder(T->rchild);//遍歷右子樹(shù)

}}中序遍歷二叉樹(shù)的遞歸算法45void

postorder(BiTreeT）

{

//

后序遍歷二叉樹(shù)

if(T==NULL)

{

postorder(T->lchild);//遍歷左子樹(shù)

postorder(T->rchild);//遍歷右子樹(shù)

visit(T->data);//訪問(wèn)結(jié)點(diǎn)

}}后序遍歷二叉樹(shù)的遞歸算法46三、遍歷算法應(yīng)用舉例1、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)

(先序遍歷)2、求二叉樹(shù)的深度(后序遍歷)3、復(fù)制二叉樹(shù)(后序遍歷)4、建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)471、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)算法基本思想:

先序(或中序或后序)遍歷二叉樹(shù)，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問(wèn)結(jié)點(diǎn)”的操作改為：若是葉子，則計(jì)數(shù)器增1。48voidCountLeaf(BiTreeT,int&count){

if(T){

if

((!T->lchild)&&(!T->rchild))count++;

//對(duì)葉子結(jié)點(diǎn)計(jì)數(shù)

CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);

}

//if}

//CountLeaf492.求二叉樹(shù)的深度(后序遍歷)算法基本思想:

從二叉樹(shù)深度的定義可知，二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加1。由此，需先分別求得左、右子樹(shù)的深度，算法中“訪問(wèn)結(jié)點(diǎn)”的操作為：求得左、右子樹(shù)深度的最大值，然后加1。

首先分析二叉樹(shù)的深度和它的左、右子樹(shù)深度之間的關(guān)系。50int

Depth(BiTreeT

){//返回二叉樹(shù)的深度

if

(!T)depthval=0;else{

depthLeft=Depth(T->lchild);

depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

return

depthval;}513、復(fù)制二叉樹(shù)(后序遍歷)核心操作：生成一個(gè)根結(jié)點(diǎn),并鏈接左右子樹(shù)根元素T根元素NEWT遞歸操作：完成左右子樹(shù)的復(fù)制52BiTNode*CopyTree(BiTNode*T)

{

if

(!T)returnNULL;

if(T->lchild)

newlptr=CopyTree(T->lchild);//復(fù)制左子樹(shù)

elsenewlptr=NULL;

if

(T->rchild)

newrptr=CopyTree(T->rchild);//復(fù)制右子樹(shù)

elsenewrptr=NULL;

newT=GetTreeNode(T->data,newlptr,

newrptr);

return

newT;}

//CopyTree53BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr){

if

(!(T=newBiTNode))

exit(1);T->data=item;T->lchild=lptr;T->rchild=rptr;

returnT;}

生成一個(gè)二叉樹(shù)的結(jié)點(diǎn)的操作算法：(其數(shù)據(jù)域?yàn)閕tem,左指針域?yàn)閘ptr,右指針域?yàn)閞ptr)54ABCDEFGHK^D^C^^H^^K^G^F^E^A例如：下列二叉樹(shù)的復(fù)制過(guò)程如下：^BnewTT554、建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法。以下建立以二叉鏈表表示的存儲(chǔ)結(jié)構(gòu)。從輸入的字符串建立二叉樹(shù)由前序和中序的序列建立二叉樹(shù)56

以字符串的形式

根

左子樹(shù)

右子樹(shù)定義一棵二叉樹(shù)例如:ABCD以空白字符“”表示A(B(,C(,)),D(,))空樹(shù)只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù)A以字符串“A”表示以下列字符串表示57voidCreateBiTree(BiTree&T){cin>>ch;

if(ch=='')T=NULL;

else{

if

(!(T=newBiTNode))exit(OVERFLOW);T->data=ch;//生成根結(jié)點(diǎn)

CreateBiTree(T->lchild);//構(gòu)造左子樹(shù)

CreateBiTree(T->rchild);//構(gòu)造右子樹(shù)

}}//CreateBiTree58AB

C

D

ABCD上頁(yè)算法執(zhí)行過(guò)程舉例如下：ATBCD^^^^^59

僅知二叉樹(shù)的先序序列“abcdefg”

不能唯一確定一棵二叉樹(shù)，由二叉樹(shù)的先序和中序序列建樹(shù)

如果同時(shí)已知二叉樹(shù)的中序序列“cbdaegf”，則會(huì)如何？

二叉樹(shù)的先序序列二叉樹(shù)的中序序列左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)根根60abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列61preinopsps+n-1isis+n-1pre[ps]kps+1k-isps+1+(k-is)k+1n-(k-is)-1子樹(shù)序列下標(biāo)位置的確定62void

CrtBT(BiTree&T,charpre[],charino[],

intps,intis,intn){

//已知pre[ps..ps+n-1]為二叉樹(shù)的先序序列，//ins[is..is+n-1]為二叉樹(shù)的中序序列，//本算法由此兩個(gè)序列構(gòu)造二叉鏈表

if

(n==0)T=NULL;

else{k=Search(ino,pre[ps]);//在中序序列中查詢(xún)

if(k==-1)T=NULL;

else{}//遞歸程序段

}}//CrtBT……

63T=newBiTNode;T->data=pre[ps];if(k==is)T->Lchild=NULL;else

CrtBT(T->Lchild,

pre[],ino[],

ps+1,is,k-is

);if(k==is+n-1)T->Rchild=NULL;else

CrtBT(T->Rchild,

pre[],ino[],

ps+1+(k-is),k+1,n-(k-is)-1);遞歸語(yǔ)句程序段：64四、線(xiàn)索二叉樹(shù)一、何謂線(xiàn)索二叉樹(shù)？二、線(xiàn)索鏈表的遍歷算法三、如何建立線(xiàn)索鏈表？65一、何謂線(xiàn)索二叉樹(shù)？

遍歷二叉樹(shù)的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線(xiàn)性序列，例如:先序序列:

ABDEGHCFIJ中序序列:

DBGEHACIJF后序序列:

DGHEBJIFCA66

遍歷引起的思考：

遍歷二叉樹(shù)把非線(xiàn)性結(jié)構(gòu)以序列的形式加以“線(xiàn)性化”了，那么所得序列信息可否長(zhǎng)期利用？信息保持可否盡量少占用額外的存儲(chǔ)空間？是否能否形成一般化的方法？

處理辦法：

在遍歷時(shí)，串聯(lián)起前驅(qū)、后繼的關(guān)系鏈，以備后期的再利用。67

指向該線(xiàn)性序列中的“前驅(qū)”和“后繼”的指針，稱(chēng)作“線(xiàn)索”DBG

E

H

A

CIJF

以中序?yàn)槔?看結(jié)點(diǎn)H的前驅(qū)線(xiàn)索和后繼線(xiàn)索ABCFDGEHIJ的前驅(qū)線(xiàn)索H的后繼線(xiàn)索H68

與其相應(yīng)的二叉樹(shù)，稱(chēng)作“線(xiàn)索二叉樹(shù)”

包含“線(xiàn)索”的存儲(chǔ)結(jié)構(gòu)，稱(chēng)作“線(xiàn)索鏈表”

按“序”來(lái)講，可分成：“先序線(xiàn)索二叉樹(shù)”、“中序線(xiàn)索二叉樹(shù)”和“后序線(xiàn)索二叉樹(shù)”69typedefstruct

BiThrNode

{

TElemTypedata;

struct

BiThrNode*lchild,rchild;

struct

BiThrNode*pred,succ;

//前驅(qū)、后繼線(xiàn)索}

BiThrNode,*BiThrTree;線(xiàn)索二叉樹(shù)的類(lèi)型定義：70HABCDEGHFIJT中序線(xiàn)索化二叉樹(shù)示例71DBGEHACIJF線(xiàn)索關(guān)系表現(xiàn)為雙向循環(huán)鏈表查找前驅(qū)和后繼變得異常容易72

遍歷帶有線(xiàn)索的二叉樹(shù)，既無(wú)需重新遞歸遍歷，也無(wú)需棧的協(xié)助，只進(jìn)行相當(dāng)“線(xiàn)性結(jié)構(gòu)”的尋訪即可，而且可正反雙向進(jìn)行。二、線(xiàn)索鏈表的遍歷算法:73void

InOrder(BiThrTreeH,void(*visit)(BiTree))

{

//H為指向中序線(xiàn)索鏈表中頭結(jié)點(diǎn)的指針

p=H->succ;

while(p!=H)

{

visit(p);p=p->succ;

}}74三、如何建立線(xiàn)索鏈表？

建立中序線(xiàn)索化的過(guò)程，是在中序遍歷的過(guò)程中串聯(lián)起前驅(qū)和后繼的線(xiàn)索指針鏈。（線(xiàn)索化過(guò)程參照教科書(shū)）756.3樹(shù)和森林一、樹(shù)和森林的定義二、樹(shù)和森林的存儲(chǔ)結(jié)構(gòu)三、樹(shù)和森林的遍歷76一、樹(shù)和森林的定義

77

樹(shù)的定義：樹(shù)是n（n≥0）個(gè)元素的有限集D，若D為空集，則為空樹(shù)。否則：

(1)在D中存在唯一的稱(chēng)為根的數(shù)據(jù)元素root；

(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹(shù)，稱(chēng)為根root的子樹(shù)。78樹(shù)的基本操作：

查找類(lèi)的操作

插入類(lèi)的操作

刪除類(lèi)的操作79Root(T)//求樹(shù)的根結(jié)點(diǎn)查找類(lèi)的操作：Value(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的元素值

Parent(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的最左孩子RightSibling(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T)//判定樹(shù)是否為空樹(shù)TreeDepth(T)//求樹(shù)的深度TraverseTree(T)//遍歷80InitTree(&T)//初始化置空樹(shù)

插入類(lèi)的操作：CreateTree(&T,definition)

//按定義構(gòu)造樹(shù)Assign(T,cur_e,value)

//給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)

//將以c為根的樹(shù)插入為結(jié)點(diǎn)p的第i棵子樹(shù)81

ClearTree(&T)//將樹(shù)清空

刪除類(lèi)的操作：DestroyTree(&T)//銷(xiāo)毀樹(shù)的結(jié)構(gòu)DeleteChild(&T,&p,i)

//刪除結(jié)點(diǎn)p的第i棵子樹(shù)82ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹(shù)根例如:83(１)有確定的根；(２)樹(shù)根和子樹(shù)根之間為有向關(guān)系。有向樹(shù)：有序樹(shù)：子樹(shù)之間存在確定的次序關(guān)系。無(wú)序樹(shù)：子樹(shù)之間不存在確定的次序關(guān)系。84任何一棵非空樹(shù)是一個(gè)二元組

Tree=（root，F(xiàn)）其中：root被稱(chēng)為根結(jié)點(diǎn)

F

被稱(chēng)為子樹(shù)森林森林：是m（m≥0）棵互不相交的樹(shù)的集合ArootCGDHIJMFBEFKL85二、樹(shù)和森林的存儲(chǔ)結(jié)構(gòu)1.雙親表示法2.孩子鏈表表示法3.樹(shù)的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法86ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=6dataparent1.雙親表示法:87

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類(lèi)型描述:88typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)}PTree;樹(shù)結(jié)構(gòu):89r=0n=6data,firstchild0

A

-11

B

02

C

03

D

04

E

25

F

26

G

56451232.孩子鏈表表示法:ABCDEFG90typedefstruct

CTNode{

intchild;

struct

CTNode*next;}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu):

childnextC語(yǔ)言的類(lèi)型描述:91

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針

}CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu)

datafirstchild92typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

int

n,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置}CTree;樹(shù)結(jié)構(gòu):93ABCEDFG

3.樹(shù)的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法ABCDEFGrootABCDEFG94typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C語(yǔ)言的類(lèi)型描述:結(jié)點(diǎn)結(jié)構(gòu):

firstchilddatanextsibling

樹(shù)—二叉樹(shù)

將一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)的方法是：

(1)樹(shù)中所有相鄰兄弟之間加一條連線(xiàn)。

(2)對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線(xiàn)，刪去其與其它孩子結(jié)點(diǎn)之間的連線(xiàn)。(刪線(xiàn)）

(3)以樹(shù)的根結(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。樹(shù)做這樣的轉(zhuǎn)換所構(gòu)成的二叉樹(shù)是唯一的。圖

樹(shù)到二叉樹(shù)的轉(zhuǎn)換圖

樹(shù)與二叉樹(shù)的對(duì)應(yīng)2.森林轉(zhuǎn)換為二叉樹(shù)森林是若干棵樹(shù)的集合。樹(shù)可以轉(zhuǎn)換為二叉樹(shù)，森林同樣也可以轉(zhuǎn)換為二叉樹(shù)。因此，森林也可以方便地用孩子兄弟鏈表表示。森林轉(zhuǎn)換為二叉樹(shù)的方法如下：（1）將森林中的每棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)。（2）第一棵二叉樹(shù)不動(dòng)，從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹(shù)連在一起后，所得到的二叉樹(shù)就是由森林轉(zhuǎn)換得到的二叉樹(shù)。圖

森林轉(zhuǎn)換為二叉樹(shù)的過(guò)程100

森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系設(shè)森林

F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉樹(shù)

B=(LBT,Node(root),RBT);101由森林轉(zhuǎn)換成二叉樹(shù)的轉(zhuǎn)換規(guī)則為:若

F=Φ，則

B=Φ；否則，

由

ROOT(T1)

對(duì)應(yīng)得到

Node(root)；

由

(t11,t12,…,t1m)

對(duì)應(yīng)得到

LBT；

由

(T2,T3,…,Tn)

對(duì)應(yīng)得到

RBT。102由二叉樹(shù)轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為：若B=Φ，則F=Φ；否則，由Node(root)

對(duì)應(yīng)得到ROOT(T1

)；由LBT

對(duì)應(yīng)得到(t11,t12,…，t1m)；由RBT

對(duì)應(yīng)得到(T2,T3,…,Tn)。103

由此，樹(shù)的各種操作均可對(duì)應(yīng)二叉樹(shù)的操作來(lái)完成。

應(yīng)當(dāng)注意的是，和樹(shù)對(duì)應(yīng)的二叉樹(shù)，其左、右子樹(shù)的概念已改變?yōu)椋?/p>

左是孩子，右是兄弟。104

三、樹(shù)和森林的遍歷

1.樹(shù)的遍歷2.森林的遍歷3.樹(shù)的遍歷的應(yīng)用1051.樹(shù)的遍歷(可有三條搜索路徑):按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:

若樹(shù)不空，則先訪問(wèn)根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹(shù)。

若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。

若樹(shù)不空，則自上而下自左至右訪問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)。106ABCDEFGHIJK

先根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：ABEFCDGHIJK

后根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：EFBCIJKHGDA

層次遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：ABCDEFGHIJK1072．森林中第一棵樹(shù)的子樹(shù)森林；1．森林中第一棵樹(shù)的根結(jié)點(diǎn)；

BCDEFGHIJK3．森林中其它樹(shù)構(gòu)成的森林。森林由三部分構(gòu)成：2.森林的遍歷108

先序遍歷

即：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行先根遍歷。

若森林不空，則訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；先序遍歷森林中第一棵樹(shù)的子樹(shù)森林；先序遍歷森林中(除第一棵樹(shù)之外)其余樹(shù)構(gòu)成的森林。109中序遍歷

若森林不空，則中序遍歷森林中第一棵樹(shù)的子樹(shù)森林；訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；中序遍歷森林中(除第一棵樹(shù)之外)其

余樹(shù)構(gòu)成的森林。

即：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行后根遍歷。110

樹(shù)的遍歷和二叉樹(shù)遍歷的對(duì)應(yīng)關(guān)系？先根遍歷后根遍歷樹(shù)二叉樹(shù)森林先序遍歷先序遍歷中序遍歷中序遍歷111(設(shè)樹(shù)的存儲(chǔ)結(jié)構(gòu)為孩子兄弟鏈表)typedefstructCSNode{Elemdata;

structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;

求樹(shù)的深度

輸出樹(shù)中所有從根到葉子的路徑

建樹(shù)的存儲(chǔ)結(jié)構(gòu)3.樹(shù)的遍歷的應(yīng)用112intTreeDepth(CSTreeT){

if(!T)return0;

else{h1=TreeDepth(T->firstchild);h2=TreeDepth(T->nextsibling);

}}//TreeDepthreturn(max(h1+1,h2));

求樹(shù)的深度的算法：113ABCDABCD求樹(shù)深算法的理解(max(h1+1,h2))的圖解

114

輸出樹(shù)中所有從根到葉子的路徑的算法:例如：對(duì)左圖所示的樹(shù)，其輸出結(jié)果應(yīng)為：ABEABFACADGHIADGHJADGHK

ABCDEFGHIJK115void

AllPath(BitreeT,Stack&S)

{

if

(T)

{

Push(S,T->data);if(!T->Lchild&&!T->Rchild)PrintStack(S);else{

AllPath(T->Lchild,S);AllPath(T->Rchild,S);

}

Pop(S);

}//

if(T)}

//AllPath//輸出二叉樹(shù)上從根到所有葉子結(jié)點(diǎn)的路徑116ABCDEFGHABA-B-D-FDFGA-B-D-GCEHA-C-E-H輸出二叉樹(shù)上從根到所有葉子結(jié)點(diǎn)的路徑演示117ABCDEFGHIJKABEABFACADGHIADGHJADGHK輸出樹(shù)中所有從根到葉子的路徑??????如何判定葉子？118void

OutPath(BitreeT,Stack&S){

while(!T){

Push(S,T->data);

if(!T->firstchild)Printstack(s);

else

OutPath(T->firstchild,s);

Pop(S);

T=T->nextsibling;

}

//while}

//OutPath//輸出森林中所有從根到葉的路徑119

建樹(shù)的存儲(chǔ)結(jié)構(gòu)的算法:

和二叉樹(shù)類(lèi)似，不同的定義相應(yīng)有不同的算法。

假設(shè)以二元組(F，C)的形式自上而下、自左而右依次輸入樹(shù)的各邊，建立樹(shù)的孩子-兄弟鏈表。120ABCDEFG例如:對(duì)下列所示樹(shù)的輸入序列應(yīng)為:(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)ABCD(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)

算法中需要一個(gè)隊(duì)列保存已建好的結(jié)點(diǎn)的指針。121voidCreatTree(CSTree&T){T=NULL;

for(scanf(&fa,&ch);ch!=#;

scanf(&fa,&ch);)

{ p=GetTreeNode(ch);//創(chuàng)建結(jié)點(diǎn)

EnQueue(Q,p);//指針入隊(duì)列

if(fa==

#)T=p;//所建為根結(jié)點(diǎn)

else{ }

//非根結(jié)點(diǎn)的情況

}

//for}

//CreateTree

……

122GetHead(Q,s);//取隊(duì)列頭元素(指針值)while(s->data!=fa){

//查詢(xún)雙親結(jié)點(diǎn)

DeQueue(Q,s);GetHead(Q,s);}

if(!(s->firstchild))

{s->firstchild=p;r=p;}

//鏈接第一個(gè)孩子結(jié)點(diǎn)else

{r->nextsibling=p;r=p;

}

//鏈接其它孩子結(jié)點(diǎn)

非根結(jié)點(diǎn)的情況的代碼段：123

6.4樹(shù)的應(yīng)用

一、堆排序的實(shí)現(xiàn)二、二叉排序樹(shù)三、赫夫曼樹(shù)及其應(yīng)用124一、堆排序的實(shí)現(xiàn)125堆是滿(mǎn)足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或堆的定義:{12,36,27,65,40,34,98,81,73,55,49}例如:是小頂堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小頂堆)(大頂堆)復(fù)習(xí)第4章排序126rir2ir2i+1

若將該數(shù)列視作完全二叉樹(shù)，則r2i

是ri

的左孩子;r2i+1

是

ri

的右孩子。1236276549817355403498例如:是堆14不127如何“建堆”？?jī)蓚€(gè)問(wèn)題:如何“篩選”？定義堆類(lèi)型為:typedef

SqListHeapType;//堆采用順序表表示之HeapAdjust(.,.,.);12812998814973556412362740例如:是大頂堆12但在98

和12

進(jìn)行互換之后，它就不是堆了因此，需要對(duì)它進(jìn)行“篩選”98128173641298比較比較130void

HeapAdjust(RcdType&R[],int

s,int

m){//已知R[s..m]中記錄的關(guān)鍵字除R[s]之外均

//滿(mǎn)足堆的特征，本函數(shù)自上而下調(diào)整R[s]的

//關(guān)鍵字，使R[s..m]也成為一個(gè)大頂堆}//HeapAdjustrc=R[s];//暫存R[s]for

(j=2*s;j<=m;j*=2

){//j初值指向左孩子

自上而下的篩選過(guò)程;}R[s]=rc;

//將調(diào)整前的堆頂記錄插入到s位置131if(rc.key>=R[j].key)break;//再作“根”和“子樹(shù)根”之間的比較，

//若“>=”成立，則說(shuō)明已找到rc的插

//入位置s，不需要繼續(xù)往下調(diào)整R[s]=R[j];s=j;

//否則記錄上移，尚需繼續(xù)往下調(diào)整if(j<m

&&R[j].key<R[j+1].key)++j;//左/右“子樹(shù)根”之間先進(jìn)行相互比較

//令j指示關(guān)鍵字較大記錄的位置自上而下的篩選過(guò)程的代碼段：132

建堆是一個(gè)從下往上進(jìn)行“篩選”的反復(fù)過(guò)程40554973816436122798例如:排序之前的關(guān)鍵字序列為123681734998817355

現(xiàn)在，左/右子樹(shù)都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹(shù)是個(gè)“堆”即可。98494064361227133voidHeapSort(HeapType&H){

//對(duì)順序表H進(jìn)行堆排序。}

//HeapSortfor

(i=H.length/2;i>0;--i)

//建大頂堆

HeapAdjust(H.r,i,H.length);

for(i=H.length;i>1;--i)

{//調(diào)整堆來(lái)實(shí)現(xiàn)排序

H.r[1]←→H.r[i];

//將堆頂記錄和當(dāng)前未經(jīng)排序子序列

//H.r[1..i]中最后一個(gè)記錄相互交換

HeapAdjust(H.r,1,i-1);

//對(duì)H.r[1]進(jìn)行篩選

}13412345678910405549731227988164363612738181559849557340984049

堆排序的邏輯結(jié)構(gòu)是一棵完全二叉樹(shù)，而實(shí)現(xiàn)的空間則是順序表。以數(shù)據(jù)模型演示數(shù)據(jù)在順序空間的動(dòng)態(tài)變化。初始堆的建立過(guò)程：初始堆的建立過(guò)程有比較大的消耗，可達(dá)4n135堆排序第一趟：1234567891098814973362740556412129881127312641281堆排序第二趟：123456789108173496436274055121298128112731264125573堆排序第三趟：1234567891073644955362740128112988173121264125564可以看出，每趟的調(diào)整只牽涉少量的數(shù)據(jù)……

有序段136堆排序的時(shí)間復(fù)雜度分析(建堆+

n-1

次調(diào)整)：

以后的每次調(diào)整，耗費(fèi)將顯著減少。因?yàn)檫@樣調(diào)整所耗用的比較操作次數(shù)都不超過(guò)堆的樹(shù)深，是一種消耗很少的局部調(diào)整。

初始堆的建立過(guò)程:O(n)

建成深度為

h=(log2n+1)的堆,需要調(diào)整n-1次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)不超過(guò)

2*(log2(n-1)+log2(n-2)+

…+log22)<2n(log2n)

因此，堆排序的時(shí)間復(fù)雜度為O(nlogn)137二、二叉排序樹(shù)

138（1）若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；1．二叉排序的定義：

二叉排序樹(shù)或者是一棵空樹(shù)；或者是具有如下特性的二叉樹(shù)：（3）它的左、右子樹(shù)也都分別是二叉排序樹(shù)。（2）若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；139503080209010854035252388例如:是二叉排序樹(shù)。66不140（49，38，65，76，49，13，27，52）4938657649132752構(gòu)造二叉排序樹(shù)

構(gòu)建二叉排序樹(shù)的過(guò)程，是一個(gè)從空樹(shù)起不斷插入結(jié)點(diǎn)的過(guò)程。每插入一個(gè)結(jié)點(diǎn)都應(yīng)保證遵從二叉排序樹(shù)的定義。141（，，，，，，，）1327384949526576（49，38，65，76，49，13，27，52）原始序列數(shù)據(jù)4938657649132752構(gòu)造的二叉排序樹(shù)中序遍歷二叉排序樹(shù)

如果中序遍歷二叉排序樹(shù)，所得序列將是有序的，即實(shí)現(xiàn)了對(duì)原始數(shù)據(jù)的排序，二叉排序樹(shù)即由此得名。142

有關(guān)二叉排序樹(shù)更詳細(xì)的討論及算法，請(qǐng)見(jiàn)第8章查找表的二叉查找樹(shù)一節(jié)143三、赫夫曼樹(shù)及其應(yīng)用

（哈夫曼樹(shù)）最優(yōu)樹(shù)的定義如何構(gòu)造最優(yōu)樹(shù)前綴編碼壓縮的本質(zhì)就是--赫夫曼樹(shù)abaabaabadbcaabcabadababa計(jì)算機(jī)內(nèi)部：ASCII碼，定長(zhǎng)編碼；8bit-一個(gè)字節(jié)，共256個(gè)字符；（漢字-雙字節(jié)表示一個(gè)漢字，共6萬(wàn)字符，康熙字典多于這個(gè)；）25*8=200bit,144哈夫曼編碼：非定長(zhǎng)編碼原則：根據(jù)如字符出現(xiàn)頻率高，則其編碼越短。在軍事情報(bào)中，根據(jù)截留的代碼，分析每串字符出現(xiàn)的頻率，分析可能是代表什么文字？慢慢湊成一句話(huà)，就能找出每個(gè)字的代碼是什么。因?yàn)檎f(shuō)話(huà)的頻率難以更改：比如我，的之類(lèi)的。145

abaabaabadbcaabcabadababa等長(zhǎng)編碼：總共才四個(gè)字符，等長(zhǎng)編碼：都用兩個(gè)bit表示，2*25=50bit用哈夫曼樹(shù)可以更省空間跟時(shí)間計(jì)數(shù)：統(tǒng)計(jì)每個(gè)字符出現(xiàn)的次數(shù)a：13次---0；b：8次---10；c:2次----110，d：2次----111；13*1+8*2+2*3+2*3=45bit在軍事上，就可能取得時(shí)間上的勝利。146如何獲得不等長(zhǎng)的編碼-建立哈夫曼樹(shù)來(lái)進(jìn)行編碼---二叉樹(shù)的應(yīng)用哈夫曼編碼的實(shí)質(zhì)就是為了壓縮，那如何譯碼呢？147問(wèn)題：如何獲得哈夫曼編碼-----如何解出實(shí)際內(nèi)容（字符）：譯碼哈夫曼法--哈夫曼樹(shù)-輸入一串字符，計(jì)算每個(gè)字符出現(xiàn)頻率--哈夫曼樹(shù)（最優(yōu)二叉樹(shù)）-哈夫曼編碼-實(shí)現(xiàn)壓縮（輸出編碼序列）編碼過(guò)程-哈夫曼樹(shù)（解壓縮）輸出字符序列：譯碼過(guò)程什么是哈夫曼樹(shù)----最優(yōu)二叉樹(shù)？148149

最優(yōu)樹(shù)的定義樹(shù)的路徑長(zhǎng)度定義為：

樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。

結(jié)點(diǎn)的路徑長(zhǎng)度定義為：

從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上

分支的數(shù)目。150

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

WPL(T)=wklk(對(duì)所有葉子結(jié)點(diǎn))。

含n個(gè)葉子結(jié)點(diǎn)、每個(gè)葉子結(jié)點(diǎn)帶權(quán)為w，必存在一棵其帶權(quán)路徑長(zhǎng)度取最小值的二叉樹(shù)，稱(chēng)為“最優(yōu)二叉樹(shù)”或者哈夫曼樹(shù)PL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954152

根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹(shù)的集合

F={T1,T2,…,Tn}，其中每棵二叉樹(shù)中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹(shù)為空樹(shù)；如何構(gòu)造最優(yōu)樹(shù)(1)(赫夫曼算法)以二叉樹(shù)為例：153

在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹(shù)，分別作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，并置這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和；(2)154

從F中刪去這兩棵樹(shù)，同時(shí)加入剛生成的新樹(shù)；

重復(fù)(2)

和(3)

兩步，直至F中只含一棵樹(shù)為止。(3)(4)1559例如:已知權(quán)值W={

5,6,2,9,7

}5627527697671395271566713952795271667132900001111000110110111157

指的是，任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。前綴編碼

利用赫夫曼樹(shù)可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長(zhǎng)度最短。158出現(xiàn)頻度:5,6,2,9,7編碼:

101,00,100,11,01字母集:

s,t,a,e,i電文:eat編碼:eat111000025701100101911160167130100012901tiase譯電文:eat

符合前綴編碼規(guī)則才能按唯一性進(jìn)行譯碼問(wèn)題：如何獲得哈夫曼編碼-----如何解出實(shí)際內(nèi)容（字符）：譯碼哈夫曼法--哈夫曼樹(shù)-輸入一串字符，計(jì)算每個(gè)字符出現(xiàn)頻率--哈夫曼樹(shù)（最優(yōu)二叉樹(shù)）-哈夫曼編碼-實(shí)現(xiàn)壓縮（輸出編碼序列）編碼過(guò)程-哈夫曼樹(shù)（解壓縮）輸出字符序列：譯碼過(guò)程什么是哈夫曼樹(shù)----最優(yōu)二叉樹(shù)？159哈夫曼算法：就是找到最優(yōu)二叉樹(shù)，就是構(gòu)造最優(yōu)二叉樹(shù)的過(guò)程，WPL總和最小。哈夫曼算法：輸入：n個(gè)帶權(quán)值的字符---將其看成H[]數(shù)組輸出：最優(yōu)二叉樹(shù)就是哈夫曼樹(shù)。160算法流程（步驟）：1、從H[]中選擇兩個(gè)權(quán)值最小的字符x,y;2、利用x，y構(gòu)建一棵二叉樹(shù)Z,權(quán)值為xw+yw；3、將新產(chǎn)生的二叉樹(shù)Z,加入到集合中，同時(shí)將x，y刪除；4、不斷重復(fù)1、2、3，直到H[]中只剩下一個(gè)元素為止。161哈夫曼樹(shù)----哈夫曼編碼？規(guī)則：1、沿著哈樹(shù)分支，左邊為0，右邊為1；2、每個(gè)葉子結(jié)點(diǎn)的路徑：從根—該葉子結(jié)點(diǎn)所形成的01代碼串---就為該葉子結(jié)點(diǎn)對(duì)應(yīng)字符編碼。162壓縮---編碼字符----01串解壓縮—譯碼01串—字符1、從哈樹(shù)的根開(kāi)始，遇0走左分支，遇1走右分支，直至葉子結(jié)點(diǎn)----輸出相應(yīng)字符；2、不斷重復(fù)1，直到01串結(jié)束。163難點(diǎn)：哈夫曼樹(shù)的構(gòu)造

采用技巧：用數(shù)組表示二叉樹(shù)。Typedefstructleafnode{intweight;權(quán)值intleft;intright;intparent;}HNODEHNODEH[];

}164Parent，left，right表示該結(jié)點(diǎn)父結(jié)點(diǎn)，孩子結(jié)點(diǎn)的下標(biāo)Parent,left,right=-1,表示無(wú)父結(jié)點(diǎn)，無(wú)左右孩子準(zhǔn)備：建立H[]數(shù)組表示葉子結(jié)點(diǎn)，其父結(jié)點(diǎn)、左右孩子均為-1；weight，data值求哈夫曼樹(shù)函數(shù)Huffman（HNODEH[],intn）（n為葉子結(jié)點(diǎn)數(shù)）165Huffman（HNODEH[],intn）Count=n；While(count>1){If(H[].parent=-1)Selecttwomin(H,n,&index1,&index2);//找當(dāng)前數(shù)組中權(quán)值最小的兩個(gè)數(shù),其下標(biāo)用Index1，index2表示Index=creatBiTree(H,n,index1,index2)//兩結(jié)點(diǎn)建立二叉樹(shù)，新生成的結(jié)點(diǎn)為indexDelecttwomin（H，n，index1，index2；）Count--;}166Index=creatBiTree(H,n,index1,index2){H[n]為新結(jié)點(diǎn)，H[0—n-1]為放原葉子結(jié)點(diǎn)值H[n].left=index1;H[n].right=index2;H[n].parent=-1;H[n].weight=H[index1].weight+H[index2].weightH[index1].parent=n;H[index2].parent=n;}技巧：當(dāng)parent==-1，表示已經(jīng)用過(guò)該結(jié)點(diǎn)。167作業(yè)：編碼：輸入：一串英文txt（都為小寫(xiě)，不考慮空格）輸出：該txt的01壓縮串（編碼）譯碼：輸入：01串輸出：該01串表示的字符串（解壓縮譯碼）168輸入：一串英文txt（都為小寫(xiě)，不考慮空格）---1、計(jì)數(shù)（求權(quán)值weight）2、建立哈樹(shù)（數(shù)組H[]）3、哈編碼：txt的編碼（01串）4、譯碼169輸入：一串英文txt（都為小寫(xiě)，不考慮空格）1、計(jì)數(shù)—求權(quán)值：每個(gè)字母出現(xiàn)的頻率.intA[26];//放每個(gè)字符出現(xiàn)的次數(shù)chardoc[];//英文txtinti=1;

while(i<n){A[doc[i]-’a’]++;i++;}//后兩條語(yǔ)句可用A[doc[i++]-’a’]++;A[doc[i]-’a’]++;//-’a’得到該字符在A[]中的下標(biāo)位置，對(duì)其++運(yùn)算，等于累計(jì)該字符在txt中出現(xiàn)的次數(shù)，也就是它的weight。1702、建立哈樹(shù)（H[]）:哈夫曼算法計(jì)數(shù)后，得到每個(gè)字母的權(quán)值weight，就可以求得哈夫曼樹(shù)---將此樹(shù)用H[]數(shù)組表示。(程序見(jiàn)前面)1713、哈編碼：txt的編碼（01串）輸出每個(gè)葉子結(jié)點(diǎn)（每個(gè)字母）的編碼。算法思路：1、從哈樹(shù)根開(kāi)始，沿著哈樹(shù)分支，左分支為0，右分支為1；2、每個(gè)葉子結(jié)點(diǎn)的編碼：從根—>該葉子結(jié)點(diǎn)所形成的01代碼串---就為該葉子結(jié)點(diǎn)對(duì)應(yīng)字符編碼。172Outputcode(H,n){

for(i=1;i<n;i++){1、Index=found(H,n)//找到每個(gè)葉子結(jié)點(diǎn)H[i].left=H[i].right=-12、沿著H[index].parent不斷往上尋找，判斷該index是其父親的左孩子還是右孩子，如為左則將0，右則將1壓入棧中。3、,重復(fù)2，直到找到根，然后將代碼出棧，就得到該葉子結(jié)點(diǎn)代表的字符的編碼。}1734、譯碼輸入一串01串----輸出字符串算法思想：1、從根開(kāi)始走，看到1就走右分支，看0就走左分支，直到走到葉子結(jié)點(diǎn)為止（left=right=-1），輸出該葉子結(jié)點(diǎn)對(duì)應(yīng)的字符。2、重復(fù)1，直到01串結(jié)束174遷移：1、可實(shí)現(xiàn)壓縮圖像圖像RGB表示，分別用8位（一個(gè)字節(jié)）表示，如R用256個(gè)字符表示。判斷每個(gè)256個(gè)字符出現(xiàn)的概率---哈夫曼樹(shù)（數(shù)組）---每個(gè)字符的編碼---壓縮2、中文txt3、視頻壓縮175176本章學(xué)習(xí)要點(diǎn)177

1.熟練掌握二叉樹(shù)的結(jié)構(gòu)特性，了解相應(yīng)性質(zhì)的證明方法。

2.熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。

3.遍歷二叉樹(shù)是二叉樹(shù)各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹(shù)遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作。層次遍歷是按另一種搜索策略進(jìn)行的遍歷。178

4.理解二叉樹(shù)線(xiàn)索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟悉二叉樹(shù)的線(xiàn)索化過(guò)程以及在中序線(xiàn)索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。二叉樹(shù)的線(xiàn)索化過(guò)程是基于對(duì)二叉樹(shù)進(jìn)行遍歷，而線(xiàn)索二叉樹(shù)上的線(xiàn)索又為相應(yīng)的遍歷提供了方便。179

5.熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng)掌握1至2種建立二叉樹(shù)和樹(shù)的存儲(chǔ)結(jié)構(gòu)的方法。

6.學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法。

7.