數(shù)據(jù)結構 第六章樹和二叉樹

數(shù)據(jù)結構第六章樹和二叉樹第一頁，共六十九頁，編輯于2023年，星期三第六章樹和二叉樹6.1樹的定義和基本術語6.2二叉樹6.2.1二叉樹的定義6.2.2二叉樹的性質6.2.3二叉樹的存儲結構6.3遍歷二叉樹和線索二叉樹6.3.1遍歷二叉樹6.3.2線索二叉樹6.4樹和森林6.4.1樹的存儲結構6.4.2森林與二叉樹的轉換6.6赫夫曼樹及其應用6.6.1最優(yōu)二叉樹(赫夫曼樹)6.6.2赫夫曼編碼第二頁，共六十九頁，編輯于2023年，星期三樹形結構是一類重要的非線性結構。樹形結構是結點之間有分支，并具有層次關系的結構。它非常類似于自然界中的樹。第三頁，共六十九頁，編輯于2023年，星期三ABCDEFGH樹形結構——結點間具有分層次的連接關系HBCDEFGA第四頁，共六十九頁，編輯于2023年，星期三6.1樹的定義和基本術語

樹(Tree)是n(n>0)個結點的有限集合T，它滿足如下條件：有且僅有一個稱為根(Root)的結點。其余結點可劃分為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年，星期三線性結構

（一對一關系）

樹結構（一對多關系）

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

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

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

樹中其它結點(一個前驅、一個后繼)

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

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

數(shù)據(jù)關系R：若D為空集，則稱為空樹;若D僅含一個數(shù)據(jù)元素，則R為空集，否則R＝｛H｝，H是如下二元關系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關系H下無前驅；（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）對應于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上的二元關系，（Di,{Hi}）是一棵符合本定義的樹，稱為根root的子樹。第九頁，共六十九頁，編輯于2023年，星期三樹的抽象數(shù)據(jù)類型定義--基本操作（之一）

InitTree(&T)；操作結果：構造空樹T。

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

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

ClearTree(&T)；初始條件：樹T存在。操作結果：將樹T清為空樹。第十頁，共六十九頁，編輯于2023年，星期三樹的抽象數(shù)據(jù)類型定義--基本操作（之二）

TreeEmpty(T)

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

TreeDepth(T)

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

Root(T)

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

Value(T,cur_e)；初始條件：樹T存在，cur_e是T中某個結點。操作結果：返回cur_e的值。第十一頁，共六十九頁，編輯于2023年，星期三樹的抽象數(shù)據(jù)類型定義--基本操作（之三）

Assign(T，cur_e，value)

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

Parent(T，cur_e)

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

LeftChild(T，cur_e)

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

RightSibling(T，cur_e)

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

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

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

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

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

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

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

rchilddatalchilddataparentlchildrchilddatalchildrchildparent第二十二頁，共六十九頁，編輯于2023年，星期三鏈式存儲結構示例注意：

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

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

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

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

DLR——先（根）序遍歷，

LDR——中（根）序遍歷，

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

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

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

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

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

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

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

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

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{//根指針退棧，訪問根結點，遍歷右子樹

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

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

0lchild域指示其左孩子ltag={1lchild域指示其前驅

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

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

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

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

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

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

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

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

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

CD∧

E∧

FG∧

H∧

K∧123∧

45∧

6∧

789∧

第四十四頁，共六十九頁，編輯于2023年，星期三6.4.1樹的存儲結構孩子表示法（鏈式存儲）

typedefstructCTNode{//孩子結點結構

intchild;structCTNode*next;}*ChildPtr;typedefstruct{ //雙親結點結構

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

}CTBox;typedefstruct{ //樹結構

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

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

ELemTypedata;

structCSNode*firstchild,*nextsibling;

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

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

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

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

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

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