第六樹(shù)和二叉樹(shù)

會(huì)計(jì)學(xué)1第六樹(shù)和二叉樹(shù)思考

你見(jiàn)過(guò)家族譜系圖嗎？試以圖形表示從你的祖父起的家族成員關(guān)系。侄兒伯父父親叔父堂兄堂姐自己堂弟祖父用關(guān)系表示的家族譜系圖<祖父，伯父>，<祖父，父親>，

<祖父，叔父>，<伯父，堂兄>，

<伯父，堂姐>，<父親，自己>，

<叔父，堂弟>，<堂兄，侄兒>第1頁(yè)/共110頁(yè)

樹(shù)型結(jié)構(gòu)是一類(lèi)重要的非線性結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)。第2頁(yè)/共110頁(yè)IndexRootChildernnode1中國(guó)河南2中國(guó)北京3中國(guó)廣東IndexRootChildernnode1北京通州2河南鄭州3河南開(kāi)封4廣東深圳5廣東廣州IndexRootChildernnode1深圳寶安區(qū)2深圳沙田區(qū)3鄭州金水區(qū)4鄭州二七區(qū)中國(guó)河南北京廣東開(kāi)封鄭州深圳廣州金水二七寶安沙田第3頁(yè)/共110頁(yè)樹(shù)的抽象數(shù)據(jù)類(lèi)型定義ADTTree{

數(shù)據(jù)對(duì)象：D是具有相同特性的數(shù)據(jù)元素的集合。

數(shù)據(jù)關(guān)系：

若D為空集，則稱(chēng)為空樹(shù)；

若D中僅含一個(gè)數(shù)據(jù)元素，則關(guān)系R為空集；

否則R={H}，

(1)在D中存在唯一的稱(chēng)為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；

(2)當(dāng)n>1時(shí)，其余數(shù)據(jù)元素可分為m(m>0)個(gè)互不相交的(非空)

有限集T1,T2,…,Tm,其中每一個(gè)子集本身又是一棵符合本定義的樹(shù)，稱(chēng)為根root的子樹(shù)，每一棵子樹(shù)的根xi都是根root

的后繼，即<root,xi>∈H,i=1,2,…,m第4頁(yè)/共110頁(yè)在這13個(gè)數(shù)據(jù)元素之間存在下列關(guān)系：R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,

<D,H>,<D,I>,<D,J>,<F,K>,<F,L>,<J,M>}第5頁(yè)/共110頁(yè)樹(shù)結(jié)構(gòu)的表現(xiàn)形式嵌套集合表示法凹入表表示法：類(lèi)似于目錄形式廣義表表示法：（A,(B,(C),(D),(E)),(F,(G),(H))）圖形表示法：ACDEFBGH第6頁(yè)/共110頁(yè)基本術(shù)語(yǔ)

分支：根和子樹(shù)根之間的連線

結(jié)點(diǎn)：一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支

結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)個(gè)數(shù)

葉子(終端結(jié)點(diǎn))：度為0的結(jié)點(diǎn)

非終端結(jié)點(diǎn)(分支結(jié)點(diǎn))：度不為0的結(jié)點(diǎn)

樹(shù)的度：樹(shù)內(nèi)各結(jié)點(diǎn)度的最大值

孩子：指結(jié)點(diǎn)的子樹(shù)的根,相應(yīng)的,該結(jié)點(diǎn)稱(chēng)為孩子的雙親

兄弟：同一雙親的孩子之間互稱(chēng)兄弟

祖先：一個(gè)結(jié)點(diǎn)的祖先指從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)

AIDBEHCFGKJ第7頁(yè)/共110頁(yè)子孫：以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱(chēng)為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)的層次：令根為第一層，根的孩子為第二層。若某結(jié)點(diǎn) 處在第l層，其子樹(shù)的根就在l+1層。堂兄弟：雙親在同一層的結(jié)點(diǎn)互稱(chēng)堂兄弟樹(shù)的深度：指樹(shù)中結(jié)點(diǎn)的最大層次有序樹(shù)：樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左至右有序（即不能互換）， 否則稱(chēng)為無(wú)序樹(shù)森林：指m(m≥0)棵互不相交的樹(shù)的集合AIDBEHCFGKJ第8頁(yè)/共110頁(yè)ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹(shù)的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹(shù)的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先第9頁(yè)/共110頁(yè)基本操作：

{結(jié)構(gòu)初始化}

InitTree(&T); //構(gòu)造空樹(shù)T

CreateTree(&T,definition); //按definition構(gòu)造樹(shù)T

{銷(xiāo)毀結(jié)構(gòu)}

DestroyTree(&T); //銷(xiāo)毀樹(shù)T

第10頁(yè)/共110頁(yè){引用型操作}TreeEmpty(T); //若T為空樹(shù)，則返回TRUE，否則返回FALSE

TreeDepth(T);//返回T的深度

Root(T);//返回T的根

Value(T,cur_e);//返回cur_e的值

Parent(T,cur_e);//若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則返回"空"。

LeftChild(T,cur_e);//若cur_e是T的非葉子結(jié)點(diǎn)，則返回它的最左孩子，否則返回"空"

RightSibling(T,cur_e);//若cur_e有右兄弟，則返回它的右兄弟，否則返回"空"

TraverseTree(T,visit());//按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦

//visit()失敗，則操作失敗。 第11頁(yè)/共110頁(yè){加工型操作}

Assign(T,cur_e,value); //結(jié)點(diǎn)cur_e賦值為value ClearTree(&T);

//將樹(shù)T清為空樹(shù)

InsertChild(&T,&p,i,c);

//插入c為T(mén)中p所指結(jié)點(diǎn)的第i棵子樹(shù)

DeleteChild(&T,&p,i); //刪除T中p所指結(jié)點(diǎn)的第i棵子樹(shù)}ADTTree

第12頁(yè)/共110頁(yè)線性結(jié)構(gòu)樹(shù)結(jié)構(gòu)存在唯一的沒(méi)有前驅(qū)的"首元素"存在唯一的沒(méi)有前驅(qū)的"根結(jié)點(diǎn)"存在唯一的沒(méi)有后繼的"尾元素"存在多個(gè)沒(méi)有后繼的"葉子"其余元素均存在唯一的"前驅(qū)元素"和唯一的"后繼元素"其余結(jié)點(diǎn)均存在唯一的"前驅(qū)(雙親)結(jié)點(diǎn)"和多個(gè)"后繼(孩子)結(jié)點(diǎn)"線性結(jié)構(gòu)和樹(shù)結(jié)構(gòu)中數(shù)據(jù)元素之間關(guān)系對(duì)比表第13頁(yè)/共110頁(yè)二叉樹(shù)的類(lèi)型定義ADTBinaryTree{

數(shù)據(jù)對(duì)象：D是具有相同特性的數(shù)據(jù)元素的集合。

數(shù)據(jù)關(guān)系：

若D為空集，稱(chēng)BinaryTree為空二叉樹(shù)；否則關(guān)系

R={H}：

(1)在D中存在唯一的稱(chēng)為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；

(2)D中其余元素必可分為兩個(gè)互不相交的子集L和

R，每一個(gè)子集都是一棵符合本定義的二叉樹(shù)，并分別為root的左子樹(shù)和右子樹(shù),如果左子樹(shù)L不空,則必存在一個(gè)根結(jié)點(diǎn)xl,它是root的”左后繼”,如果右子樹(shù)R

不空,則必存在一個(gè)根結(jié)點(diǎn)xr,它是root的”右后繼”第14頁(yè)/共110頁(yè)第15頁(yè)/共110頁(yè)基本操作P：{結(jié)構(gòu)初始化} InitBiTree(&T);//構(gòu)造空二叉樹(shù)T CreateBiTree(&T,definition); //按definition構(gòu)造二叉樹(shù)T{銷(xiāo)毀結(jié)構(gòu)} DestroyBiTree(&T);//銷(xiāo)毀二叉樹(shù)T

第16頁(yè)/共110頁(yè){引用型操作} BiTreeEmpty(T); BiTreeDepth(T); Root(T); Value(T,e); Parent(T,e); LeftChild(T,e);

RightChild(T,e); LeftSibling(T,e); RightSibling(T,e); PreOrderTraverse(T,visit()); //先序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗

InOrderTraverse(T,vsit()); //中序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗

PostOrderTraverse(T,visit()); //后序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗

LevelOrderTraverse(T,visit()); //層序遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗第17頁(yè)/共110頁(yè){加工型操作} ClearBiTree(&T);

//將二叉樹(shù)T清為空樹(shù)

Assign(&T,&e,value);

//結(jié)點(diǎn)e賦值為value InsertChild(&T,p,LR,c);

//根據(jù)LR為0或1，插入c為T(mén)中p所指結(jié)點(diǎn)的左或右

//子樹(shù)。p所指結(jié)點(diǎn)原有左或右子樹(shù)成為c的右子樹(shù)

DeleteChild(&T,p,LR); //根據(jù)LR為0或1，刪除T中p所指結(jié)點(diǎn)的左或右子樹(shù)}ADTBinaryTree第18頁(yè)/共110頁(yè)二叉樹(shù)和樹(shù)是兩種不同的樹(shù)型結(jié)構(gòu)，二叉樹(shù)不等同于度為2的有序樹(shù)。

Why?第19頁(yè)/共110頁(yè)具有三個(gè)結(jié)點(diǎn)的樹(shù)的棵數(shù)：ACBCBA具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)的棵數(shù)：ACBCBACBACBACBA第20頁(yè)/共110頁(yè)二叉樹(shù)的五種形態(tài)空樹(shù)，結(jié)點(diǎn)數(shù)為0單節(jié)點(diǎn)二叉樹(shù)，只有一個(gè)結(jié)點(diǎn)左子樹(shù)為空，右子樹(shù)不空右子樹(shù)為空，左子樹(shù)不空左右子樹(shù)均不空第21頁(yè)/共110頁(yè)二叉樹(shù)的幾個(gè)特性一、在二叉樹(shù)的第i層上至多有2i-1

個(gè)結(jié)點(diǎn)(i≥1)二、深度為k的二叉樹(shù)中至多含有2k-1個(gè)結(jié)點(diǎn)，

(k≥1)。三、對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為

n0，度為2的結(jié)點(diǎn)數(shù)為n2，則：

n0=n2+1

第22頁(yè)/共110頁(yè)證明：

由于二叉樹(shù)中只有三種結(jié)點(diǎn)，假設(shè)n1為二叉樹(shù)T

中度為1的結(jié)點(diǎn)數(shù)，則二叉樹(shù)中結(jié)點(diǎn)總數(shù)為

n=n0+n1+n2

①

再看二叉樹(shù)中的分支數(shù)目。除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，假設(shè)B為分支數(shù)，則

n=B+1。從另一角度看，這些分支是由度為1或2

的結(jié)點(diǎn)射出的，所以又有

B=n1+2n2

即n=n1+2n2+1②

綜合以上①和②兩個(gè)等式便可得到

n0=n2+1第23頁(yè)/共110頁(yè)思考：若一棵樹(shù)的度為4，其中，度為1的結(jié)點(diǎn)有4個(gè)，度為2的結(jié)點(diǎn)有2個(gè)，度為3的結(jié)點(diǎn)有1個(gè)，度為4的結(jié)點(diǎn)有1個(gè)，則該樹(shù)中葉子有多少個(gè)？第24頁(yè)/共110頁(yè)兩種特殊形式的二叉樹(shù)若二叉樹(shù)中所有的分支結(jié)點(diǎn)的度數(shù)都為2，且葉子結(jié)點(diǎn)都在同一層次上，則稱(chēng)這類(lèi)二叉樹(shù)為滿二叉樹(shù)。

對(duì)滿二叉樹(shù)從上到下從左到右進(jìn)行從1開(kāi)始的編號(hào)，則任意一棵二叉樹(shù)都可以和同深度的滿二叉樹(shù)對(duì)比

第25頁(yè)/共110頁(yè)假如一棵包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)中每個(gè)結(jié)點(diǎn)都可以和滿二叉樹(shù)中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)，則稱(chēng)這類(lèi)二叉樹(shù)為完全二叉樹(shù)。在滿二叉樹(shù)的最下層從右到左連續(xù)地刪除若干個(gè)結(jié)點(diǎn)所得到的二叉樹(shù)。顯然一棵深度為h的完全二叉樹(shù)中，前h-1層中的結(jié)點(diǎn)都是“滿”的。滿二叉樹(shù)本身也是完全二叉樹(shù)。第26頁(yè)/共110頁(yè)1231145891213671014151231145891267101234567123456第27頁(yè)/共110頁(yè)二叉樹(shù)的幾個(gè)特性四、具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為五、如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序從1

開(kāi)始編號(hào)，則對(duì)任一編號(hào)為i的結(jié)點(diǎn)(1≤i≤n)，有：

(1)如果i=1，則編號(hào)為i的結(jié)點(diǎn)是二叉樹(shù)的根；如果

i>1，則其雙親結(jié)點(diǎn)parent(i)的編號(hào)是

(2)如果2i>n，則編號(hào)為i的結(jié)點(diǎn)無(wú)左孩子（編號(hào)為i的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）；否則其左孩子結(jié)點(diǎn)lChild(i)的編號(hào)是2i。

(3)如果2i+1>n，則編號(hào)為i的結(jié)點(diǎn)無(wú)右孩子；否則其右孩子結(jié)點(diǎn)rChild(i)的編號(hào)是結(jié)點(diǎn)2i+1。第28頁(yè)/共110頁(yè)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)----順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹(shù)中的數(shù)據(jù)元素

二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)的定義如下：

constMAXSIZE=100;

//定義二叉樹(shù)中結(jié)點(diǎn)數(shù)的最大值為100

typedefstruct

{

ElemType*data;

//存儲(chǔ)空間基址(初始化時(shí)分配空間)

intnodeNum;

//二叉樹(shù)中結(jié)點(diǎn)數(shù)

}SqBiTree;

//二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)

SqBiTreebt;第29頁(yè)/共110頁(yè)為了能在存儲(chǔ)結(jié)構(gòu)中反映出結(jié)點(diǎn)之間的邏輯關(guān)系，必須將二叉樹(shù)中結(jié)點(diǎn)依照一定規(guī)律安排在這組存儲(chǔ)單元中。對(duì)于完全二叉樹(shù)，只要從根起按層序存儲(chǔ)即可。將完全二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為i-1的分量中

0123456789abcdefghij第30頁(yè)/共110頁(yè)根據(jù)二叉樹(shù)的特性五，可推出順序存儲(chǔ)結(jié)構(gòu)中“雙親”和“孩子”的關(guān)系：

假設(shè)bt.data[i]是完全二叉樹(shù)上的一個(gè)結(jié)點(diǎn)若2i+1<bt.nodeNum，則bt.data[2i+1]是它的左孩子，否則它的左子樹(shù)為空樹(shù)；若2i+2<bt.nodeNum，則bt.data[2i+2]是它的右孩子，否則它的右子樹(shù)為空樹(shù)。0123456789abcdefghij第31頁(yè)/共110頁(yè)對(duì)于一般的二叉樹(shù)，可對(duì)照完全二叉樹(shù)的編號(hào)進(jìn)行相應(yīng)的存儲(chǔ)，但在沒(méi)有結(jié)點(diǎn)的分量中需填充空白字符。為此，需要依據(jù)實(shí)際結(jié)點(diǎn)數(shù)來(lái)分配存儲(chǔ)空間，即采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。abcdefgabcde0000fg012345678910第32頁(yè)/共110頁(yè)二叉鏈表二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)：

LchilddataRchild二叉樹(shù)的二叉鏈表存儲(chǔ)表示

typedefstructBiTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指針

}BiTNode,*BiTree;

第33頁(yè)/共110頁(yè)整個(gè)二叉樹(shù)可用一個(gè)指向根結(jié)點(diǎn)的指針表示。第34頁(yè)/共110頁(yè)BiTreecreate_tree(){ BiTreeq[100]; BiTNode*s,*root=NULL; charch; intrear=0,front=1; ch=getchar(); while(ch!='#') { if(ch!=',') { s=(BiTNode*)malloc(sizeof(BiTNode)); s->data=ch; s->lchild=NULL; s->rchild=NULL; }elses=NULL; q[++rear]=s; if(rear==1) root=s;

else { if(rear%2==0)q[front]->lchild=s;else{q[front]->rchild=s;front++; } }ch=getchar(); }//whilereturnroot;}

第35頁(yè)/共110頁(yè)三叉鏈表三叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)：

parentLchilddataRchild二叉樹(shù)的三叉鏈表存儲(chǔ)表示

typedefstructTriTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指針

structBiTNode*parent;

//雙親指針

}TriTNode,*TriTree;

第36頁(yè)/共110頁(yè)第37頁(yè)/共110頁(yè)雙親鏈表雙親鏈表的結(jié)點(diǎn)結(jié)構(gòu)：

dataparentLRTag二叉樹(shù)的雙親鏈表存儲(chǔ)表示typedefstructBPTNode{

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

ElemTypedata;

int*parent;

//指向雙親的指針

charLRTag;

//左、右孩子標(biāo)志域

}BPTNode

typedefstructBPTree{

//樹(shù)結(jié)構(gòu)

BPTNode*nodes;

//初始化時(shí)分配存儲(chǔ)空間

intnodeNum;

//結(jié)點(diǎn)數(shù)目

introot;

//根結(jié)點(diǎn)的位置

}BPTree

第38頁(yè)/共110頁(yè)二叉樹(shù)的雙親鏈表建表過(guò)程constMAXSIZE=100;

//暫定二叉樹(shù)中結(jié)點(diǎn)數(shù)的最大值為100cin>>BT.nodeNum;

//輸入結(jié)點(diǎn)數(shù)目

BT.root=0;

cin>>BT.nodes[0].data;

//輸入根

BT.nodes[0].parent=-1;

//根的雙親為空

BT.nodes[0].LRTag=‘L’;

for(i=1;i<BT.nodeNum;i++)

{

cin>>BT.nodes[i].data>>F>>BT.nodes[i].LRtag;

k=i-1;

while(k>=0&&BT.nodes[k].data!=F)k--;//查詢雙親

if(k<0)returnFALSE;

//沒(méi)有找到雙親

BT.nodes[i].parent=k;

returnTRUE;

}第39頁(yè)/共110頁(yè)二叉樹(shù)的輸入數(shù)據(jù)為：

6,A,(B,A,L),(C,B,R),(D,A,R),(E,D,R),(F,E,L)

建立的雙親鏈表如下所示：第40頁(yè)/共110頁(yè)二叉樹(shù)的遍歷

“遍歷”的含義是對(duì)結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素都訪問(wèn)一次且僅僅訪問(wèn)一次。因此進(jìn)行遍歷應(yīng)該確定一條搜索路徑，使得結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素都出現(xiàn)在這條搜索路徑上，才能確保每個(gè)數(shù)據(jù)元素都被訪問(wèn)到。

二叉樹(shù)中每個(gè)結(jié)點(diǎn)都有兩個(gè)后繼，可以有三條搜索路徑：

1)先左(子樹(shù))后右(子樹(shù))；

2)先右(子樹(shù))后左(子樹(shù))；

3)按層次從上到下。

第41頁(yè)/共110頁(yè)先左后右的遍歷第一次走到根結(jié)點(diǎn)即“訪問(wèn)”為“先序遍歷”，從左子樹(shù)回來(lái)再“訪問(wèn)”為“中序遍歷”，從右子樹(shù)回來(lái)再"訪問(wèn)"為"后序遍歷"第42頁(yè)/共110頁(yè)根據(jù)對(duì)二叉樹(shù)進(jìn)行遍歷的先左后右的搜索路徑，可得以下三個(gè)遍歷二叉樹(shù)的算法先序遍歷二叉樹(shù)中序遍歷二叉樹(shù)后序遍歷二叉樹(shù)若二叉樹(shù)為空，則空操作；

否則

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

(2)先序遍歷左子樹(shù)

(3)先序遍歷右子樹(shù)若二叉樹(shù)為空，則空操作；

否則

(1)中序遍歷左子樹(shù)

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

(3)中序遍歷右子樹(shù)若二叉樹(shù)為空，則空操作；

否則

(1)后序遍歷左子樹(shù)

(2)后序遍歷右子樹(shù)

(3)訪問(wèn)根結(jié)點(diǎn)按照遍歷過(guò)程中先后訪問(wèn)的次序?qū)⒍鏄?shù)中的結(jié)點(diǎn)排列起來(lái)可分別得到二叉樹(shù)的先序序列、中序序列和后序序列。第43頁(yè)/共110頁(yè)voidPreOrder(BiTreeT，void(*visit)(BiTree))

{

//先序遍歷以T為根的二叉樹(shù)

if(T){ //T=NULL時(shí)，二叉樹(shù)為空樹(shù)，不做任何操作

visit(T);

//通過(guò)函數(shù)指針*visit訪問(wèn)根結(jié)點(diǎn)

Preorder(T->Lchild,visit); //先序遍歷左子樹(shù)

Preorder(T->Rchild,visit); //先序遍歷右子樹(shù)

}//if

}第44頁(yè)/共110頁(yè)voidInOrder(BiTreeT，void(*visit)(BiTree))

{

//中序遍歷以T為根的二叉樹(shù)

if(T){ //T=NULL時(shí)，二叉樹(shù)為空樹(shù)，不做任何操作

InOrder(T->Lchild,visit); //中序遍歷左子樹(shù)

visit(T);

//通過(guò)函數(shù)指針*visit訪問(wèn)根結(jié)點(diǎn)

InOrder(T->Rchild,visit); //中序遍歷右子樹(shù)

}//if

}第45頁(yè)/共110頁(yè)voidPostOrder(BiTreeT，void(*visit)(BiTree))

{

//后序遍歷以T為根的二叉樹(shù)

if(T){ //T=NULL時(shí)，二叉樹(shù)為空樹(shù)，不做任何操作

PostOrder(T->Lchild,visit); //先序遍歷左子樹(shù)

PostOrder(T->Rchild,visit); //先序遍歷右子樹(shù)

visit(T);

//通過(guò)函數(shù)指針*visit訪問(wèn)根結(jié)點(diǎn)

}//if

}第46頁(yè)/共110頁(yè)遍歷算法例題1假設(shè)訪問(wèn)二叉樹(shù)T的結(jié)點(diǎn)的操作是打印結(jié)點(diǎn)的值，請(qǐng)分別寫(xiě)出下圖所示的二叉樹(shù)的先序、中序和后序序列ACBDFGHEJIAABF

ABCDEFGHIJ

ALARFLBLBRFRFBALARBLBRFLFRALAR第47頁(yè)/共110頁(yè)-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef用二叉樹(shù)可以表示數(shù)學(xué)表達(dá)式，例如：

a+b*(c-d)-e/f表達(dá)式的前綴表示表達(dá)式的中綴表示表達(dá)式的后綴表示第48頁(yè)/共110頁(yè)遍歷算法例題2已知二叉樹(shù)的先序和中序序列如下，試構(gòu)造出相應(yīng)的二叉樹(shù)。先序：ABCDEFGHIJ

中序：CDBFEAIHGJ原理：先序序列的第一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)中序序列根結(jié)點(diǎn)處于左右子樹(shù)的中序序列之間注意：二叉樹(shù)的先序和后序序列不能唯一確定一棵二叉樹(shù)，但由先序和中序或后序和中序序列能唯一確定一棵二叉樹(shù)。先序：ABCDEFGHIJ中序：CDBFEAIHGJBCDEFCDBFEGHIJIHGJACDCDEFFEHIIHJJAGBAJECBFDGHI第49頁(yè)/共110頁(yè)非遞歸算法——中序遍歷BoolInOrder(BiTreeT,bool(*visit)(ElemTypee)){//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，中序遍歷二叉樹(shù)T的非遞歸算法

InitStack(S);Push(S,T);//根指針進(jìn)棧

while(!StackEmpty(S)){while(Gettop(S,p)&&p)Push(S,p->lchild);//找最左下結(jié)點(diǎn)

Pop(S,p);//空指針退棧

if(!StackEmpty(S)){Pop(S,p);visit(p->data);//訪問(wèn)結(jié)點(diǎn)

Push(S,p->rchild);//訪問(wèn)右子樹(shù)

}//if}//whilereturnOK;}//InOrder第50頁(yè)/共110頁(yè)非遞歸算法——先序遍歷BoolPreOrder(BiTreeT,bool(*visit)(ElemTypee)){//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，中序遍歷二叉樹(shù)T的非遞歸算法

InitStack(S);Push(S,T);//根指針進(jìn)棧

while(!StackEmpty(S)){Gettop(S,p)if(p){visit(p->data);//訪問(wèn)結(jié)點(diǎn)

Push(S,p->lchild);}else{Pop(S,p);//空指針退棧

if(!StackEmpty(S)){Pop(S,p);Push(S,p->rchild);//訪問(wèn)右子樹(shù)

}}//else}//whilereturnOK;}//InOrder第51頁(yè)/共110頁(yè)二叉樹(shù)算法舉例建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)--二叉鏈表設(shè)二叉樹(shù)中結(jié)點(diǎn)的元素均為一個(gè)單字符，并以“#”表示空樹(shù)。假設(shè)二叉樹(shù)以由“根”、“左子樹(shù)串”和“右子樹(shù)串“聯(lián)接而成的字符串表示，則建立二叉鏈表的算法應(yīng)該是一個(gè)“先序遍歷”的過(guò)程，并且遍歷過(guò)程中“訪問(wèn)”的操作應(yīng)是識(shí)別輸入的字符并作相應(yīng)操作

第52頁(yè)/共110頁(yè)例如，空樹(shù)以“#”表示，只有一個(gè)根結(jié)點(diǎn)A的二叉樹(shù)以"A##"表示，下列二叉樹(shù)則以"AB#CD###E#F##“表示。

第53頁(yè)/共110頁(yè)在輸入數(shù)據(jù)正確的前提下，由此建立二叉鏈表的算法為：

若輸入的字符是'#'，則建立空樹(shù)；

否則

建立根結(jié)點(diǎn)；

遞歸建立左子樹(shù)的二叉鏈表；

遞歸建立右子樹(shù)的二叉鏈表。

第54頁(yè)/共110頁(yè)voidCreateBiTree(BiTree&T)

{

//在先序遍歷二叉樹(shù)的過(guò)程中輸入二叉樹(shù)的“先序字符

//串”，建立根指針為T(mén)的二叉鏈表存儲(chǔ)結(jié)構(gòu)。在先序

//字符串中，字符‘#’表示空樹(shù)，其它字母字符為結(jié)點(diǎn)

//的數(shù)據(jù)元素

cin>>ch；

if(ch==‘#’)T=NULL;

//建空樹(shù)

else{

T=newBiTNode;

//“訪問(wèn)”操作為生成根結(jié)點(diǎn)

T->data=ch;

CreateBiTree(T->Lchild);

//遞歸建(遍歷)左子樹(shù)

CreateBiTree(T->Rchild);//遞歸建(遍歷)右子樹(shù)

}//else

}//CreateBiTree第55頁(yè)/共110頁(yè)

先序序列為：ABDEGHCFIJ

中序序列為：DBGEHACIJF

后序序列為：DGHEBJIFCA

第56頁(yè)/共110頁(yè)二叉樹(shù)的線索鏈表如果將在第一次遍歷過(guò)程中得到的前驅(qū)和后繼信息保存起來(lái)，那么在以后需要再次對(duì)二叉樹(shù)進(jìn)行“遍歷”時(shí)就可以將二叉樹(shù)視作線性結(jié)構(gòu)進(jìn)行訪問(wèn)操作第57頁(yè)/共110頁(yè)如何保存在遍歷過(guò)程中得到的前驅(qū)和后繼信息？最簡(jiǎn)單的辦法是在結(jié)點(diǎn)中增加兩個(gè)指針域分別指向該結(jié)點(diǎn)的前驅(qū)和后繼。一個(gè)含n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)鏈域的值為“NULL”，可以利用這些空的指針域存放指向前驅(qū)和后繼的信息，由此得到的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)稱(chēng)作“線索鏈表”，其中指向前驅(qū)或后繼的指針?lè)Q作"線索"。

第58頁(yè)/共110頁(yè)二叉樹(shù)的二叉線索鏈表存儲(chǔ)表示

typedefenumPointerType{Link=0,Thread=1};

//定義指針類(lèi)型，以Link表示指針，Thread表示線索

typedefstructBiThrNode{

ElemTypedata;

structBiThrNode*Lchild,*Rchild;

//左右指針

PointerTypeLTag,RTag;

//左右指針類(lèi)型標(biāo)志

}*BiThrTree;

第59頁(yè)/共110頁(yè)若結(jié)點(diǎn)的左指針類(lèi)型標(biāo)志為“Link”，則Lchild指向它的左子樹(shù)根結(jié)點(diǎn)，否則指向它的“前驅(qū)”；若結(jié)點(diǎn)的右指針類(lèi)型標(biāo)志為“Link”，則Rchild指向它的右子樹(shù)根結(jié)點(diǎn)，否則指向它的"后繼"。

第60頁(yè)/共110頁(yè)中序線索鏈表第61頁(yè)/共110頁(yè)在線索鏈表中添加了一個(gè)“頭結(jié)點(diǎn)”，頭結(jié)點(diǎn)的左指針指向二叉樹(shù)的根結(jié)點(diǎn)，其右線索指向中序序列中的最后一個(gè)結(jié)點(diǎn)，中序序列中的第一個(gè)結(jié)點(diǎn)的左線索和中序序列中的最后一個(gè)結(jié)點(diǎn)的右線索均指向頭結(jié)點(diǎn)。第62頁(yè)/共110頁(yè)以中序線索鏈表為存儲(chǔ)結(jié)構(gòu)的中序遍歷如何在中序線索鏈表上進(jìn)行遍歷，關(guān)鍵問(wèn)題有二：

一是如何找到訪問(wèn)的第一個(gè)結(jié)點(diǎn)？

二是如何找到每個(gè)結(jié)點(diǎn)在中序序列中的后繼？

第63頁(yè)/共110頁(yè)如何找到訪問(wèn)的第一個(gè)結(jié)點(diǎn)？中序遍歷訪問(wèn)的第一個(gè)結(jié)點(diǎn)必定是"其左子樹(shù)為空“的結(jié)點(diǎn)。若根結(jié)點(diǎn)沒(méi)有左子樹(shù)，則根結(jié)點(diǎn)即為中序遍歷訪問(wèn)的第一個(gè)結(jié)點(diǎn)，若根結(jié)點(diǎn)的左子樹(shù)不空，則訪問(wèn)的第一個(gè)結(jié)點(diǎn)應(yīng)該是其左子樹(shù)中“最左下的結(jié)點(diǎn)“，即從根結(jié)點(diǎn)出發(fā)，順指針Lchild找到其左子樹(shù)直至某個(gè)結(jié)點(diǎn)的指針Lchild為“線索”止，該結(jié)點(diǎn)必為中序序列中的第一個(gè)結(jié)點(diǎn)。第64頁(yè)/共110頁(yè)如何找到每個(gè)結(jié)點(diǎn)在中序序列中的后繼？

若結(jié)點(diǎn)沒(méi)有右子樹(shù)，即結(jié)點(diǎn)的右指針類(lèi)型標(biāo)志Rtag為“Thread”，則指針Rchild所指即為它的后繼若結(jié)點(diǎn)有右子樹(shù)，則它的后繼應(yīng)該是其右子樹(shù)中訪問(wèn)的第一個(gè)結(jié)點(diǎn)。和前面所述找二叉樹(shù)的第一個(gè)結(jié)點(diǎn)一樣，就應(yīng)該從它的右子樹(shù)根出發(fā)，順指針Lchild直至沒(méi)有左子樹(shù)的結(jié)點(diǎn)為止，該結(jié)點(diǎn)即為它的后繼。

第65頁(yè)/共110頁(yè)例如：找結(jié)點(diǎn)B的后繼。結(jié)點(diǎn)B的RTag=Link，則順指針Rchild找到它的右子樹(shù)根E，因?yàn)榻Y(jié)點(diǎn)E的LTag=Link，則順指針Lchild找到它的左子樹(shù)根G，因?yàn)榻Y(jié)點(diǎn)G的Ltag=Thread，說(shuō)明G是結(jié)點(diǎn)B的右子樹(shù)中“最左下”的結(jié)點(diǎn)，所以結(jié)點(diǎn)G是結(jié)點(diǎn)B的后繼。第66頁(yè)/共110頁(yè)voidInOrderTraverse_Thr(BiThrTreeThead,void(*Visit)(ElemTypee))

{

//Thead指向中序線索鏈表中的頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左指針Lchild

//指向二叉樹(shù)的根結(jié)點(diǎn)，頭結(jié)點(diǎn)的右線索Rchild指向中序遍歷

//訪問(wèn)的最后一個(gè)結(jié)點(diǎn)。本算法對(duì)此二叉樹(shù)進(jìn)行中序遍歷，對(duì)

//樹(shù)中每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit進(jìn)行訪問(wèn)操作

p=Thead->Lchild;

//p指向二叉樹(shù)的根結(jié)點(diǎn)

while(p!=Thead){

//空樹(shù)或遍歷結(jié)束時(shí)，p==Thead

while(p->LTag==Link)p=p->Lchild;

Visit(p->data);

//訪問(wèn)其左子樹(shù)為空的結(jié)點(diǎn)

while(p->RTag==Thread&&p->Rchild!=Thread){

p=p->rchild;Visit(p->data);

//訪問(wèn)"右線索"所指后繼結(jié)點(diǎn)

}//while

p=p->Rchild;

//p進(jìn)至其右子樹(shù)根

}//while

}//InOrderTraverse_Thr第67頁(yè)/共110頁(yè)線索鏈表的生成由于線索鏈表上保存的是“遍歷”過(guò)程中得到的前驅(qū)和后繼的信息，顯然，線索鏈表應(yīng)該在遍歷過(guò)程中建立，即在遍歷過(guò)程中改變二叉鏈表中結(jié)點(diǎn)的“空指針“以及相應(yīng)的”指針類(lèi)型標(biāo)志“。若結(jié)點(diǎn)沒(méi)有左子樹(shù)，則令其左指針指向它的“前驅(qū)“并將左指針類(lèi)型標(biāo)志改為“Thread”，若結(jié)點(diǎn)沒(méi)有右子樹(shù)，則令它的右指針指向它的“后繼”并將右指針類(lèi)型標(biāo)志改為“Thread”。為了獲取“前驅(qū)”的信息，需要在遍歷過(guò)程中添加一個(gè)指向其前驅(qū)的指針pre。

第68頁(yè)/共110頁(yè)建立線索鏈表的過(guò)程即為將遍歷過(guò)程中對(duì)結(jié)點(diǎn)進(jìn)行下列"訪問(wèn)"操作(指針p指向當(dāng)前訪問(wèn)的結(jié)點(diǎn)，pre指向在它之前“剛剛”訪問(wèn)過(guò)的結(jié)點(diǎn))：

if(!pre->Rchild){

pre->RTag=Thread;

pre->Rchild=p;

}

if(!p->Lchild){

p->LTag=Thread;

p->Lchild=pre;

}

pre=p;第69頁(yè)/共110頁(yè)voidInThreading(BiThrTreep，BiThrTree&pre)

{

//對(duì)p指向根結(jié)點(diǎn)的二叉樹(shù)進(jìn)行中序遍歷，遍歷過(guò)程中進(jìn)行“中序線索

//化”。若p所指結(jié)點(diǎn)的左指針為空，則將它改為“左線索”，若pre

//所指結(jié)點(diǎn)的右指針為空，則將它改為“右線索”。指針pre在遍歷

//過(guò)程中緊隨其后，即始終指向p所指結(jié)點(diǎn)在中序序列中的前驅(qū)。

if(p){

InThreading(p->Lchild,pre);

//對(duì)左子樹(shù)進(jìn)行線索化

if(!p->Lchild)

{p->LTag=Thread;p->Lchild=pre;}

//建前驅(qū)線索

if(!pre->Rchild)

{pre->RTag=Thread;pre->Rchild=p;}//建后繼線索

pre=p;

//保持pre指向p的前驅(qū)

InThreading(p->Rchild,pre);

//對(duì)右子樹(shù)進(jìn)行線索化

}//if

}//InThreading第70頁(yè)/共110頁(yè)voidInOrderThreading(BiThrTree&Thead,BiThrTreeBT)

{

//BT為指向二叉樹(shù)根結(jié)點(diǎn)的指針，由此二叉鏈表建立二叉樹(shù)

//的中序線索鏈表，Thead指向線索鏈表中的頭結(jié)點(diǎn)。

BiThrTreepre;

if(!(Thead=newBiThrNode))exit(1);//存儲(chǔ)分配失敗

Thead->LTag=Link;Thead->RTag=Thread;

//建頭結(jié)點(diǎn)

Thead->Rchild=Thead;

//右指針回指

if(!BT)Thead->Lchild=Thead;

//若二叉樹(shù)空，則左指針回指

else{

Thead->Lchild=BT;pre=Thead;

InThreading(BT,pre);

//中序遍歷進(jìn)行中序線索化

pre->Rchild=Thead;pre->RTag=Thead;

//對(duì)中序序列中最后一個(gè)結(jié)點(diǎn)進(jìn)行線索化

Thead->Rchild=pre;

//建非空樹(shù)的頭結(jié)點(diǎn)的"右線索"

}//else

}//InOrderThreading第71頁(yè)/共110頁(yè)樹(shù)的存儲(chǔ)結(jié)構(gòu)——樹(shù)的雙親表示法樹(shù)的雙親鏈表存儲(chǔ)表示

constMAX_TREE_SIZE=100;

typedefstruct{

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

ElemTypedata;

intparent;

//雙親位置域

}PTNode;

typedefstruct{

//樹(shù)結(jié)構(gòu)

PTNodenodes[MAX_TREE_SIZE];

intr,n;

//根的位置和結(jié)點(diǎn)數(shù)

}PTree;

第72頁(yè)/共110頁(yè)A-1B0E1H2I2J2C0D0F7G7K9該樹(shù)的雙親鏈表如下所示

01532648710911第73頁(yè)/共110頁(yè)樹(shù)的孩子表示法讓每個(gè)結(jié)點(diǎn)的“子樹(shù)根”構(gòu)成一個(gè)線性表，以鏈表作它的存儲(chǔ)結(jié)構(gòu)，令其頭指針和結(jié)點(diǎn)的數(shù)據(jù)元素構(gòu)成一個(gè)結(jié)點(diǎn)，并將所有這樣的結(jié)點(diǎn)存放在一個(gè)地址連續(xù)的存儲(chǔ)空間里，所構(gòu)成的樹(shù)的存儲(chǔ)結(jié)構(gòu)稱(chēng)為樹(shù)的孩子鏈表。第74頁(yè)/共110頁(yè)樹(shù)的孩子鏈表存儲(chǔ)表示

typedefstructCTNode{

//孩子結(jié)點(diǎn)

intchild;

structCTNode*next;

}*ChildPtr;

typedefstruct{

ElemTypedata;

//結(jié)點(diǎn)的數(shù)據(jù)元素

ChildPtrfirstchild;

//孩子鏈表頭指針

}CTBox;

typedefstruct{

CTBoxnodes[MAX_TREE_SIZE];

intn,r;

//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置

}CTree;第75頁(yè)/共110頁(yè)第76頁(yè)/共110頁(yè)樹(shù)和森林的孩子兄弟表示法樹(shù)和森林的二叉鏈表(孩子-兄弟）存儲(chǔ)表示

typedefstructCSNode{

ElemTypedata;

structCSNode*firstchild,*nextsibling;

}CSNode,*CSTree;

樹(shù)中每個(gè)結(jié)點(diǎn)都設(shè)有兩個(gè)指針：

firstchild：指向該結(jié)點(diǎn)的“第一個(gè)”子樹(shù)根結(jié)點(diǎn)

nextsibling：指向它的"下一個(gè)"兄弟結(jié)點(diǎn)

第77頁(yè)/共110頁(yè)第78頁(yè)/共110頁(yè)可將上圖所示的二叉鏈表看成是下列二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)由此，通過(guò)存儲(chǔ)結(jié)構(gòu)的一致性作為“媒介”，可建立森林和二叉樹(shù)之間一一對(duì)應(yīng)的關(guān)系

第79頁(yè)/共110頁(yè)森林和二叉樹(shù)的轉(zhuǎn)換假設(shè)森林

F={T1,T2,…,Tn}可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹(shù)

B=(LBT,Node(root),RBT)

若森林F為空集，則二叉樹(shù)B為空樹(shù)；否則，由森林中第一棵樹(shù)的根結(jié)點(diǎn)ROOT(T1)復(fù)制得二叉樹(shù)的根Node(root)，由森林中第一棵樹(shù)的子樹(shù)森林轉(zhuǎn)換得到二叉樹(shù)中的左子樹(shù)LBT，由森林中刪去第一棵樹(shù)之后由其余樹(shù)構(gòu)成的森林{T2,T3,…,Tn}轉(zhuǎn)換得到二叉樹(shù)中的右子樹(shù)RBT第80頁(yè)/共110頁(yè)第81頁(yè)/共110頁(yè)反之，對(duì)于任意一棵二叉樹(shù)B=(LBT,Node(root),RBT)可轉(zhuǎn)換得到由n棵樹(shù)構(gòu)成的森林F={T1,T2,…,Tn}

若二叉樹(shù)B為空樹(shù),則與其對(duì)應(yīng)的森林F為空集；否則，由二叉樹(shù)的根結(jié)點(diǎn)Node(root)復(fù)制得森林中第一棵樹(shù)的根結(jié)點(diǎn)ROOT(T1)，由二叉樹(shù)中的左子樹(shù)LBT轉(zhuǎn)換構(gòu)造森林中第一棵樹(shù)的子樹(shù)森林，由二叉樹(shù)中的右子樹(shù)RBT轉(zhuǎn)換構(gòu)造森林中其余樹(shù)構(gòu)成的森林{T2,T3,…,Tn}第82頁(yè)/共110頁(yè)樹(shù)的遍歷樹(shù)的遍歷：從根結(jié)點(diǎn)出發(fā)，對(duì)樹(shù)中各個(gè)結(jié)點(diǎn)進(jìn)行一次且僅進(jìn)行一次訪問(wèn)對(duì)樹(shù)進(jìn)行遍歷可有兩條搜索路徑：一條是從左到右；另一條是按層次從上到下

第83頁(yè)/共110頁(yè)對(duì)樹(shù)進(jìn)行從左到右遍歷的過(guò)程中要途徑根結(jié)點(diǎn)兩次，由對(duì)根的訪問(wèn)時(shí)機(jī)不同可得下列兩個(gè)算法：

一、先根(次序)遍歷樹(shù)

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

二、后根(次序)遍歷樹(shù)若樹(shù)不空，則先依次從左到右后根遍歷根的各棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)；HIJEBCFKGDA

第84頁(yè)/共110頁(yè)森林的遍歷一、先序遍歷森林

若森林不空，則可依下列次序進(jìn)行遍歷

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

(2)先序遍歷第一棵樹(shù)中的子樹(shù)森林；

(3)先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。

第85頁(yè)/共110頁(yè)二、中序遍歷森林

若森林不空，則可依下列次序進(jìn)行遍歷：

(1)中序遍歷第一棵樹(shù)中的子樹(shù)森林；

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

(3)中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。

第86頁(yè)/共110頁(yè)容易看出，樹(shù)的先根遍歷即森林的先序遍歷可對(duì)應(yīng)到二叉樹(shù)的先序遍歷，樹(shù)的后根遍歷即森林的中序遍歷可對(duì)應(yīng)到二叉樹(shù)的中序遍歷。

第87頁(yè)/共110頁(yè)最優(yōu)樹(shù)和赫夫曼編碼最優(yōu)樹(shù)：又稱(chēng)赫夫曼樹(shù)（HuffmanTree）是一類(lèi)帶權(quán)路徑長(zhǎng)度最短的樹(shù)路徑：從樹(shù)的根結(jié)點(diǎn)到其余結(jié)點(diǎn)的分支構(gòu)成的一條路徑路徑長(zhǎng)度：路徑上的分支數(shù)目樹(shù)的路徑長(zhǎng)度：指的是從樹(shù)根到樹(shù)中其余每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從樹(shù)根到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上所帶權(quán)值的乘積第88頁(yè)/共110頁(yè)樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和假設(shè)樹(shù)上有n個(gè)葉子結(jié)點(diǎn)，且每個(gè)葉子結(jié)點(diǎn)上帶有權(quán)值為wk(k=1,2,…,n)，則樹(shù)的帶權(quán)路徑長(zhǎng)度為

其中l(wèi)k為帶權(quán)wk的葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度

第89頁(yè)/共110頁(yè)

假設(shè)有n個(gè)權(quán)值{w1，w2，…wn}，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為

wi。顯然，這樣的二叉樹(shù)可以構(gòu)造出多棵，其中必存在一棵帶權(quán)路徑長(zhǎng)度WPL取最小的二叉樹(shù)，稱(chēng)該二叉樹(shù)為最優(yōu)二叉樹(shù)。

第90頁(yè)/共110頁(yè)右圖中的四棵二叉樹(shù)，都有5個(gè)葉子結(jié)點(diǎn)且?guī)嗤瑱?quán)值5、6、2、9、7，它們的帶權(quán)路徑長(zhǎng)度分別為

WPL=7×3+9×3+5×2+6×2+2×2=74

WPL=2×1+6×3+7×4+9×4+5×2=94

WPL=6×2+7×2+5×3+2×3+9×2=65

WPL=2×1+5×3+7×3+9×3+6×3=83

第91頁(yè)/共110頁(yè)最優(yōu)樹(shù)的構(gòu)造方法赫夫曼最早給出了一個(gè)構(gòu)造最優(yōu)樹(shù)的帶有一般規(guī)律的算法，俗稱(chēng)赫夫曼算法根據(jù)給定的n個(gè)權(quán)值{w1,w2,…wn}，構(gòu)成n棵二叉樹(shù)的集合F={T1,T2,…,Tn}，其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹(shù)均空。在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。在F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F中

重復(fù)(2)和(3)，直到F只含一棵樹(shù)為止。這棵樹(shù)便是所求的赫夫曼樹(shù)。第92頁(yè)/共110頁(yè)最優(yōu)前綴編碼赫夫曼二叉樹(shù)在通訊編碼中的一個(gè)應(yīng)用是利用它構(gòu)造一組最優(yōu)前綴編碼。在某些通訊場(chǎng)合，需將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符組成的字符串第93頁(yè)/共110頁(yè)

例如，假設(shè)需傳送的電文為“ABACCDA”，它只有

A、B、C和D四種字符，可設(shè)它們的編碼分別為

00、01、10和11，則上述七個(gè)字符的電文便為“000100101100”，總長(zhǎng)14位。顯然這樣的等長(zhǎng)編碼便于譯碼，對(duì)方接收時(shí)，可按兩位一分進(jìn)行譯碼。

第94頁(yè)/共110頁(yè)通常有兩類(lèi)二進(jìn)制編碼：一類(lèi)為等長(zhǎng)編碼，這類(lèi)編碼的二進(jìn)制串的長(zhǎng)度取決于電文中不同的字符個(gè)數(shù)，假設(shè)需傳送的電文中只有四種字符，只需兩位字符的串便可分辨，但如果電文中可能出現(xiàn)26種不同字符，則等長(zhǎng)編碼串的長(zhǎng)度為5。另一類(lèi)是