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

數(shù)據(jù)結(jié)構(gòu)第六章樹和二叉樹第一頁，共六十九頁，編輯于2023年，星期三第六章樹和二叉樹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赫夫曼編碼第二頁，共六十九頁，編輯于2023年，星期三樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹形結(jié)構(gòu)是結(jié)點之間有分支，并具有層次關(guān)系的結(jié)構(gòu)。它非常類似于自然界中的樹。第三頁，共六十九頁，編輯于2023年，星期三ABCDEFGH樹形結(jié)構(gòu)——結(jié)點間具有分層次的連接關(guān)系HBCDEFGA第四頁，共六十九頁，編輯于2023年，星期三6.1樹的定義和基本術(shù)語

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

T3J

MB

E

LKT1F第五頁，共六十九頁，編輯于2023年，星期三樹的表示方法1）樹形圖法

2）嵌套集合法

3）廣義表形式

4）凹入表示法(A(B,C(E,F),D(G)))ABCDEFGABCEFDGABDGEFC第六頁，共六十九頁，編輯于2023年，星期三線性結(jié)構(gòu)

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

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

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

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

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

樹中其它結(jié)點(一個前驅(qū)、一個后繼)

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

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

數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹;若D僅含一個數(shù)據(jù)元素，則R為空集，否則R＝｛H｝，H是如下二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；（2）若D－｛root｝≠Ф，則存在D－｛root｝的一個劃分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>｝有唯一的一個劃分H1,H2,...,Hm（m＞0），對任意j≠k（1≤j,k≤m）有Hj∩Hk=Ф，且對任意的i（1≤i≤m），Hi是Di上的二元關(guān)系，（Di,{Hi}）是一棵符合本定義的樹，稱為根root的子樹。第九頁，共六十九頁，編輯于2023年，星期三樹的抽象數(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清為空樹。第十頁，共六十九頁，編輯于2023年，星期三樹的抽象數(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中某個結(jié)點。操作結(jié)果：返回cur_e的值。第十一頁，共六十九頁，編輯于2023年，星期三樹的抽象數(shù)據(jù)類型定義--基本操作（之三）

Assign(T，cur_e，value)

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

Parent(T，cur_e)

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

LeftChild(T，cur_e)

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

RightSibling(T，cur_e)

初始條件：樹T存在，cur_e是T中某個結(jié)點。操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則函數(shù)值為“空”。第十二頁，共六十九頁，編輯于2023年，星期三樹的抽象數(shù)據(jù)類型定義--基本操作（之四）

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

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

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

②對于完全二叉樹,若某結(jié)點無左孩子,則必?zé)o右孩子,該結(jié)點為葉結(jié)點。第十七頁，共六十九頁，編輯于2023年，星期三1231145891213671014151231145891267101234567123456第十八頁，共六十九頁，編輯于2023年，星期三性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為log2n+1性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號，則對任一結(jié)點i(1≤i≤n)，有：

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

(最壞的情況下，一個深度為k且只有k個結(jié)點的右單支樹需要2k-1個結(jié)點的存儲空間)ABCDEE?D?CBA第二十一頁，共六十九頁，編輯于2023年，星期三鏈?zhǔn)酱鎯Y(jié)構(gòu)typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;

rchilddatalchilddataparentlchildrchilddatalchildrchildparent第二十二頁，共六十九頁，編輯于2023年，星期三鏈?zhǔn)酱鎯Y(jié)構(gòu)示例注意：

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

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

StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲結(jié)構(gòu),Visit是對結(jié)點操作的應(yīng)用函數(shù)。//中序遍歷二叉樹T，一旦Visit()失敗，則操作失敗。StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲結(jié)構(gòu),Visit是對結(jié)點操作的應(yīng)用函數(shù)。//后序遍歷二叉樹T，一旦Visit()失敗，則操作失敗。StatusLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉鏈表存儲結(jié)構(gòu),Visit是對結(jié)點操作的應(yīng)用函數(shù)。//層序遍歷二叉樹T，一旦Visit()失敗，則操作失敗。第二十五頁，共六十九頁，編輯于2023年，星期三6.3遍歷二叉樹

按某條搜索路徑巡訪二叉樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。ABCDGEF第二十六頁，共六十九頁，編輯于2023年，星期三假如以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點和遍歷右子樹，遍歷整個二叉樹則有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。若規(guī)定先左后右，則只有前三種情況，分別規(guī)定為：

DLR——先（根）序遍歷，

LDR——中（根）序遍歷，

LRD——后（根）序遍歷。第二十七頁，共六十九頁，編輯于2023年，星期三先序遍歷二叉樹的操作定義若二叉樹為空，則空操作；否則（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。

ABCDFEGABCDGEF第二十八頁，共六十九頁，編輯于2023年，星期三中序遍歷二叉樹的操作定義若二叉樹為空，則空操作；否則（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。

CBDFAGEABCDGEF第二十九頁，共六十九頁，編輯于2023年，星期三后序遍歷二叉樹的操作定義若二叉樹為空，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。

CFDBGEAABCDGEF第三十頁，共六十九頁，編輯于2023年，星期三例：已知結(jié)點的先序序列和中序序列，求整棵二叉樹先序序列：ABCDEFG中序序列：CBEDAFGAC

B

E

DFGABCDEFGABCFDEG第三十一頁，共六十九頁，編輯于2023年，星期三先序遍歷二叉樹的遞歸算法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第三十二頁，共六十九頁，編輯于2023年，星期三作業(yè)分別寫出中序遍歷二叉樹和后序遍歷二叉樹的遞歸算法已知一棵二叉樹的中序和后序序列如下，畫出此二叉樹并寫出該二叉樹的先序遍歷序列。中序序列：A,B,C,D,J,E,F,H,G,I

后序序列：B,C,J,D,A,H,I,G,F,E第三十三頁，共六十九頁，編輯于2023年，星期三中序遍歷二叉樹的非遞歸算法基本思想

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

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

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

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

if(!StackEmpty(S)){ //訪問結(jié)點，向右一步

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

}//if }//whilereturnOK;}//InOrderTraverse算法6.2第三十五頁，共六十九頁，編輯于2023年，星期三算法6.3StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}//根指針進棧，遍歷左子樹

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

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

BinaryTree)。對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。第三十七頁，共六十九頁，編輯于2023年，星期三線索二叉樹結(jié)點的結(jié)構(gòu):其中，ltag和rtag是增加的兩個標(biāo)志域，用來區(qū)分結(jié)點的左、右指針域是指向其左、右孩子的指針，還是指向其前趨或后繼的線索。

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

0rchild域指示其右孩子rtag={1rchild域指示其后繼datalchildrchildrtagltag第三十八頁，共六十九頁，編輯于2023年，星期三中序線索二叉樹的表示第三十九頁，共六十九頁，編輯于2023年，星期三注意：

圖中的實線表示指針，虛線表示線索。

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

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

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

第四十頁，共六十九頁，編輯于2023年，星期三6.4樹和森林樹的存儲結(jié)構(gòu)雙親表示法（靜態(tài)鏈表存儲）：以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中附設(shè)一個指示器指示其雙親結(jié)點在(靜態(tài))鏈表中的位置

第四十一頁，共六十九頁，編輯于2023年，星期三雙親表示法舉例RADEFCBGKHR-1A0B0C0D1E1F3G6H6K60123456789數(shù)組下標(biāo):第四十二頁，共六十九頁，編輯于2023年，星期三#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;//雙親位置域

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

}PTree;*便于涉及雙親的操作；*求結(jié)點的孩子時需要遍歷整棵樹。第四十三頁，共六十九頁，編輯于2023年，星期三孩子鏈表存儲表示舉例RADEFCBGKH0123456789數(shù)組下標(biāo):RAB∧

CD∧

E∧

FG∧

H∧

K∧123∧

45∧

6∧

789∧

第四十四頁，共六十九頁，編輯于2023年，星期三6.4.1樹的存儲結(jié)構(gòu)孩子表示法（鏈?zhǔn)酱鎯Γ?/p>

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

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

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

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

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

}CTree;*便于涉及孩子的操作；*求結(jié)點的雙親時不方便。第四十五頁，共六十九頁，編輯于2023年，星期三6.4.1樹的存儲結(jié)構(gòu)孩子兄弟表示法：又稱二叉樹表示法，或二叉鏈表表示法。記以二叉鏈表作樹的存儲結(jié)構(gòu)。鏈表中結(jié)點的兩個鏈域分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點，分別命名為firstchild域和nextsibling域。typedefstructCSNode{

ELemTypedata;

structCSNode*firstchild,*nextsibling;

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

IJ第五十三頁，共六十九頁，編輯于2023年，星期三先序遍歷：ABCDEFGHIJ中序遍歷：BCDAFEHJIGABCDEFGH

IJ第五十四頁，共六十九頁，編輯于2023年，星期三說明先序遍歷森林等同于先序遍歷該森林對應(yīng)的二叉樹中序遍歷森林等同于中序遍歷該森林對應(yīng)的二叉樹當(dāng)用二叉鏈表作樹和森林的存儲結(jié)構(gòu)時，樹和森林的先序遍歷和后序遍歷，可用二叉樹的先序遍歷和中序遍歷算法來實現(xiàn)。第五十五頁，共六十九頁，編輯于2023年，星期三6.6赫夫曼樹及其應(yīng)用路徑長度：

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

第五十六頁，共六十九頁，編輯于2023年，星期三6.6.1最優(yōu)二叉樹（赫夫曼樹）定義：假設(shè)有n個權(quán)值{ω1,ω2,

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