數(shù)據(jù)結(jié)構(gòu) 第六章樹和二叉樹

數(shù)據(jù)結(jié)構(gòu)第六章樹和二叉樹第1頁，課件共69頁，創(chuàng)作于2023年2月第六章樹和二叉樹6.1樹的定義和基本術(shù)語6.2二叉樹6.2.1二叉樹的定義6.2.2二叉樹的性質(zhì)6.2.3二叉樹的存儲結(jié)構(gòu)6.3遍歷二叉樹和線索二叉樹6.3.1遍歷二叉樹6.3.2線索二叉樹6.4樹和森林6.4.1樹的存儲結(jié)構(gòu)6.4.2森林與二叉樹的轉(zhuǎn)換6.6赫夫曼樹及其應(yīng)用6.6.1最優(yōu)二叉樹(赫夫曼樹)6.6.2赫夫曼編碼第2頁，課件共69頁，創(chuàng)作于2023年2月樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹形結(jié)構(gòu)是結(jié)點(diǎn)之間有分支，并具有層次關(guān)系的結(jié)構(gòu)。它非常類似于自然界中的樹。第3頁，課件共69頁，創(chuàng)作于2023年2月ABCDEFGH樹形結(jié)構(gòu)——結(jié)點(diǎn)間具有分層次的連接關(guān)系HBCDEFGA第4頁，課件共69頁，創(chuàng)作于2023年2月6.1樹的定義和基本術(shù)語

樹(Tree)是n(n>0)個(gè)結(jié)點(diǎn)的有限集合T，它滿足如下條件：有且僅有一個(gè)稱為根(Root)的結(jié)點(diǎn)。其余結(jié)點(diǎn)可劃分為m(m>=0)個(gè)互不相交的有限集合T1,T2,…,Tm,其中每個(gè)集合又是一棵樹，并稱其為根的子樹(SubTree)。這是一個(gè)遞歸定義。有時(shí)n=0也稱為空樹。ACGT2DHI

T3J

MB

E

LKT1F第5頁，課件共69頁，創(chuàng)作于2023年2月樹的表示方法1）樹形圖法

2）嵌套集合法

3）廣義表形式

4）凹入表示法(A(B,C(E,F),D(G)))ABCDEFGABCEFDGABDGEFC第6頁，課件共69頁，創(chuàng)作于2023年2月線性結(jié)構(gòu)

（一對一關(guān)系）

樹結(jié)構(gòu)（一對多關(guān)系）

第一個(gè)數(shù)據(jù)元素(無前驅(qū))

根結(jié)點(diǎn)(無前驅(qū))最后一個(gè)數(shù)據(jù)元素(無后繼)

多個(gè)終端結(jié)點(diǎn)(無后繼)其它數(shù)據(jù)元素

樹中其它結(jié)點(diǎn)(一個(gè)前驅(qū)、一個(gè)后繼)

(一個(gè)前驅(qū)、多個(gè)后繼)樹形結(jié)構(gòu)和線性結(jié)構(gòu)的比較第7頁，課件共69頁，創(chuàng)作于2023年2月樹結(jié)構(gòu)的基本術(shù)語結(jié)點(diǎn)(node)——表示樹中的元素，包括數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點(diǎn)的度(degree)——結(jié)點(diǎn)擁有的子樹數(shù)。葉子(leaf)或終端結(jié)點(diǎn)——度為0的結(jié)點(diǎn)。分支結(jié)點(diǎn)——度大于零的結(jié)點(diǎn)。樹的度——樹中所有結(jié)點(diǎn)的度的最大值。孩子(child)——結(jié)點(diǎn)的子樹的根。雙親(parents)——孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)。兄弟(sibling)——同一雙親的孩子。堂兄弟——其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。結(jié)點(diǎn)的層次(level)——從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層…。深度(depth)——樹中結(jié)點(diǎn)的最大層次數(shù)。森林(forest)——m(m0)棵互不相交的樹的集合。ABCDEFGHIJKLM第8頁，課件共69頁，創(chuàng)作于2023年2月樹的抽象數(shù)據(jù)類型定義：ADTTree｛

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

數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹;若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則R＝｛H｝，H是如下二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；（2）若D－｛root｝≠Ф，則存在D－｛root｝的一個(gè)劃分D1,D2,...,Dm（m＞0），對任意j≠k（1≤j,k≤m）有Dj∩Dk=φ，且對任意的i（1≤i≤m），唯一存在數(shù)據(jù)元素xi∈Di，有<root,xi>∈H;（3）對應(yīng)于D－｛root｝的劃分，H－｛<root,x1>，....，<root,xm>｝有唯一的一個(gè)劃分H1,H2,...,Hm（m＞0），對任意j≠k（1≤j,k≤m）有Hj∩Hk=Ф，且對任意的i（1≤i≤m），Hi是Di上的二元關(guān)系，（Di,{Hi}）是一棵符合本定義的樹，稱為根root的子樹。第9頁，課件共69頁，創(chuàng)作于2023年2月樹的抽象數(shù)據(jù)類型定義--基本操作（之一）

InitTree(&T)；操作結(jié)果：構(gòu)造空樹T。

DestroyTree(&T)；初始條件：樹T存在。操作結(jié)果：銷毀樹T。

CreateTree(&T，definition)；初始條件：definition給出樹T的定義。操作結(jié)果：按definition構(gòu)造樹T。

ClearTree(&T)；初始條件：樹T存在。操作結(jié)果：將樹T清為空樹。第10頁，課件共69頁，創(chuàng)作于2023年2月樹的抽象數(shù)據(jù)類型定義--基本操作（之二）

TreeEmpty(T)

初始條件：樹T存在。操作結(jié)果：若T為空樹，則返回TURE，否則FALSE。

TreeDepth(T)

初始條件：樹T存在。操作結(jié)果：返回T的深度。

Root(T)

初始條件：樹T存在。操作結(jié)果：返回T的根。

Value(T,cur_e)；初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回cur_e的值。第11頁，課件共69頁，創(chuàng)作于2023年2月樹的抽象數(shù)據(jù)類型定義--基本操作（之三）

Assign(T，cur_e，value)

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：結(jié)點(diǎn)cur_e賦值為value。

Parent(T，cur_e)

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則函數(shù)值為“空”。

LeftChild(T，cur_e)

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：若cur_e是T的非葉子結(jié)點(diǎn)，則返回它的最左孩子，否則返回“空”。

RightSibling(T，cur_e)

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則函數(shù)值為“空”。第12頁，課件共69頁，創(chuàng)作于2023年2月樹的抽象數(shù)據(jù)類型定義--基本操作（之四）

InsertChild(&T，&p，i，c)；初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p所指結(jié)點(diǎn)的度＋1，非空樹c與T不相交。操作結(jié)果：插入c為T中p指結(jié)點(diǎn)的第i棵子樹。

DeleteChild(&T，&p，i)；初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p指結(jié)點(diǎn)的度。操作結(jié)果：刪除T中p所指結(jié)點(diǎn)的第i棵子樹。

TraverseTree(T，Visit())；初始條件：樹t存在，Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit()一次且至多一次。一旦Visit()失敗，則操作失敗。｝ADTTree第13頁，課件共69頁，創(chuàng)作于2023年2月6.2二叉樹二叉樹的定義：二叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。二叉樹的特點(diǎn)：每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn))二叉樹的子樹有左、右之分，且其次序不能任意顛倒第14頁，課件共69頁，創(chuàng)作于2023年2月二叉樹的五種基本形態(tài)：空二叉樹只有一個(gè)根結(jié)點(diǎn)的二叉樹右子樹為空的二叉樹左子樹為空的二叉樹左、右子樹均非空的二叉樹注意：二叉樹中子樹是有左右之分的，即使只有一棵子樹，或?yàn)樽笞訕洌驗(yàn)橛易訕溥@不是二叉樹這是二叉樹第15頁，課件共69頁，創(chuàng)作于2023年2月6.2.2二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)。性質(zhì)2：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k≥1)。性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。1234567第16頁，課件共69頁，創(chuàng)作于2023年2月幾種特殊形態(tài)的二叉樹滿二叉樹定義：深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)完全二叉樹定義：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)，稱為完全二叉樹。特點(diǎn)：①葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)②對任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為L，則其左分支下子孫的最大層次必為L或L+1說明：①滿二叉樹是完全二叉樹,反之不成立;

②對于完全二叉樹,若某結(jié)點(diǎn)無左孩子,則必?zé)o右孩子,該結(jié)點(diǎn)為葉結(jié)點(diǎn)。第17頁，課件共69頁，創(chuàng)作于2023年2月1231145891213671014151231145891267101234567123456第18頁，課件共69頁，創(chuàng)作于2023年2月性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1性質(zhì)5：如果對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號，則對任一結(jié)點(diǎn)i(1≤i≤n)，有：

(1)如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙親；如果i>1，則其雙親是i/2(2)如果2i>n，則結(jié)點(diǎn)i無左孩子；如果2in，則其左孩子是2i(3)如果2i+1>n，則結(jié)點(diǎn)i無右孩子；如果2i+1n，則其右孩子是2i+1123114589126710第19頁，課件共69頁，創(chuàng)作于2023年2月6.2.3二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結(jié)點(diǎn)元素，即將完全二叉樹上編號為i的結(jié)點(diǎn)元素存儲在如上定義的一維數(shù)組中下標(biāo)為i-1的分量中。下標(biāo)01234567891011ABCDEFGHIJKLABCDEFGHIJKL第20頁，課件共69頁，創(chuàng)作于2023年2月對完全二叉樹而言，順序存儲結(jié)構(gòu)既簡單又節(jié)省存儲空間。一般的二叉樹采用順序存儲結(jié)構(gòu)時(shí)，雖然簡單，但易造成存儲空間的浪費(fèi)。

(最壞的情況下，一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的右單支樹需要2k-1個(gè)結(jié)點(diǎn)的存儲空間)ABCDEE?D?CBA第21頁，課件共69頁，創(chuàng)作于2023年2月鏈?zhǔn)酱鎯Y(jié)構(gòu)typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;

rchilddatalchilddataparentlchildrchilddatalchildrchildparent第22頁，課件共69頁，創(chuàng)作于2023年2月鏈?zhǔn)酱鎯Y(jié)構(gòu)示例注意：

①一個(gè)二叉鏈表由根指針root惟一確定。若二叉樹為空，則root=NULL；若結(jié)點(diǎn)的某個(gè)孩子不存在，則相應(yīng)的指針為空。

②具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有2n個(gè)指針域。其中只有n-1個(gè)用來指示結(jié)點(diǎn)的左、右孩子，其余的n+1個(gè)指針域?yàn)榭?。?3頁，課件共69頁，創(chuàng)作于2023年2月基本操作的函數(shù)原型說明(一)StatusCreateBiTree(BiTree&T);//按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），//空格字符表示空樹，//構(gòu)造二叉鏈表表示的二叉樹T。StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲結(jié)構(gòu),Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)//先序遍歷二叉樹T，對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。//一旦Visit()失敗，則操作失敗。第24頁，課件共69頁，創(chuàng)作于2023年2月基本操作的函數(shù)原型說明(二)

StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲結(jié)構(gòu),Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。//中序遍歷二叉樹T，一旦Visit()失敗，則操作失敗。StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲結(jié)構(gòu),Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。//后序遍歷二叉樹T，一旦Visit()失敗，則操作失敗。StatusLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲結(jié)構(gòu),Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。//層序遍歷二叉樹T，一旦Visit()失敗，則操作失敗。第25頁，課件共69頁，創(chuàng)作于2023年2月6.3遍歷二叉樹

按某條搜索路徑巡訪二叉樹中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。ABCDGEF第26頁，課件共69頁，創(chuàng)作于2023年2月假如以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點(diǎn)和遍歷右子樹，遍歷整個(gè)二叉樹則有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。若規(guī)定先左后右，則只有前三種情況，分別規(guī)定為：

DLR——先（根）序遍歷，

LDR——中（根）序遍歷，

LRD——后（根）序遍歷。第27頁，課件共69頁，創(chuàng)作于2023年2月先序遍歷二叉樹的操作定義若二叉樹為空，則空操作；否則（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。

ABCDFEGABCDGEF第28頁，課件共69頁，創(chuàng)作于2023年2月中序遍歷二叉樹的操作定義若二叉樹為空，則空操作；否則（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。

CBDFAGEABCDGEF第29頁，課件共69頁，創(chuàng)作于2023年2月后序遍歷二叉樹的操作定義若二叉樹為空，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。

CFDBGEAABCDGEF第30頁，課件共69頁，創(chuàng)作于2023年2月例：已知結(jié)點(diǎn)的先序序列和中序序列，求整棵二叉樹先序序列：ABCDEFG中序序列：CBEDAFGAC

B

E

DFGABCDEFGABCFDEG第31頁，課件共69頁，創(chuàng)作于2023年2月先序遍歷二叉樹的遞歸算法StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}//PreOrderTraverse第32頁，課件共69頁，創(chuàng)作于2023年2月作業(yè)分別寫出中序遍歷二叉樹和后序遍歷二叉樹的遞歸算法已知一棵二叉樹的中序和后序序列如下，畫出此二叉樹并寫出該二叉樹的先序遍歷序列。中序序列：A,B,C,D,J,E,F,H,G,I

后序序列：B,C,J,D,A,H,I,G,F,E第33頁，課件共69頁，創(chuàng)作于2023年2月中序遍歷二叉樹的非遞歸算法基本思想

中序遍歷一棵非空樹t時(shí)，首先應(yīng)該進(jìn)入t的左子樹訪問，此時(shí)由于t的根結(jié)點(diǎn)及右子樹尚未訪問，因此必須將t保存起來，放入棧中，以便訪問完其左子樹后，從棧中取出t，進(jìn)行其根結(jié)點(diǎn)及右子樹的訪問；對t的左子樹和右子樹的遍歷也是如此。主要步棸先將根結(jié)點(diǎn)入棧；將棧頂元素的所有左孩子依次入棧；出棧一個(gè)結(jié)點(diǎn)，訪問之；若該結(jié)點(diǎn)的右孩子不空，入棧，重復(fù)2)，3)步；如果棧不空，重復(fù)3)，4)步，否則結(jié)束。第34頁，課件共69頁，創(chuàng)作于2023年2月StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉鏈表存儲結(jié)構(gòu)，中序遍歷二叉樹的非遞歸算法。

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)){ //訪問結(jié)點(diǎn)，向右一步

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

}//if }//whilereturnOK;}//InOrderTraverse算法6.2第35頁，課件共69頁，創(chuàng)作于2023年2月算法6.3StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}//根指針進(jìn)棧，遍歷左子樹

else{//根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹

Pop(S,p);if(!Visit(p->data))returnERROR;p=p->rchild;}//else}//whilereturnOK;}//InOrderTraverse第36頁，課件共69頁，創(chuàng)作于2023年2月6.3.2線索二叉樹n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針（這種附加的指針稱為“線索”）這種加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹(Threaded

BinaryTree)。對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。第37頁，課件共69頁，創(chuàng)作于2023年2月線索二叉樹結(jié)點(diǎn)的結(jié)構(gòu):其中，ltag和rtag是增加的兩個(gè)標(biāo)志域，用來區(qū)分結(jié)點(diǎn)的左、右指針域是指向其左、右孩子的指針，還是指向其前趨或后繼的線索。

0lchild域指示其左孩子ltag={1lchild域指示其前驅(qū)

0rchild域指示其右孩子rtag={1rchild域指示其后繼datalchildrchildrtagltag第38頁，課件共69頁，創(chuàng)作于2023年2月中序線索二叉樹的表示第39頁，課件共69頁，創(chuàng)作于2023年2月注意：

圖中的實(shí)線表示指針，虛線表示線索。

結(jié)點(diǎn)C的左線索為空，表示C是中序序列的開始結(jié)點(diǎn)，無前趨；

結(jié)點(diǎn)E的右線索為空，表示E是中序序列的終端結(jié)點(diǎn)，無后繼。

線索二叉樹中，一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)的充要條件為：左、右標(biāo)志均是1。

第40頁，課件共69頁，創(chuàng)作于2023年2月6.4樹和森林樹的存儲結(jié)構(gòu)雙親表示法（靜態(tài)鏈表存儲）：以一組連續(xù)空間存儲樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在(靜態(tài))鏈表中的位置

第41頁，課件共69頁，創(chuàng)作于2023年2月雙親表示法舉例RADEFCBGKHR-1A0B0C0D1E1F3G6H6K60123456789數(shù)組下標(biāo):第42頁，課件共69頁，創(chuàng)作于2023年2月#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;//雙親位置域

}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//結(jié)點(diǎn)數(shù)

}PTree;*便于涉及雙親的操作；*求結(jié)點(diǎn)的孩子時(shí)需要遍歷整棵樹。第43頁，課件共69頁，創(chuàng)作于2023年2月孩子鏈表存儲表示舉例RADEFCBGKH0123456789數(shù)組下標(biāo):RAB∧

CD∧

E∧

FG∧

H∧

K∧123∧

45∧

6∧

789∧

第44頁，課件共69頁，創(chuàng)作于2023年2月6.4.1樹的存儲結(jié)構(gòu)孩子表示法（鏈?zhǔn)酱鎯Γ?/p>

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

intchild;structCTNode*next;}*ChildPtr;typedefstruct{ //雙親結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;ChildPtrfirstchild;//孩子鏈表頭指針

}CTBox;typedefstruct{ //樹結(jié)構(gòu)

CTBoxnodes[MAX_TREE_SIZE];intn,r;//結(jié)點(diǎn)數(shù)和根的位置

}CTree;*便于涉及孩子的操作；*求結(jié)點(diǎn)的雙親時(shí)不方便。第45頁，課件共69頁，創(chuàng)作于2023年2月6.4.1樹的存儲結(jié)構(gòu)孩子兄弟表示法：又稱二叉樹表示法，或二叉鏈表表示法。記以二叉鏈表作樹的存儲結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)，分別命名為firstchild域和nextsibling域。typedefstructCSNode{

ELemTypedata;

structCSNode*firstchild,*nextsibling;

}CSNode,*CSTree;第46頁，課件共69頁，創(chuàng)作于2023年2月RADEFCBGKHR^A^DE^^C^H^F^G^B^K^^孩子兄弟表示法示例：*易于實(shí)現(xiàn)找結(jié)點(diǎn)孩子的操作；第47頁，課件共69頁，創(chuàng)作于2023年2月6.4.2森林與二叉樹的轉(zhuǎn)換將樹轉(zhuǎn)換成二叉樹的步驟：將所有兄弟結(jié)點(diǎn)用邊連接起來對每個(gè)結(jié)點(diǎn)，除了保留與其長子的邊外，去掉該結(jié)點(diǎn)與其它孩子的邊abcefd轉(zhuǎn)換abcefd整理abcefd說明：根結(jié)點(diǎn)沒有右孩子第48頁，課件共69頁，創(chuàng)作于2023年2月6.4.2森林與二叉樹的轉(zhuǎn)換將森林轉(zhuǎn)換成二叉樹的步驟將森林中的每棵樹轉(zhuǎn)換成二叉樹將每個(gè)二叉樹的根結(jié)點(diǎn)看成兄弟用邊連起來bacdefghi轉(zhuǎn)換abcdefghi整理abcdefghi第49頁，課件共69頁，創(chuàng)作于2023年2月6.4.2森林與二叉樹的轉(zhuǎn)換將二叉樹轉(zhuǎn)換成樹(森林)的步驟如果根有右子樹，將根的右子樹分開，得到幾棵二叉樹根據(jù)得到的二叉樹往回轉(zhuǎn)換。(若結(jié)點(diǎn)X是雙親y的左孩子，則把X的右孩子，右孩子的右孩子,…,都與y用連線連起來，最后去掉所有X到右孩子的連線。)abcdefghijk轉(zhuǎn)換feabcdjkghi去邊整理feabcdjkghi第50頁，課件共69頁，創(chuàng)作于2023年2月6.4.3樹和森林的遍歷樹的兩種遍歷方法：先根遍歷：訪問樹的根結(jié)點(diǎn)；依次先根遍歷每棵子樹。RADEBCFGHK后根遍歷：依次后根遍歷每棵子樹；訪問樹的根結(jié)點(diǎn)。DEABGHKFCRRADEFCBGKH第51頁，課件共69頁，創(chuàng)作于2023年2月6.4.3樹和森林的遍歷森林的兩種遍歷方法：先序遍歷森林：若森林非空，則訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林；先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的的森林。中序遍歷森林：若森林非空，則中序遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林；訪問森林中第一棵樹的根結(jié)點(diǎn)；中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的的森林。第52頁，課件共69頁，創(chuàng)作于2023年2月先序遍歷：ABCDEFGHIJ中序遍歷：BCDAFEHJIGABCDEFGH

IJ第53頁，課件共69頁，創(chuàng)作于2023年2月先序遍歷：ABCDEFGHIJ中序遍歷：BCDAFEHJIGABCDEFGH

IJ第54頁，課件共69頁，創(chuàng)作于2023年2月說明先序遍歷森林等同于先序遍歷該森林對應(yīng)的二叉樹中序遍歷森林等同于中序遍歷該森林對應(yīng)的二叉樹當(dāng)用二叉鏈表作樹和森林的存儲結(jié)構(gòu)時(shí)，樹和森林的先序遍歷和后序遍歷，可用二叉樹的先序遍歷和中序遍歷算法來實(shí)現(xiàn)。第55頁，課件共69頁，創(chuàng)作于2023年2月6.6赫夫曼樹及其應(yīng)用路徑長度：

從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑,路徑上的分支數(shù)目稱做路徑長度。樹的路徑長度：從樹根到每一結(jié)點(diǎn)的路徑長度之和。結(jié)點(diǎn)的帶權(quán)路徑長度：從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上權(quán)的乘積。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。通常記作：nWPL=∑ωkιkk=1

第56頁，課件共69頁，創(chuàng)作于2023年2月6.6.1最優(yōu)二叉樹（赫夫曼樹）定義：假設(shè)有n個(gè)權(quán)值{ω1,ω2,

…,ωn}，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹,每個(gè)葉子結(jié)點(diǎn)帶權(quán)為ωi,則其中：帶權(quán)路徑長度WPL最小的二叉樹稱做最優(yōu)二叉樹或赫夫曼樹。第57頁，課件共69頁，創(chuàng)作于2023年2月[例]：下面三棵二叉樹的四個(gè)葉子結(jié)點(diǎn)a,b,c,d的權(quán)值為7、5、2、4abcd7524abcd7524cdab7524(a)WPL=7×2+5×2+2×2+4×2=36(b)WPL=7×3+5×3+2×1+4×2=46(c)WPL=7×1+5×2+2×2+4×2=35第58頁，課件共69頁，創(chuàng)作于2023年2月赫夫曼算法的基本思想根據(jù)給定的n個(gè)權(quán)值{ω1,ω2,…,ωn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn}其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為ωi的根結(jié)點(diǎn),其左右子樹均空。在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一顆新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中。重復(fù)上述兩個(gè)步驟，直到F只含一棵樹為止。這棵樹便是赫夫曼樹。第59頁，課件共69頁，創(chuàng)作于2023年2月構(gòu)造赫夫曼樹舉例cdab7524abc2d457abc6d57abcd117第60頁，課件共69頁，創(chuàng)作于2023年2月6.2.2赫夫曼編碼在電文傳輸中，需要將電文中出現(xiàn)的每個(gè)字符進(jìn)行二進(jìn)制編碼。在設(shè)計(jì)編碼時(shí)需要遵守兩個(gè)原則：發(fā)送方傳輸?shù)亩M(jìn)制編碼，到接收方解碼后必須具有唯一性，即解碼結(jié)果與發(fā)送方發(fā)送的電文完全一樣發(fā)送的二進(jìn)制編碼盡可能地短第61頁，課件共69頁，創(chuàng)作于2023年2月編碼方式等長編碼：將給定字符集C中每個(gè)字符的碼長相同【例】設(shè)待壓縮的數(shù)據(jù)文件共有