工程數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)Page22024/2/3第六章樹(shù)和二叉樹(shù)學(xué)習(xí)目標(biāo)領(lǐng)會(huì)樹(shù)和二叉樹(shù)的類(lèi)型定義，理解樹(shù)和二叉樹(shù)的結(jié)構(gòu)差別。熟記二叉樹(shù)的主要特性，并掌握它們的證明方法。熟練掌握二叉樹(shù)的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作。理解二叉樹(shù)的線(xiàn)索化過(guò)程以及在中序線(xiàn)索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。熟練掌握二叉樹(shù)和樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法。學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法。了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和赫夫曼編碼的方法。Page32024/2/3重點(diǎn)和難點(diǎn)重點(diǎn)：二叉樹(shù)和樹(shù)的遍歷及其應(yīng)用。難點(diǎn)：編寫(xiě)實(shí)現(xiàn)二叉樹(shù)和樹(shù)的各種操作的遞歸算法。知識(shí)點(diǎn)樹(shù)的類(lèi)型定義、二叉樹(shù)的類(lèi)型定義二叉樹(shù)的存儲(chǔ)表示二叉樹(shù)的遍歷以及其它操作的實(shí)現(xiàn)線(xiàn)索二叉樹(shù)樹(shù)和森林的存儲(chǔ)表示樹(shù)和森林的遍歷以及其它操作的實(shí)現(xiàn)最優(yōu)樹(shù)和赫夫曼編碼Page42024/2/3樹(shù)型結(jié)構(gòu)是一類(lèi)非常重要的非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。Page52024/2/36.1樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)(tree)是n(n

0)個(gè)結(jié)點(diǎn)的有限集T；在任意一棵非空樹(shù)中，有且僅有一個(gè)特定的結(jié)點(diǎn)，稱(chēng)為樹(shù)的根(root)；當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,……Tm，其中每一個(gè)集合本身又是一棵樹(shù)，稱(chēng)為根的子樹(shù)(subtree)。特點(diǎn)：非空樹(shù)中至少有一個(gè)結(jié)點(diǎn)——根；樹(shù)中各子樹(shù)是互不相交的集合。Page62024/2/3AABCDEFGHIJKLM只有根結(jié)點(diǎn)的樹(shù)有子樹(shù)的樹(shù)根子樹(shù)Page72024/2/3樹(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為空集； 若D中含多于一個(gè)數(shù)據(jù)元素，則R={H}，H是如下二元關(guān)系：

(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。Page82024/2/3基本操作：

InitTree(&T);

操作結(jié)果：構(gòu)造空樹(shù)T。

CreateTree(&T,definition);

初始條件：definition給出樹(shù)T的定義。

操作結(jié)果：按definition構(gòu)造樹(shù)T。

DestroyTree(&T);

初始條件：樹(shù)T存在。

操作結(jié)果：銷(xiāo)毀樹(shù)T。

TreeEmpty(T);

初始條件：樹(shù)T存在。

操作結(jié)果：若T為空樹(shù)，則返回TRUE，否則返回FALSE。Page92024/2/3

TreeDepth(T);

初始條件：樹(shù)T存在。

操作結(jié)果：返回T的深度。

Root(T);

初始條件：樹(shù)T存在。

操作結(jié)果：返回T的根。

Value(T,cur_e);

初始條件：樹(shù)T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回cur_e的值。Page102024/2/3

Parent(T,cur_e);

初始條件：樹(shù)T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親，

否則返回“空”。

LeftChild(T,cur_e);

初始條件：樹(shù)T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur_e是T的非葉子結(jié)點(diǎn)，則返回它的最左

孩子，否則返回“空”。

RightSibling(T,cur_e);

初始條件：樹(shù)T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則

返回“空”。 Page112024/2/3

TraverseTree(T,visit());

初始條件：樹(shù)T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()

一次且至多一次。一旦visit()失敗，則操作

失敗。

Assign(T,cur_e,value);

初始條件：樹(shù)T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：結(jié)點(diǎn)cur_e賦值為value。

ClearTree(&T);

初始條件：樹(shù)T存在。

操作結(jié)果：將樹(shù)T清為空樹(shù)。Page122024/2/3

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

初始條件：樹(shù)T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p所

指結(jié)點(diǎn)的度＋1，非空樹(shù)c與T不相交。

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

DeleteChild(&T,&p,i);

初始條件：樹(shù)T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p

指結(jié)點(diǎn)的度。

操作結(jié)果：刪除T中p所指結(jié)點(diǎn)的第i棵子樹(shù)。}ADTTreePage132024/2/3基本術(shù)語(yǔ)結(jié)點(diǎn)(node)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支。結(jié)點(diǎn)的度(degree)：結(jié)點(diǎn)擁有的子樹(shù)數(shù)。葉子(leaf)：度為0的結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。樹(shù)的度：一棵樹(shù)中各結(jié)點(diǎn)的度的最大值。孩子(child)：結(jié)點(diǎn)的子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子。雙親(parents)：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)。兄弟(sibling)：同一雙親的孩子之間互稱(chēng)為兄弟。祖先：從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。子孫：以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱(chēng)為該結(jié)點(diǎn)的子孫。Page142024/2/3結(jié)點(diǎn)的層次(level)：從根結(jié)點(diǎn)算起，根為第一層，根的孩子為

第二層……。堂兄弟：其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。深度(depth)：樹(shù)中結(jié)點(diǎn)的最大層次。有序樹(shù)：將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左至右是有次序的，即不能

互換。無(wú)序樹(shù)：將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左至右是無(wú)次序的，即可以

互換。森林(forest)：m(m

0)棵互不相交的樹(shù)的集合。Page152024/2/3ABCDEFGHIJKLM結(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)A是結(jié)點(diǎn)F，G的祖先結(jié)點(diǎn)F，G為堂兄弟Page162024/2/3樹(shù)的表示方法樹(shù)形表示法：自然界倒長(zhǎng)的樹(shù)；文氏表示法：用集合表示；凹入表示法：類(lèi)似書(shū)目；嵌套括號(hào)表示法：廣義表表示法。樹(shù)形文氏ABDCG凹入ABCDG嵌套括號(hào)(A(B,C(G),D))Page172024/2/3樹(shù)和線(xiàn)性結(jié)構(gòu)對(duì)照線(xiàn)性結(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)"Page182024/2/36·2二叉樹(shù)二叉樹(shù)的定義是n(n>=0)個(gè)結(jié)點(diǎn)的有限集，其子樹(shù)分為互不相交的兩個(gè)集合，分別稱(chēng)為左子樹(shù)和右子樹(shù)，左子樹(shù)和右子樹(shù)也是二叉樹(shù)。ABCDEIJGH根結(jié)點(diǎn)左子樹(shù)右子樹(shù)Page192024/2/3二叉樹(shù)不是樹(shù)的特例。特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)(即不存在度大于2的結(jié)點(diǎn))；二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任意顛倒?；拘螒B(tài)A

ABABABC空二叉樹(shù)只有根結(jié)點(diǎn)的二叉樹(shù)右子樹(shù)為空左子樹(shù)為空左、右子樹(shù)均非空Page202024/2/3二叉樹(shù)的性質(zhì)性質(zhì)1：在二叉樹(shù)的第i層至多有2i-1個(gè)結(jié)點(diǎn)(i1)。性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)。性質(zhì)3：對(duì)于任何一棵二叉樹(shù)T，若其終端結(jié)點(diǎn)(葉子)數(shù)為

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

則n0=n2+1。Page212024/2/3幾種特殊形式的二叉樹(shù)滿(mǎn)二叉樹(shù)深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。特點(diǎn)每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)；所有的分支結(jié)點(diǎn)的度數(shù)都為2；葉子結(jié)點(diǎn)都在同一層次上。123114589121367101415Page222024/2/3完全二叉樹(shù)若對(duì)滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)從上到下從左至右進(jìn)行編號(hào)，則深度為k且有n個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為完全二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)的編號(hào)從1到n一一對(duì)應(yīng)時(shí)。特點(diǎn)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；前k-1層中的結(jié)點(diǎn)都是“滿(mǎn)”的，且第k層的結(jié)點(diǎn)都集中在左邊。123114589126710Page232024/2/3判斷是否為完全二叉樹(shù)，說(shuō)明理由。1234567123456思考：滿(mǎn)二叉樹(shù)與完全二叉樹(shù)的關(guān)系？Page242024/2/3性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是

log2n

+1。性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序

編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1in)，有：如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i>1，則其雙親是

i/2；如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子；如果2in，則其左孩子是2i；如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子；如果2i+1n，則其右孩子是2i+1。Page252024/2/3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹(shù)中的數(shù)據(jù)元素。完全二叉樹(shù)，只要從根起按層序存儲(chǔ)即可。將完全二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為i-1的分量中。一般的二叉樹(shù)，可對(duì)照完全二叉樹(shù)的編號(hào)進(jìn)行相應(yīng)的存儲(chǔ)，但在沒(méi)有結(jié)點(diǎn)的分量中需填充空白字符(例如填充0)。順序存儲(chǔ)表示

#defineMAX_TREE_SIZE100 //最大結(jié)點(diǎn)數(shù)

Typedef TElemTypeSqBiTree[MAX_TREE_SIZE]; //0號(hào)根結(jié)點(diǎn)

SqBiTreebt;Page262024/2/3深度為4，有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的順序存儲(chǔ)123451011678912111210987654321123456789101112沒(méi)有浪費(fèi)Page272024/2/3深度為4，有7個(gè)結(jié)點(diǎn)的一般二叉樹(shù)的順序存儲(chǔ)abcdefggf0000edcba1234567891011浪費(fèi)4個(gè)Page282024/2/3深度為4，只有4個(gè)右孩子的二叉樹(shù)的順序存儲(chǔ)0000400030002011234123456789101112131415浪費(fèi)11個(gè)Page292024/2/3順序存儲(chǔ)結(jié)構(gòu)適用于滿(mǎn)二叉樹(shù)和完全二叉樹(shù)的存儲(chǔ)。Page302024/2/3鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表結(jié)點(diǎn)除包括元素自身的信息外，還包括指向其左、右子樹(shù)的指針。即結(jié)點(diǎn)要包括數(shù)據(jù)域，左子樹(shù)指針域和右子樹(shù)指針域。

二叉鏈表的存儲(chǔ)表示

typedefstructBiTNode{

TElemTypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*Bitree;lchilddatarchildPage312024/2/3ABCDEFGABCDEFG^^^^^^^^在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域。Page322024/2/3三叉鏈表結(jié)點(diǎn)包括數(shù)據(jù)域，左子樹(shù)指針域、雙親域和右子樹(shù)指針域。lchilddataparentrchild三叉鏈表的存儲(chǔ)表示

typedefstructTriTNode{

TElemTypedata;

structTriTNode*lchild,*rchild,*parent;

}TriTNode,*Tritree;Page332024/2/3ABC

DEFG^^^^^^^^^ABCDEFGPage342024/2/36.3遍歷二叉樹(shù)和線(xiàn)索二叉樹(shù)

遍歷是樹(shù)結(jié)構(gòu)的一種常用的、重要的運(yùn)算，是樹(shù)的其它運(yùn)算的基礎(chǔ)。Page352024/2/3遍歷按一定的規(guī)律，走遍二叉樹(shù)的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪(fǎng)問(wèn)一次，且只被訪(fǎng)問(wèn)一次。遍歷方式按根、左子樹(shù)、右子樹(shù)三個(gè)部分進(jìn)行訪(fǎng)問(wèn)；按層次訪(fǎng)問(wèn)；

遍歷的過(guò)程就是把非線(xiàn)性結(jié)構(gòu)的二叉樹(shù)中的結(jié)點(diǎn)排成一個(gè)線(xiàn)性序列的過(guò)程。Page362024/2/3按根、左子樹(shù)、右子樹(shù)三個(gè)部分進(jìn)行訪(fǎng)問(wèn)設(shè)D表示根結(jié)點(diǎn)，L表示左子樹(shù)，R表示右子樹(shù)，則對(duì)這三個(gè)部分進(jìn)行訪(fǎng)問(wèn)的組合共有6種，DLRDRLLDRLRDRDLRLD若限定先左后右，則只有DLR，LDR，LRD三種，分別稱(chēng)為先序遍歷，中序遍歷，后序遍歷。Page372024/2/3先序遍歷若二叉樹(shù)為空，則空操作；否則訪(fǎng)問(wèn)根結(jié)點(diǎn)：先序遍歷左子樹(shù)；先序遍歷右子樹(shù)。Page382024/2/3ADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDCPage392024/2/3算法6.1先序遍歷的遞歸算法StatusPreOrderTraverse(BiTreeT，Status(*visit)(TElemTypee)){

//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)元素操作的應(yīng)用函數(shù)，

//先序遍歷二叉樹(shù)T的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。

//最簡(jiǎn)單的visit函數(shù)是輸出元素的值。

if(T){

visit(T->data)；

PreOrderTraverse(T->lchild,visit)；

PreOrderTraverse(T->rchild,visit);}//if}//PreOrderTraversePage402024/2/3ABCDGEFH先序遍歷：ABDGCEFHPage412024/2/3中序遍歷若二叉樹(shù)為空，則空操作；否則中序遍歷左子樹(shù)；訪(fǎng)問(wèn)根結(jié)點(diǎn)；中序遍歷右子樹(shù)。Page422024/2/3ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDACPage432024/2/3中序遍歷的遞歸算法StatusInOrderTraverse(BiTreeT，Status(*visit)(TElemTypee)){

//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)元素操作的應(yīng)用函數(shù)，

//中序遍歷二叉樹(shù)T的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。

//最簡(jiǎn)單的visit函數(shù)是輸出元素的值。

if(T){

InOrderTraverse(T->lchild,visit)；

visit(T->data)；

InOrderTraverse(T->rchild,visit)；

}//if}//InOrderTraversePage442024/2/3DGBAECH中序遍歷：ABCDGEFHFPage452024/2/3后序遍歷若二叉樹(shù)為空，則空操作；否則后序遍歷左子樹(shù)；后序遍歷右子樹(shù)；訪(fǎng)問(wèn)根結(jié)點(diǎn)。Page462024/2/3ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCABPage472024/2/3ABCDGEFH后序遍歷：CGFDHBEAPage482024/2/3后序遍歷的遞歸算法StatusPostOrderTraverse(BiTreeT，Status(*visit)(TElemTypee)){

//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)元素操作的應(yīng)用函數(shù)，

//先序遍歷二叉樹(shù)T的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。

//最簡(jiǎn)單的visit函數(shù)是輸出元素的值。

if(T){

PostOrderTraverse(T->lchild,visit);PostOrderTraverse(T->rchild,visit); visit(T->data);}//if}//InOrderTraversePage492024/2/3三種遍歷算法的比較相同點(diǎn)：如果把訪(fǎng)問(wèn)根結(jié)點(diǎn)這個(gè)不涉及遞歸的語(yǔ)句拋開(kāi)，則三個(gè)遞歸算法走過(guò)的路線(xiàn)是一樣的。Page502024/2/3三種遍歷算法的比較不同點(diǎn)：前序遍歷是每進(jìn)入一層遞

歸調(diào)用時(shí)先訪(fǎng)問(wèn)根結(jié)點(diǎn)，

然后再依次向它的左、右

子樹(shù)執(zhí)行遞歸調(diào)用；中序遍歷是在執(zhí)行完左子

樹(shù)遞歸調(diào)用后再訪(fǎng)問(wèn)根結(jié)

點(diǎn)，然后向它的右子樹(shù)遞

歸調(diào)用；后序遍歷則是在從右子樹(shù)

遞歸調(diào)用退出后訪(fǎng)問(wèn)根結(jié)

點(diǎn)。Page512024/2/3實(shí)例1：統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)算法思想：對(duì)二叉樹(shù)“遍歷”一遍，并在遍歷過(guò)程中對(duì)“葉子結(jié)點(diǎn)計(jì)數(shù)”

即可。為了在遍歷的同時(shí)進(jìn)行計(jì)數(shù)，在算法的參數(shù)中設(shè)

一個(gè)“計(jì)數(shù)器”。這個(gè)遍歷的次序可以隨意，即先序或中

序或后序均可。voidCountLeaf(BiTreeT,int&count){

//先序遍歷二叉樹(shù)，以count返回二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目

if(T){if((!T->Lchild)&&(!T->Rchild))

count++;CountLeaf(T->Lchild,count);CountLeaf(T->Rchild,count);}//if}//CountLeafPage522024/2/3實(shí)例2：求二叉樹(shù)的深度算法思想：深度為樹(shù)中葉子結(jié)點(diǎn)所在層次的最大值。

結(jié)點(diǎn)的層次需從根結(jié)點(diǎn)起遞推，根結(jié)點(diǎn)為第一層。

需要在先序遍歷二叉樹(shù)的過(guò)程中求每個(gè)結(jié)點(diǎn)的層次數(shù)，并

將其中的最大值設(shè)為二叉樹(shù)的深度。算法一：voidBiTreeDepth(BiTreeT,intlevel,int&depth){

//T指向二叉樹(shù)的根，level為T(mén)所指結(jié)點(diǎn)所在層次，

//其初值為1，depth為當(dāng)前求得的最大層次,其初值為0if(T){if(level>depth)depth=level;BiTreeDepth(T->Lchild,level+1,depth);BiTreeDepth(T->Rchild,level+1,depth);}//if}//BiTreeDepthPage532024/2/3Page542024/2/3算法二：intdepth(BitreeT){ if(T==NULL)return0; else{ h1=depth(T->lchild); h2=depth(T->rchild); returnmax(h1,h2)+1; }}Page552024/2/3實(shí)例3：在二叉樹(shù)上查詢(xún)某個(gè)結(jié)點(diǎn)問(wèn)題描述假設(shè)給定一個(gè)和二叉樹(shù)中數(shù)據(jù)元素有相同類(lèi)型的值，在已知二叉樹(shù)中進(jìn)行查找，若存在和給定值相同的數(shù)據(jù)元素，則返回函數(shù)值為T(mén)RUE，并用引用參數(shù)返回指向該結(jié)點(diǎn)的指針；否則返回函數(shù)值為FALSE。算法的基本思想為：若二叉樹(shù)為空樹(shù)，則二叉樹(shù)上不存在這個(gè)結(jié)點(diǎn)，返回FALSE；否則，和根結(jié)點(diǎn)的元素進(jìn)行比較，若相等，則找到，即刻返回指向該結(jié)點(diǎn)的指針和函數(shù)值TRUE，從而查找過(guò)程結(jié)束；否則，在左子樹(shù)中進(jìn)行查找，若找到，則返回TRUE；否則，返回在右子樹(shù)中進(jìn)行查找的結(jié)果。因?yàn)橛易訕?shù)上查找的結(jié)果即為整個(gè)查找過(guò)程的結(jié)果，即若找到，返回的函數(shù)值為T(mén)RUE，并且已經(jīng)得到指向該結(jié)點(diǎn)的指針，否則返回的函數(shù)值為FALSE。Page562024/2/3boolLocate(BiTreeT,ElemTypex,BiTree&p){

//存在和x相同的元素，則p指向該結(jié)點(diǎn)并返回TRUE，否則p=NULL且返回FALSE

if(!T){

p=NULL;returnFALSE;}

//空樹(shù)中不存在這樣的結(jié)點(diǎn)

else{if(T->data==x){

p=T;returnTRUE;}

//找到所求結(jié)點(diǎn)elseif(Preorder(T->Lchild,x,p))

returnTRUE;

//在左子樹(shù)中找到所求結(jié)點(diǎn)

elsereturn(Preorder(T->Rchild,x,p)); //返回在右子樹(shù)

//中查找的結(jié)果

}//else}Page572024/2/3實(shí)例4：建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)--二叉鏈表voidCreateBiTree(BiTree&T){//按先序序列輸入二叉樹(shù)中結(jié)點(diǎn)的值（一個(gè)字符），空格表示空樹(shù)，//構(gòu)造二叉鏈表表示的二叉樹(shù)T。

scanf(&ch)；

if(ch==‘

’)T=NULL;

//建空樹(shù)

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))eixt(OVERFLOW);

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

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

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

}//else returnOK;}//CreateBiTreePage582024/2/3AB#CD###E#F##Page592024/2/3實(shí)例5：交換二叉樹(shù)中所有結(jié)點(diǎn)的左、右子樹(shù)。voidexchg_tree(bitreptrBT){

//采用后序遍歷的方法，交換每一個(gè)結(jié)點(diǎn)的左右子樹(shù)。

if(BT!=null){//非空

exchg_tree(BT->lchild);//交換左子樹(shù)所有結(jié)點(diǎn)指針

exchg_tree(BT->rchild);//交換右子樹(shù)所有結(jié)點(diǎn)指針

p=BT->lchild;//交換根結(jié)點(diǎn)左右指針

BT->lchild=BT->rchild;BT->rchild=p; }}Page602024/2/3實(shí)例6：輸出后序序列的逆序。voidpreorder(treeT){

//輸出后序序列的逆序

if(T!=NULL){ printf(“%f”,T->data); preorder(T->rchild); preorder(T->lchild); }}Page612024/2/3遞歸算法轉(zhuǎn)化為非遞歸算法遞歸算法優(yōu)點(diǎn)形式簡(jiǎn)潔，可讀性好，正確性容易得到證明，可以給程序的編制和調(diào)試帶來(lái)很大的方便。遞歸算法缺點(diǎn)遞歸調(diào)用比非遞歸調(diào)用消耗的時(shí)間與存儲(chǔ)空間多，運(yùn)行的效率較低。

所有的遞歸算法都可轉(zhuǎn)化成相應(yīng)的非遞歸算法。將遞歸算法改成相應(yīng)的非遞歸算法需要一個(gè)棧來(lái)記

錄調(diào)用返回的路徑。通過(guò)分析遞歸調(diào)用的執(zhí)行過(guò)程，

并觀(guān)察棧的變化就可得到相應(yīng)的非遞歸算法。Page622024/2/3statusInOrderTraverse(BiTreeT,status(*visit)(TElemTypee)){

//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)

//中序遍歷二叉樹(shù)T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。

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

while(!StackEmpty(S){

while(GetTop(S,p)&&p)Push(S,p->lchild); //向左走到盡頭

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

if(!StackEmpty(S)){ //訪(fǎng)問(wèn)結(jié)點(diǎn)，向右一步

Pop(S,p);if(!Visit(p->data))returnERROR;

Push(S,p->rchild);

}

} returnOK;}中序遍歷二叉樹(shù)T的非遞歸算法Page632024/2/3piP->AABCDEFGPage642024/2/3piP->AP->BABCDEFGPage652024/2/3piP->AP->BP->CABCDEFGPage662024/2/3p=NULLiP->AP->BABCDEFG訪(fǎng)問(wèn)：CPage672024/2/3piP->A訪(fǎng)問(wèn)：CBABCDEFGPage682024/2/3piP->AP->D訪(fǎng)問(wèn)：CBABCDEFGPage692024/2/3piP->AP->DP->E訪(fǎng)問(wèn)：CBABCDEFGPage702024/2/3訪(fǎng)問(wèn)：CBEpABCDEFGiP->AP->DPage712024/2/3訪(fǎng)問(wèn)：CBEP=NULLABCDEFGiP->AP->DP->GPage722024/2/3訪(fǎng)問(wèn)：CBEGpABCDEFGiP->AP->DPage732024/2/3訪(fǎng)問(wèn)：CBEGDpABCDEFGiP->APage742024/2/3pABCDEFGiP->AP->F訪(fǎng)問(wèn)：CBEGDPage752024/2/3ABCDEFGiP->Ap=NULL訪(fǎng)問(wèn)：CBEGDFPage762024/2/3pABCDEFGi訪(fǎng)問(wèn)：CBEGDFAPage772024/2/3ABCDEFGip=NULL訪(fǎng)問(wèn)：CBEGDFAPage782024/2/3表達(dá)式a+b*(c-d)-e/f用二叉樹(shù)表示-+/a*b-efcd先序遍歷：-+a*b-cd/ef波蘭式Page792024/2/3表達(dá)式a+b*(c-d)-e/f用二叉樹(shù)表示-+/a*b-efcd中序遍歷：-+a*b-cd/ef中綴表示Page802024/2/3表達(dá)式a+b*(c-d)-e/f用二叉樹(shù)表示-+/a*b-efcd后序遍歷：-+a*b-cd/ef逆波蘭式Page812024/2/3

已知一棵二叉樹(shù)的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫(huà)出這顆二叉樹(shù)。AEBCDFHIGJPage822024/2/3

已知一棵二叉樹(shù)的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫(huà)出這顆二叉樹(shù)。AFHIGJBECDPage832024/2/3

已知一棵二叉樹(shù)的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫(huà)出這顆二叉樹(shù)。AFHIGJBECDPage842024/2/3

已知一棵二叉樹(shù)的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫(huà)出這顆二叉樹(shù)。AFHIGJBDECPage852024/2/3

已知一棵二叉樹(shù)的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫(huà)出這顆二叉樹(shù)。AFHIGJBECDPage862024/2/3

已知一棵二叉樹(shù)的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫(huà)出這顆二叉樹(shù)。AHIGJBECDFPage872024/2/3

已知一棵二叉樹(shù)的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫(huà)出這顆二叉樹(shù)。AHIBECDFGJPage882024/2/3

已知一棵二叉樹(shù)的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫(huà)出這顆二叉樹(shù)。ABECDFGHJI

試編寫(xiě)算法實(shí)現(xiàn)上述過(guò)程。

思考：先序、中序、后序序列中任意給定兩個(gè)

序列就可以畫(huà)出該二叉樹(shù)嗎？為什么？Page892024/2/3按層次遍歷ABECDFGHJI按層次遍歷序列：ABFECGDHJIPage902024/2/36.3.2線(xiàn)索二叉樹(shù)遍歷二叉樹(shù)的實(shí)質(zhì)二叉樹(shù)遍歷的過(guò)程，為沿著某一條搜索路徑對(duì)二叉樹(shù)中的結(jié)點(diǎn)進(jìn)行一次且僅僅一次訪(fǎng)問(wèn)。也就是按一定規(guī)則將一個(gè)處于層次結(jié)構(gòu)中的結(jié)點(diǎn)排列成一個(gè)線(xiàn)性序列之后進(jìn)行依次訪(fǎng)問(wèn)，這個(gè)線(xiàn)性序列或是先序序列、或是中序序列或是后序序列。在這些線(xiàn)性序列中每個(gè)結(jié)點(diǎn)（除第一個(gè)和最后一個(gè)外）有且僅有一個(gè)直接前驅(qū)和直接后繼。顯然，這種信息是在遍歷的動(dòng)態(tài)過(guò)程中產(chǎn)生的，如果將這些信息在第一次遍歷時(shí)就保存起來(lái)，則在以后再次需要對(duì)二叉樹(shù)進(jìn)行"遍歷"時(shí)就可以將二叉樹(shù)視作線(xiàn)性結(jié)構(gòu)進(jìn)行訪(fǎng)問(wèn)操作了。

如何保存在遍歷過(guò)程中得到的前驅(qū)和后繼信息？Page912024/2/3最簡(jiǎn)單的辦法在結(jié)點(diǎn)中增加兩個(gè)指針域分別指向該結(jié)點(diǎn)的前驅(qū)和后繼。缺點(diǎn)：存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度大大降低，浪費(fèi)。另一種方法（尋求存儲(chǔ)結(jié)構(gòu)中的空指針域）靈感：

思想：一個(gè)含n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)鏈域的值為

“NULL”。

問(wèn)題：利用這些空的指針域存放指向前驅(qū)和后繼的信息。引起混淆。lchilddatarchild是左孩子還是前驅(qū)指針？是右孩子還是后繼指針？Page922024/2/3ABCDEFG^^^^^^^^Page932024/2/3

解決辦法：在結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域。lchildLtagdataRtagrchild 0 lchild域指示結(jié)點(diǎn)的左孩子Ltag= 1 lchild域指示結(jié)點(diǎn)的前趨 0 rchild域指示結(jié)點(diǎn)的右孩子Rtag= 1 rchild域指示結(jié)點(diǎn)的后繼Page942024/2/3線(xiàn)索鏈表：以這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表。線(xiàn)索：指向結(jié)點(diǎn)前趨和后繼的指針。線(xiàn)索二叉樹(shù)：加上線(xiàn)索二叉樹(shù)。線(xiàn)索化：對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€(xiàn)索二叉樹(shù)

的過(guò)程。

若某程序中所用二叉樹(shù)需經(jīng)常遍歷或查找結(jié)點(diǎn)在遍歷所得線(xiàn)性序列中的前驅(qū)或后繼，應(yīng)采用線(xiàn)索鏈表作存儲(chǔ)結(jié)構(gòu)。Page952024/2/3先序線(xiàn)索鏈表和先序線(xiàn)索二叉樹(shù)ABCDEABDCE先序序列：ABCDE先序線(xiàn)索鏈表0000111111thrt

0

1先序線(xiàn)索二叉樹(shù)NIL指向根結(jié)點(diǎn)指向序列的最后一個(gè)結(jié)點(diǎn)最后一個(gè)結(jié)點(diǎn)的右線(xiàn)索指向頭結(jié)點(diǎn)Page962024/2/3中序線(xiàn)索鏈表和中序線(xiàn)索二叉樹(shù)DABCE中序序列：BCAED中序線(xiàn)索鏈表0000111111ABCDEthrt

0

1中序線(xiàn)索二叉樹(shù)NILNIL指向根結(jié)點(diǎn)指向序列的最后一個(gè)結(jié)點(diǎn)最后一個(gè)結(jié)點(diǎn)的右線(xiàn)索指向頭結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)的左線(xiàn)索指向頭結(jié)點(diǎn)Page972024/2/3后序線(xiàn)索鏈表和后序線(xiàn)索二叉樹(shù)ABCDEABDCE后序序列：CBEDA后序線(xiàn)索鏈表0000111111thrt

0

1后序線(xiàn)索二叉樹(shù)指向根結(jié)點(diǎn)指向序列的最后一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)的左線(xiàn)索指向頭結(jié)點(diǎn)NILPage982024/2/3對(duì)二叉樹(shù)進(jìn)行中序線(xiàn)索化的算法StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){

//中序遍歷二叉樹(shù)T，并將其中序線(xiàn)索化，Thrt指向頭結(jié)點(diǎn)。

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);

Thrt->Ltag=0;Thrt->Rtag=1; //建頭結(jié)點(diǎn)

Thrt->rchild=Thrt; //右指針回指

if(!T)Thrt->lchild=Thrt; //若二叉樹(shù)為空，則左指針回指

else{ Thrt->lchild=T;pre=Thrt; InThreading(T); //中序遍歷進(jìn)行中序線(xiàn)索化

pre->rchild=Thrt;pre->Rtag=1; //最后一個(gè)結(jié)點(diǎn)線(xiàn)索化

Thrt->rchild=pre;//頭結(jié)點(diǎn)的右指針指向遍歷的最后一個(gè)結(jié)點(diǎn)

}returnOK;}//InOrderThreading空指針改為指向前驅(qū)或后繼的線(xiàn)索1

2

34

567891011Page992024/2/3voidInThreading(BiThrtTreep){if(p){ InThreading(p->lchild); //左子樹(shù)線(xiàn)索化

if(!p->lchild)

{p->Ltag=1;p->lchild=pre;} //前驅(qū)線(xiàn)索

if(!pre->rchild)

{pre->Rtag=1;p->rchild=p;} //后繼線(xiàn)索

pre=p;InThreading(p->rchild);}}先序、后序線(xiàn)索化的算法？與中序的區(qū)別？123

45

6789Page1002024/2/3在線(xiàn)索二叉樹(shù)上進(jìn)行遍歷（以中序線(xiàn)索二叉樹(shù)為例）遍歷的關(guān)鍵問(wèn)題找到訪(fǎng)問(wèn)的第一個(gè)結(jié)點(diǎn)；根據(jù)中序遍歷的特點(diǎn)，第一個(gè)結(jié)點(diǎn)必定是“其左子樹(shù)為空”的結(jié)點(diǎn)。若根結(jié)點(diǎn)沒(méi)有左子樹(shù)，根結(jié)點(diǎn)即為中序遍歷訪(fǎng)問(wèn)的第一個(gè)結(jié)點(diǎn)；若根結(jié)點(diǎn)有左子樹(shù)，第一個(gè)結(jié)點(diǎn)是其左子樹(shù)中“最左下的結(jié)點(diǎn)”。即從根結(jié)點(diǎn)出發(fā)，順指針lchild找到其左子樹(shù)直至某個(gè)結(jié)點(diǎn)的指針lchild為"線(xiàn)索"止，該結(jié)點(diǎn)為中序序列中的第一個(gè)結(jié)點(diǎn)。找到每個(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ù)中訪(fǎng)問(wèn)的第一個(gè)結(jié)點(diǎn)。應(yīng)該從它的右子樹(shù)根出發(fā)，順指針lchild直至沒(méi)有左子樹(shù)的結(jié)點(diǎn)為止，該結(jié)點(diǎn)即為它的后繼。Page1012024/2/3FJICAHEGBDPage1022024/2/3FJICAHEGBD另一種遍歷方法：找最后一個(gè)結(jié)點(diǎn)；然后找每個(gè)結(jié)點(diǎn)的前驅(qū)。先序、后序線(xiàn)索二叉樹(shù)上如何遍歷？Page1032024/2/3對(duì)線(xiàn)索二叉樹(shù)進(jìn)行中序遍歷的算法StatusInOrderTraverse_Tri(BiThrTreeT,Status(*Visit)(TElemTypee)){

//T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的lchid指向根結(jié)點(diǎn)，

//中序遍歷二叉線(xiàn)索樹(shù)T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。

p=T->lchild; //p指向根結(jié)點(diǎn)

while(p!=T){ //空樹(shù)或遍歷結(jié)束時(shí)，p==T while(p->Ltag==0) p=p->lchild; if(!Visit(p->data)) returnERROR;//訪(fǎng)問(wèn)左子樹(shù)為空的結(jié)點(diǎn)

while(p->Rtag==1&&p->rchild!=T){

p=p->rchild; Visit(p->data);//訪(fǎng)問(wèn)后繼結(jié)點(diǎn)

} p=p->rchild; } returnOK;}123

45

6

789Page1042024/2/3

學(xué)習(xí)線(xiàn)索化時(shí)，有三點(diǎn)必須注意：何種“序”的線(xiàn)索化，是先序、中序還是后序；要“前驅(qū)”線(xiàn)索化、“后繼”線(xiàn)索化還是“全”線(xiàn)索化；只有空指針處才能加線(xiàn)索；Page1052024/2/36.4樹(shù)和森林6.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親表示法以一組連續(xù)的存儲(chǔ)空間存放樹(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指針指示其雙親結(jié)點(diǎn)在這連續(xù)的存儲(chǔ)空間中的位置。形式說(shuō)明#defineMAX_TREE_SIZE=100;typedefstructPTNode{

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

TElemTypedata;

intparent;

//雙親位置域

}PTNode;typedefstruct{

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

PTNodenodes[MAX_TREE_SIZE];

intr,n;

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

}PTree;Page1062024/2/3abcdefhgiacdefghib-1011244406012345789dataparent優(yōu)點(diǎn)：找雙親容易。缺點(diǎn)：找孩子難，

需要遍歷整個(gè)結(jié)構(gòu)。r=0n=9Page1072024/2/3孩子表示法把每個(gè)結(jié)點(diǎn)的孩子排列起來(lái)，看成一個(gè)線(xiàn)性表，以單鏈表存儲(chǔ)；令其頭指針和結(jié)點(diǎn)的數(shù)據(jù)元素構(gòu)成一個(gè)結(jié)點(diǎn)，并將所有這樣的結(jié)點(diǎn)存放在一個(gè)地址連續(xù)的存儲(chǔ)空間里。形式說(shuō)明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ù)和根的位置

}CTree;Page1082024/2/3abcdefhgi優(yōu)點(diǎn)：找孩子容易。缺點(diǎn)：找雙親難，

需要遍歷整個(gè)結(jié)構(gòu)。acdefghib6012345789datafc12^34^^867^5^^^^^n=9r=0Page1092024/2/3abcdefhgi優(yōu)點(diǎn)：找孩子和雙親容易。缺點(diǎn)：存儲(chǔ)空間增加。acdefghib12^34^^867^5^^^^^n=9r=06012345789datafcpar-101124440Page1102024/2/3孩子兄弟表示法（二叉鏈表表示法）用二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。形式說(shuō)明typedefstructCSNode{

ElemTypedata;

structCSNode*firstchild,*nextsibling;

}CSNode,*CSTree;Page1112024/2/3abcdefghi^^^^^^^^^^abcdefhgiPage1122024/2/3優(yōu)點(diǎn)：便于實(shí)現(xiàn)樹(shù)的各種操作。缺點(diǎn)：破壞了樹(shù)的層次。abcdefhgiabcdefghi^^^^^^^^^^Page1132024/2/36.4.2森林與二叉樹(shù)的轉(zhuǎn)換ACBED樹(shù)ABCDE二叉樹(shù)A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^對(duì)應(yīng)存儲(chǔ)存儲(chǔ)解釋解釋Page1142024/2/3樹(shù)轉(zhuǎn)換為二叉樹(shù)的方法加線(xiàn)：在兄弟之間加一連線(xiàn)。抹線(xiàn)：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系。旋轉(zhuǎn)：以樹(shù)的根結(jié)點(diǎn)為軸心，將整樹(shù)順時(shí)針轉(zhuǎn)45°。ABCDEFGHIPage1152024/2/3ABCDEFGHIABCDEFGHIABCDEFGHI樹(shù)轉(zhuǎn)換成的二叉樹(shù)其右子樹(shù)一定為空Page1162024/2/3森林轉(zhuǎn)換成二叉樹(shù)的方法將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù)。將每棵樹(shù)的根結(jié)點(diǎn)用線(xiàn)相連。以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹(shù)型結(jié)構(gòu)。ABCDEFGHIJPage1172024/2/3ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJPage1182024/2/3二叉樹(shù)轉(zhuǎn)換成樹(shù)的方法加線(xiàn)：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩

子，……沿分支找到的所有右孩子，都與p的雙親用線(xiàn)連起來(lái)。抹線(xiàn)：抹掉原二叉樹(shù)中雙親與右孩子之間的連線(xiàn)。調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)。ABCDEFGHIPage1192024/2/3ABCDEFGHIABCDEFGHIABCDEFGHIPage1202024/2/3二叉樹(shù)轉(zhuǎn)換成森林抹線(xiàn)：將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線(xiàn)，及沿右分支搜索到的

所有右孩子間連線(xiàn)全部抹掉，使之變成孤立的二叉樹(shù)。還原：將孤立的二叉樹(shù)還原成樹(shù)。ABCDEFGHIJPage1212024/2/3ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJPage1222024/2/36.4.3樹(shù)和森林的遍歷樹(shù)的遍歷先根遍歷若樹(shù)不空，則先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后依次從左到右先根遍歷根的各棵子樹(shù)。后根遍歷若樹(shù)不空，則先依次從左到右后根遍歷根的各棵子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)。Page1232024/2/3ABCDEFGHIJKLMNO先根遍歷：后根遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDA轉(zhuǎn)換二叉樹(shù)的先序遍歷轉(zhuǎn)換二叉樹(shù)的中序遍歷Page1242024/2/3森林的遍歷先序遍歷

訪(fǎng)問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；先序遍歷第一棵樹(shù)中的子樹(shù)森林；先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。中序遍歷

中序遍歷第一棵樹(shù)中的子樹(shù)森林；訪(fǎng)問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。Page1252024/2/3ABCDEFGHIJ先序遍歷：中序遍歷：ABCDEFGHIJBCDAFEHJIG轉(zhuǎn)換二叉樹(shù)的先序遍歷轉(zhuǎn)換二叉樹(shù)的中序遍歷Page1262024/2/36.6哈夫曼樹(shù)及其應(yīng)用6.6.1哈夫曼樹(shù)（最優(yōu)二叉樹(shù)帶權(quán)路徑長(zhǎng)度最短的樹(shù)）基本概念路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支。路徑長(zhǎng)度：路徑上的分支數(shù)目稱(chēng)為路徑長(zhǎng)度。樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。256714327134561710完全二叉樹(shù)是路徑長(zhǎng)度最短的二叉樹(shù)Page1272024/2/3結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上

的權(quán)值的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。通常

記作其中，Wk葉子結(jié)點(diǎn)的權(quán)值，lk葉子結(jié)點(diǎn)的路徑長(zhǎng)度。dcab2475WPL=7*3+5*3+2*1+4*2=46Page1282024/2/3結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上

的權(quán)值的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。通常

記作其中，Wk葉子結(jié)點(diǎn)的權(quán)值，lk葉子結(jié)點(diǎn)的路徑長(zhǎng)度。WPL=7*2+5*2+2*2+4*2=36abcd7524Page1292024/2/3結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上

的權(quán)值的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。通常

記作其中，Wk葉子結(jié)點(diǎn)的權(quán)值，lk葉子結(jié)點(diǎn)的路徑長(zhǎng)度。WPL=7*1+5*2+2*3+4*3=35abcd7524Page1302024/2/3結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上

的權(quán)值的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。通常

記作其中，Wk葉子結(jié)點(diǎn)的權(quán)值，lk葉子結(jié)點(diǎn)的路徑長(zhǎng)度。

加權(quán)后路徑長(zhǎng)度最小的并非是完全二叉樹(shù)，而是權(quán)大的葉子離根最近的二叉樹(shù)。Page1312024/2/3哈夫曼樹(shù)：設(shè)有n個(gè)權(quán)值{w1,w2,……wn}，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)

的二叉樹(shù)，每個(gè)葉子的權(quán)值為wi，WPL最小的二叉樹(shù)。構(gòu)造哈夫曼樹(shù)的過(guò)程（哈夫曼算法）根據(jù)給定的n個(gè)權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹(shù)，令初始權(quán)值為wj；在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，置新二叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；在森林中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入森林中；重復(fù)上述兩步，直到只含一棵樹(shù)為止，這棵樹(shù)即哈夫曼樹(shù)。

哈夫曼樹(shù)的形態(tài)不是唯一的，但對(duì)具有一組權(quán)值的各哈夫曼樹(shù)的WPL是唯一的。Page1322024/2/3w={5,29,7,8,14,23,3,11}，構(gòu)造哈夫曼樹(shù)85311192342291487152958100WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=271w={5,29,7,8,14,23,3,11}w={29,7,8,14,23,11,8}w={29,14,23,11,8,15}w={29,14,23,15,19}w={29,23,19,29}w={29,29,42}w={42,58}w={100}Page1332024/2/3哈夫曼樹(shù)應(yīng)用判定樹(shù)等級(jí)分?jǐn)?shù)段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.1070

a<80YNCa<60EYNABYN80

a<90DYN60

a<70EADBC哈夫曼樹(shù)Page1342024/2/3哈夫曼樹(shù)應(yīng)用判定樹(shù)等級(jí)分?jǐn)?shù)段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.10a<80YNa<60EDYNCa<70YNa<90YNBA70

a<80YNCa<60EYNABYN80

a<90DYN60

a<70Page1352024/2/36.6.2哈夫曼編碼背景目前，遠(yuǎn)距離通信的主要手段是電報(bào)，即將需傳送的文字轉(zhuǎn)換成由二進(jìn)制的字符組成的字符串。編碼時(shí)需要遵循以下原則解碼的結(jié)果唯一；發(fā)送的二進(jìn)制編碼盡可能短。兩類(lèi)二進(jìn)制編碼等長(zhǎng)編碼：各個(gè)字符的編碼長(zhǎng)度相等。優(yōu)點(diǎn)：解碼簡(jiǎn)單。缺點(diǎn)：編碼長(zhǎng)度可能不最短。不等長(zhǎng)編碼：各個(gè)字符的編碼長(zhǎng)度不等。優(yōu)點(diǎn)：編碼長(zhǎng)度盡可能地短。缺點(diǎn)：解碼困難。Page1362024/2/3例如：傳送電文“ABACCDA”等長(zhǎng)編碼A：00B：01C：10D：11編碼結(jié)果00010010101100，長(zhǎng)度為14位。解碼方以?xún)晌粸橐蛔侄谓獯a。不等長(zhǎng)編碼原則：出現(xiàn)次數(shù)較多的字符編碼短，次數(shù)較少的字符編碼長(zhǎng)。A：0B：00C：1D：01編碼結(jié)果000011010，長(zhǎng)度為9位。解碼方無(wú)法解碼，因?yàn)榻獯a的結(jié)果不唯一。Page1372024/2/3前綴編碼任意一個(gè)字符的編碼都不能是另一個(gè)字符的編碼的前綴，這種編碼稱(chēng)為前綴編碼。哈夫曼編碼（同時(shí)滿(mǎn)足代碼長(zhǎng)度短，且解碼唯一）目標(biāo)：使電文總長(zhǎng)最短。以字符出現(xiàn)的次數(shù)為權(quán)，構(gòu)造一棵赫夫曼樹(shù)；將樹(shù)中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的0、1序列，這樣得到的編碼稱(chēng)為哈夫碼編碼。哈夫曼編碼為前綴編碼。以這組編碼傳送電文可使電文總長(zhǎng)最短(對(duì)所有其它前綴編碼而言)。Page1382024/2/3vuiywtre

字符集vwertyui頻率5297814233110000000111111100100000111011111110100001iuytrewvPage1392024/2/3哈夫曼解碼從哈夫曼樹(shù)根開(kāi)始，從待譯碼電文中逐位取碼。若編碼是“0”，則向左走；若編碼是“1”，則向右走，一旦到達(dá)葉子結(jié)點(diǎn)，則譯出一個(gè)字符；再重新從根出發(fā)，直到電文結(jié)束。vuiywtre

00000001111111解碼：010結(jié)果：reviewPage1402024/2/3構(gòu)造哈夫曼樹(shù)和哈夫曼編碼的算法typedefstruct{

unsignedintweight;

unsignedintparent,lchild,rchild;

}HTNode,*HuffmanTree; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹(shù)typedefchar**HuffmanCode; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表Page1412024/2/3voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){

//w存放n個(gè)字符的權(quán)值，構(gòu)造哈夫曼樹(shù)HT，并求出n個(gè)字符的哈夫曼編碼HC。

if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0號(hào)單元未用

for(p=HT,p++,i=1;i<=n;++i,++p,++w)*p={*w,0,0,0};//初始化

for(;i<=m;++i,++p)*p={0,0,0,0};for(i=n+1;i<=m;++i){ //建哈夫曼樹(shù)

Select(HT,i-1,s1,s2)//在HT[1..i-1]選擇parent為0，且weight

//最小兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2。

HT[s1].parent=i;HT[s2].parent=i;

HT[i].lchild=s1;HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;

}12345

6

7

8

9

10

11Page1422024/2/3//從葉子到根逆向求每個(gè)字符的哈夫曼編碼//HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n個(gè)字符編碼

//的頭指針向量

cd=(char*)malloc(n*sizeof(char)); //分配求編碼的工作空間

cd[n-1]=“\0”; //編碼結(jié)束符

for(i=1;i<=n;++i){ //逐個(gè)字符求哈夫曼編碼

start=n-1; //編碼結(jié)束符位置

f