大學教程(零起點)數(shù)據(jù)結構- 樹和二叉樹

上傳人：a*** IP屬地：湖北上傳時間：2023-02-05 格式：PPT 頁數(shù)：169 大?。?.82MB 積分：28 舉報 版權申訴

已閱讀5頁，還剩164頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

復習前節(jié)1、數(shù)據(jù)結構的基本概念2、順序表、鏈表3、順序棧、鏈棧4、順序隊、鏈隊5、順序串、鏈串6、數(shù)組和廣義表線性表線性表的推廣樹的推廣1第五章樹和二叉樹5.1樹的概念和術語5.2二叉樹5.3二叉樹的運算5.4線索二叉樹5.5樹和森林5.6哈夫曼樹及其應用2本章項目：電文編碼3文字電文編碼電波譯碼摩爾斯電碼（又譯為摩斯電碼）是一種時通時斷的信號代碼，這種信號代碼通過不同的排列順序來表達不同的英文字母、數(shù)字和標點符號等。它由美國人艾爾菲德·維爾發(fā)明（1835年）。4網(wǎng)絡信息傳輸：文字數(shù)字編碼電信號電文編碼發(fā)送者數(shù)字編碼文字電文編碼接收者你好0101010101你好核心問題：電文如何編碼稱為01串？？51、樹的概念2、樹的專業(yè)術語3、二叉樹的概念4、哈夫曼樹和哈夫曼編碼6789自然中的樹抽象的樹知識點1：樹的概念10旋轉后11適當進行調(diào)整ABCDEFGHI12數(shù)據(jù)結構中樹的形態(tài)，具有分層特點ABCDEFGHI13某姓氏族譜14ABCDEFGHIJKLMNOPQRSTUVWXYZ……..對樹中的結點給定一個符號名稱，具有一對多的特點15樹描述的是一種層次結構，是一種一對多的邏輯關系FGIJABCEDH16樹(Tree)是n(n>=0)個結點的有限集T。n=0時稱為空樹。對于非空樹有且僅有一個稱為根(ROOT)的結點；n>1其余結點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm,其中每個集合又是一棵樹，稱為子樹知識點1：樹的定義FGIJABCEDH根根17樹的其他表示形式ABCDEFHGM18結點：數(shù)據(jù)元素的內(nèi)容及其指向其子樹根的分支結點的度（Degree）：結點擁有的子樹的數(shù)目。樹的度：一棵樹內(nèi)各結點的度的最大值；知識點3：樹的基本術語ABCDEFHGMA、B、C、D、E、F、G、H、M均稱為結點A結點的度為2C結點的度為3M結點的度為0樹的度為319葉子（終端結點Leaf），非終端結點：度為0的結點稱為葉子結點；度不為0的結點稱為非終端結點。ABCDEFHGM知識點3：樹的基本術語20孩子，雙親，兄弟，堂兄：結點的子樹的根稱為該結點的孩子；該結點稱為孩子的雙親；同一個雙親的孩子之間互稱兄弟；雙親在同一層的結點互為堂兄弟。ABCDEFHGMA是B、C的雙親B、C是A的孩子B、C是兄弟關系E、F是堂兄弟關系21路徑：若樹中存在一個序列k1，k2…kn，使得ki是ki+1的雙親，則稱該結點序列為k1到kn的一條路徑。路徑長度：這些節(jié)點經(jīng)過的邊的條數(shù)ABCDEFHGM序列：ABDME序列：ABDM序列：ACF是路徑非路徑是路徑22子孫，祖先：以某結點為根的子樹中的所有結點都被稱為是該結點的子孫。從根結點到該結點路徑上的所有結點稱為該結點的祖先。ABCDEFHGM23結點的層數(shù)：樹中根結點的層次為1，根結點子樹的根為第2層，以此類推。樹的高度（深度）：樹中所有結點層次的最大值ABCDEFHGM24森林：多棵互不相交的樹的集合構成森林BCDEFHGM三棵樹構成的森林IJA25結點結點的度(Degree)葉子（Leaf)或終端結點分支結點或非終端結點樹的度層次(Level)樹的深度(Depth)孩子（child)雙親（Parent)兄弟(Sibling)祖先子孫路徑ABCDEFHGM26ABCDEFGHIJKLM結點A的度：3結點B的度：2結點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結點A的孩子：B，C，D結點B的孩子：E，F(xiàn)結點I的雙親：D結點L的雙親：E結點B，C，D為兄弟結點K，L為兄弟樹的度：3結點A的層次：1結點M的層次：4樹的深度：4結點F，G為堂兄弟結點G的祖先是結點A，C結點D的子孫為H,I,J,M27知識點3：二叉樹的概念二叉樹(BinaryTree)：或者是一棵空樹，或者是一棵由一個根結點和兩棵互不相交的左子樹和右子樹所組成的非空樹，左子樹和右子樹同樣也都是二叉樹ABCDEFHM28特征：每個結點最多只有兩棵子樹子樹有左右之分，次序不能任意顛倒，只有一棵子樹時也必須分清是左子樹還是右子樹ABCACB29二叉樹的五種基本形態(tài)AAAA(a)(b)(c)(d)(e)(a)空二叉樹(b)單結點二叉樹(c)右子樹為空(d)左子樹為空(e)左、右子樹非空二叉樹的五種基本形態(tài)30性質(zhì)1.非空二叉樹的第i層上至多有2i-1個結點（i1）證明：i=1,只有根結點，顯然成立設i=k時成立，最多有2k-1個結點

當i=k+1時，最多的結點個數(shù)：

2k-1*2=2k-1+1=2k=2(

k+1)-1二叉樹的性質(zhì)12345678910111213141531性質(zhì)2.深度為k的二叉樹至多有2k-1個結點(k1)

證明：二叉樹的結點個數(shù)為：

1+2+…+2k-1=2k-112345678910111213141532性質(zhì)3.對任何一棵二叉樹T，如果其終端結點數(shù)為n0，度為2的結點數(shù)為n2，則n0=n2+1。證明：設n1為T中度為1的結點數(shù)，則總結點數(shù)：

n=n0+n1+n2(1)

另：根據(jù)各個結點的前驅和后繼情況度數(shù)為1的結點表示有一個孩子結點度數(shù)為2的結點表示有兩個孩子節(jié)點所以樹中孩子結點總數(shù)為

n1+2*n2(2)由(1)和(2)有：n1+2*n2=n0+n1+n2-1故

n0=n2+1;33考慮到有序性，任一結點在樹中都有確切的位置，因此可以對滿二叉樹進行編號。編號方式為：從上到下，從左到右。滿二叉樹(FullBinaryTree)深度為k且有2k-1個結點的二叉樹12345678910111213141534完全二叉樹若一顆深度為k的二叉樹，其k-1層是一顆滿二叉樹，而最下面一層，即第k層上的結點都集中在該層最左邊的若干位置上，則稱作完全二叉樹。abcdefghij35894101151213614157213894101152112673(a)滿二叉樹(b)完全二叉樹1362455674213(c)非完全二叉樹圖6-4特殊形態(tài)的二叉樹361.滿二叉樹一定是一棵完全二叉樹，反之完全二叉樹不一定是一棵滿二叉樹。(√)2.滿二叉樹的葉子結點全部在最底層，而完全二叉樹的葉子結點可以分布在最下面兩層。

(√)判斷題37性質(zhì)4.具有n個結點的完全二叉樹的深度:k=log2(n)+1證明：假設n個結點的完全二叉樹的深度為k，則n的值應大于深度為k-1的滿二叉樹的結點數(shù)2k-1-1，小于等于深度為k的滿二叉樹的結點數(shù)2k-1，即

2k-1-1<n≤2k-1進一步可推導出

2k-1≤n<2k兩邊取對數(shù)后，有

k-1≤log2(n)<k進一步可推導出

log2(n)<k≤log2(n)+1因為k是整數(shù)，所以有k＝log2(n)+138（a）如果i=1,此結點為根結點，無雙親；若i>1,則其雙親結點是i/2。（b）如果2i>n,則結點i無左孩子，i為葉子結點,否則其左孩子是結點2i。（c）如果2i+1>n，則結點i無右孩子，否則其右孩子是結點2i+1。性質(zhì)5.如果將一棵有n個結點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結點編號1,2,3,…,n,則對任一結點i（1in）有abcdefghij391.一棵樹高為K的完全二叉樹至少有（）個結點A.2k–1B.2k-1–1C.2k-1

D.2k習題答案：C相當于k-1層的滿二叉樹加一個結點K-1層滿二叉樹結點個數(shù)為：2k-1-1402.已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹有______個葉子結點。習題結點總個數(shù)n=2+3+4+x結點數(shù)為所有結點的度數(shù)之和加1n=2*1+3*2+4*3+x*0+1（根節(jié)點）故x=12答案：1241習題3.有關二叉樹下列說法正確的是（）A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結點的度為2D．二叉樹中任何一個結點的度都為2答案：B424、如果知道完全二叉樹上有1001個結點，其葉子結點的個數(shù)為多少？

深度為9的節(jié)點數(shù)是511，深度為10的節(jié)點數(shù)是1023，該樹為10層。最后一層節(jié)點是1001-511=490（均是葉子節(jié)點），最后一層490個節(jié)點對應的第9層得父節(jié)點有245個，第9層節(jié)點共有256個節(jié)點，所以第9層葉子節(jié)點有256-245=11個總的葉子節(jié)點數(shù)為490+11=501習題43習題5、設樹T的度為4，其中度為1，2，3和4的結點個數(shù)分別為4，2，1，1則T中的葉子數(shù)為（）A．5B．6C．7D．8445.2.3二叉樹的存儲結構順序存儲結構鏈式存儲結構45abcdefghij二叉樹的順序存儲結構整個二叉樹可以按照從上到下，從左到右的順序編號46將一棵二叉樹按完全二叉樹順序存放到一維數(shù)組中abcdefghm123456789101112131415

0123456789101112131415abcdefghm47順序存儲結構舉例ABCABC????A?B???C48對于一棵二叉樹,若采用順序存貯時,當它為完全二叉樹時,比較方便;若為非完全二叉樹,將會浪費大量存貯單元。因此，對于非完全二叉樹，宜采用下面的鏈式存儲結構。49鏈式存儲結構二叉鏈表三叉鏈表50二叉鏈表lchilddatarchildABDCEFADEBCFBinTree51二叉鏈表的定義struct

btnode

{//結點結構

datatypedata;

struct

btnode*lchild,*rchild;};結點結構:lchilddatarchild52ADEBCFBinTree問題：如何找到某結點的子樹？如何找到某結點的雙親？53三叉鏈表lchilddatarchildparentADEBCFBinTree54三叉鏈表的定義struct

btnode

{//結點結構

datatypedata;

struct

btnode*lchild,*rchild}；結點結構:lchilddatarchildparent,*parent;;55鏈式存儲的缺點；

若一棵二叉樹有n個結點,采用二叉鏈表作存貯結構時,共有2n個指針域,其中只有n-1個指針指向左右孩子,其余n+1個指針為空,沒有發(fā)揮作用。565.3.1二叉樹的生成建立二叉樹的存儲結構鏈式存儲結構——二叉鏈表1、按廣義表表示二叉樹結構生成二叉鏈表的算法2、按完全二叉樹的層次順序依次輸入結點信息建立二叉鏈表的算法5.3二叉樹的運算571、按廣義表表示二叉樹結構生成二叉鏈表的算法（A（B（,D（E,F））,C））靠近左括號的結點是在左子樹上，而逗號右邊的結點是在右子樹上。ACBDFE582、按完全二叉樹的層次順序依次輸入結點信息建立二叉鏈表的算法首先對一般的二叉樹添加若干個虛點，使其成為完全二叉樹59605.3.2二叉樹的遍歷遍歷一棵二叉樹是按某種次序系統(tǒng)地“訪問”二叉樹上的所有結點，使每個結點恰好被“訪問”一次。先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法“訪問”的含義可以很廣，如：輸出結點的信息等61若二叉樹為空樹，則空操作；否則，（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：AECBGL62若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。中（根）序的遍歷算法：AECBGL63若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。后（根）序的遍歷算法：AECBGL64先（根）序的遍歷算法：voidPreorder(bitreptr

bt){//先序遍歷二叉樹

if(bt！=NULL){visit(bt);Preorder(bt->lchild);Preorder(bt->rchild);

}}AECBGL65中（根）序的遍歷算法：voidInorder(bitreptr

bt){//中序遍歷二叉樹

if(bt！=NULL){

Inorder(bt->lchild);visit(bt);

Inorder(bt->rchild);

}}AECBGL66后（根）序的遍歷算法：voidPostorder(bitreptr

bt){//后序遍歷二叉樹

if(bt！=NULL){

Postorder(bt->lchild);

Postorder(bt->rchild);visit(bt);

}}AECBGL67二叉樹的遍歷算法：AECBGLDLRLDR、LRD、DLR68ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

EHGKFDCBHKGFE

A69習題

1.給定二叉樹如下圖所示。設N代表二叉樹的根，L代表根結點的左子樹，R代表根結點的右子樹。若遍歷后的結點序列為3,1,7,5,6,2,4，則其遍歷方式是LRNB.NRLC.RLND.RNL答案：D70習題

2.假設前序序列為ABDGHCEFI，中序序列為GDHBAECIF，請確定一棵二叉樹ABDGHCEFIGDHBAECIF前序中序71習題

3.試找出滿足下列條件的二叉樹1）先序序列與中序序列相同2）中序序列與后序序列相同3）先序序列與后序序列相同答案1）不含左子樹的二叉樹2）不含右子樹的二叉樹3）空二叉樹或只含根結點的二叉樹72習題

4.某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是()的二叉樹

A．空或只有一個結點B.高度等于其結點數(shù)C．任一結點無左孩子D.任一結點無右孩子先序：根左右后序：左右根答案：B732、非遞歸遍歷算法利用棧（1）、利用棧的非遞歸中序遍歷74中序非遞歸算法演示ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問：C(4)75pABCDEFGiP->A訪問：CB(5)ABCDEFGiP->AP->D訪問：CBp(6)ABCDEFGiP->AP->DP->E訪問：CBp(7)ABCDEFGiP->AP->D訪問：CBEp(8)76ABCDEFGiP->AP->DP->G訪問：CBEP=NULL(9)ABCDEFGiP->A訪問：CBEGDp(11)ABCDEFGiP->AP->F訪問：CBEGDp(12)ABCDEFGiP->AP->D訪問：CBEGp(10)77ABCDEFGiP->A訪問：CBEGDFp=NULL(13)ABCDEFGi訪問：CBEGDFAp(14)ABCDEFGi訪問：CBEGDFAp=NULL(15)785.3.3二叉樹的應用舉例例5.2已知二叉樹的前序和中序遍歷序列（中序和后序遍歷序列），確定二叉樹。已知二叉樹的前序和中序遍歷序列在前序序列中尋找根到中序序列中分左右規(guī)律已知二叉樹的中序和后序遍歷序列在后序序列中尋找根到中序序列中分左右795.3.3二叉樹的應用舉例例5.3已知二叉樹的鏈式存儲結構，求二叉樹的深度。例5.4以二叉鏈表為存儲結構，試編寫在二叉樹中查找值為x的結點以及求x所在結點在樹中層數(shù)的算法805.4線索二叉樹81ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA一、何謂線索二叉樹？遍歷二叉樹的結果是，求得結點的一個線性序列82ADEBCFrootABDCEF缺點：空指針較多，找某個序列的前序后繼不方便83指向某遍歷序列中的“前驅”和“后繼”的指針，稱作“線索”包含“線索”的存儲結構，稱作“線索鏈表”與其相應的二叉樹，稱作“線索二叉樹”利用鏈表中空的左指針指向遍歷序列的前驅利用鏈表中空的右指針指向遍歷序列的后繼8485對線索鏈表中結點的約定：在二叉鏈表的結點中增加兩個標志域，標志二叉樹中的左右指針指向的是前驅還是后繼Tag值為1表示存的是線索值為0表示存的是孩子86Tag值為1表示存的是線索值為0表示存的是孩子中序線索87Tag值為1表示存的是線索值為0表示存的是孩子中序線索88typedef

struct

BiThrNod{

TElemTypedata;

struct

BiThrNode*lchild,*rchild;

PointerThr

LTag,RTag;}BiThrNode,*BiThrTree;線索鏈表的類型typedef

enum{Link,Thread}PointerThr;Link值為0:指針，Thread值為1:線索89二、線索鏈表的遍歷算法:中序線索由于在線索鏈表中添加了遍歷中得到的“前驅”和“后繼”的信息，從而簡化了遍歷的算法。90中序線索化鏈表的遍歷算法

※中序遍歷的第一個結點？

※在中序線索樹中結點的后繼是哪個結點？左子樹上處于”最左下”(沒有左子樹)的結點。若某節(jié)點無右子樹，則其后繼是右指針所指結點否則為對其右子樹進行中序遍歷時訪問的第一個結點。91若某節(jié)點無右子樹，則其后繼是右指針所指結點ADEBCFroot925.5樹和森林樹的存儲結構樹和二叉樹之間的轉換森林和二叉樹的轉換樹和森林的遍歷93樹的存儲結構ABECDF雙親表示法

孩子鏈表表示法

孩子兄弟鏈表表示法

94雙親表示法樹的雙親表示法主要描述的是結點的雙親關系順序表示，存放頂點和雙親信息HDEFGBCA雙親表示法缺點：求結點的孩子時需要遍歷整個結構01234567DataParent

-1

41234095孩子表示法來存儲方法：將每個結點的孩子排列起來，形成一個帶表頭（裝父親結點）的線性表（n個結點要設立n個鏈表），再將n個表頭用數(shù)組存放起來，這樣就形成一個混合結構。HDEFGBCA孩子表示法

C^A

E^BC^D^

H^EF^G^H^0123456796HDEFGBCA帶雙親的孩子表示法ParentData01234567ABCDEFGH-10011444

H^^^^^^帶雙親的孩子表示法97用孩子兄弟表示法來存儲方法：用二叉鏈表來存儲樹，但鏈表的兩個指針域含義不同。firstchilddatanextsibling指向結點的第一個孩子指向結點的第一個兄弟HDEFGBCA孩子兄弟表示法AB^DC^^^EF^^GH^^^98請畫出該樹的孩子鏈表結構圖請畫出該樹的孩子兄弟鏈表結構圖雙親表示法結構圖995.5.2樹、森林與二叉樹的轉換1、樹（森林）到二叉樹轉換—唯一的二叉樹與之對應(1)加線：在各兄弟結點之間用虛線相連。(2)抹線：對每個結點僅保留它與其最左一個孩子的連線，抹去該結點與其它孩子之間的連線。(3)旋轉：把虛線改為實線從水平方向向下旋轉45℃，成右斜下方向。原樹中實線成左斜下方向。這樣就樹的形狀成呈現(xiàn)出一棵二叉樹。100ABDCEGFHIMJNKL1、加線2、抹線1011、加線ABDCEGFHIMJNKL2、抹線3、旋轉102ABDCEGFHIMJNKLKABDCEGFHIMJNL1035.5.2樹、森林與二叉樹的轉換2、二叉樹到樹（森林）轉換二叉樹必須是沒有右子樹的二叉樹。并非隨便一棵二叉樹都能還原成一般樹。其實現(xiàn)過程：（１）加線：若某結點i是雙親結點的左孩子，則將該結點i的右孩子以及當且僅當連續(xù)地沿著右孩子的右鏈不斷搜索到所有右孩子，都分別與結點i的雙親結點用虛線連接。（２）抹線：把原二叉樹中所有雙親結點與其右孩子的連線抹去。（３）進行整理：把虛線改為實線，把結點按層次排列。104ABCDEFGHIJKLABCDEFGHIJKLCDABCDEFGHIJKLC105DEFGHIJLABCKFILCABEGHJKD習題二叉樹到森林的轉換1065.5.3

樹和森林的遍歷1樹的遍歷

由樹結構的定義可知，樹的遍歷有二種方法。⑴

先序遍歷：先訪問根結點，然后依次先序遍歷完每棵子樹。如右圖的樹，先序遍歷的次序是：ABCDEFGIJHK⑵

后序遍歷：先依次后序遍歷完每棵子樹，然后訪問根結點。如右圖的樹，后序遍歷的次序是：CDBFGIJHEKAABDCKGJIFHE樹107說明：◆樹的先序遍歷實質(zhì)上與將樹轉換成二叉樹后對二叉樹的先序遍歷相同?！魳涞暮笮虮闅v實質(zhì)上與將樹轉換成二叉樹后對二叉樹的中序遍歷相同。1082森林的遍歷

設F={T1,T2,?,Tn}是森林，對F的遍歷有二種方法。⑴先序遍歷：按先序遍歷樹的方式依次遍歷F中的每棵樹。⑵中序遍歷：按后序遍歷樹的方式依次遍歷F中的每棵樹。109習題設X是樹T中的一個非根結點，B是T所對應的二叉樹。在B中，X是其雙親的右孩子，下列結論正確的是()。A.在樹T中，X是其雙親的第一個孩子B.在樹T中，X一定無右邊兄弟C.在樹T中，X一定是葉子結點D.在樹T中，X一定有左邊兄弟答案：D110中序遍歷：BDCEAFHG

后序遍歷：DECBHGFA111112113二叉樹的存儲結構順序存儲結構整個二叉樹可以按照從上到下從左到右的順序編號鏈式存儲結構二叉鏈表三叉鏈表lchilddatarchildparentlchilddatarchild二叉樹的遍歷：前序遍歷、中序遍歷、后序遍歷樹的存儲結構：雙親表示法

孩子鏈表表示法

孩子兄弟鏈表表示法

01234567DataParent

-1

4HDEFGBCA

C^A

E^BC^D^

H^EF^G^H^01234567AB^DC^^^EF^^G^114樹、森林與二叉樹的轉換1、樹（森林）到二叉樹轉換—唯一的二叉樹與之對應(1)加線：在各兄弟結點之間用虛線相連。(2)抹線：對每個結點僅保留它與其最左一個孩子的連線，抹去該結點與其它孩子之間的連線。(3)旋轉：2、二叉樹到樹（森林）轉換(1)加線：若某結點i是雙親結點的左孩子，則將該結點i的右孩子以及當且僅當連續(xù)地沿著右孩子的右鏈不斷搜索到所有右孩子，都分別與結點i的雙親結點用虛線連接。(2)抹線：把原二叉樹中所有雙親結點與其右孩子的連線抹去。(3)進行整理：1155.6哈夫曼樹及其應用赫夫曼(Huffman)樹又稱最優(yōu)樹，是一類帶權路徑長度最短的樹，有著廣泛的應用。1

基本概念①結點路徑：從樹中一個結點到另一個結點的之間的分支構成這兩個結點之間的路徑。②路徑長度：結點路徑上的分支數(shù)目稱為路徑長度。③樹的路徑長度：從樹根到每一個結點的路徑長度之和。116如圖所示的樹A到F：結點路徑AEF；路徑長度(即邊的數(shù)目)2

；樹的路徑長度：31+52+23=19

ABDCKGJIFHE樹117④結點的帶權路徑長度：從該結點的到樹的根結點之間的路徑長度與結點的權(值)的乘積。權(值)：各種開銷、代價、頻度等的抽象稱呼。⑤

樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和，記做：其中：n為葉子結點的個數(shù)；wi為第i個結點的權值；li為第i個結點的路徑長度。⑥

Huffman樹：具有n個葉子結點(每個結點的權值為wi)的二叉樹不止一棵，但在所有的這些二叉樹中，必定存在一棵WPL值最小的樹，稱這棵樹為Huffman樹(或稱最優(yōu)樹)

。118例有4個結點，權值分別為8，5，2，4，構造有4個葉子結點的二叉樹abcd8524WPL=8*2+5*2+2*2+4*2=38dcab2485WPL=8*3+5*3+2*1+4*2=49abcd8524WPL=8*1+5*2+2*3+4*3=36119哈夫曼樹的構造方法

(1)由給定的n個權值{w0,w1,w2,…,wn-1}，構造具有n棵二叉樹的森林F={T0,T1,T2,…,Tn-1}，其中每一棵二叉樹Ti只有一個帶有權值wi的根結點，其左、右子樹均為空。

(2)重復以下步驟,直到F中僅剩下一棵樹為止：

①在F中選取兩棵根結點的權值最小的二叉樹,做為左、右子樹構造一棵新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。

②在F中刪去這兩棵二叉樹。

③把新的二叉樹加入F。1209例如:已知權值W={5,6,2,9,7}

構造以權值為葉子的哈夫曼樹5627第一步：把每個權值看作只有一個結點的樹1219例如:已知權值W={5,6,2,9,7}

構造以權值為葉子的哈夫曼樹5267第二步：取權值最小的兩棵樹，合并成，新樹的權值為兩棵子樹權值之和71229例如:已知權值W={5,6,2,9,7}

構造以權值為葉子的哈夫曼樹5267第三步：從森林中去掉被合并的結點，并將新合并的樹加入到森林中，繼續(xù)執(zhí)行第二步，直到森林合并成為一棵樹71239例如:已知權值W={5,6,2,9,7}

構造以權值為葉子的哈夫曼樹5267713第三步：從森林中去掉被合并的結點，并將新合并的樹加入到森林中，繼續(xù)執(zhí)行第二步，直到森林合并成為一棵樹1249例如:已知權值W={5,6,2,9,7}

構造以權值為葉子的哈夫曼樹526771316第三步：從森林中去掉被合并的結點，并將新合并的樹加入到森林中，繼續(xù)執(zhí)行第二步，直到森林合并成為一棵樹1259例如:已知權值W={5,6,2,9,7}

構造以權值為葉子的哈夫曼樹526771316第三步：從森林中去掉被合并的結點，并將新合并的樹加入到森林中，繼續(xù)執(zhí)行第二步，直到森林合并成為一棵樹1269例如:已知權值W={5,6,2,9,7}

構造以權值為葉子的哈夫曼樹52677131629第三步：從森林中去掉被合并的結點，并將新合并的樹加入到森林中，繼續(xù)執(zhí)行第二步，直到森林合并成為一棵樹構造完成127例w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100128指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。三、前綴編碼利用哈夫曼樹可以構造一種不等長的二進制編碼，并且構造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。129哈夫曼樹的應用——編碼各類編碼ABCD等長編碼00011011報文總長可以縮短不等長編碼010011存在多義性0000AAAAAACACA前綴編碼010110111一組編碼中任何一個編碼均不為其他編碼的前綴.避免了多義性，且縮短了報文總長哈夫曼編碼通過建立哈夫曼樹得到最優(yōu)的二進制前綴編碼130哈夫曼編碼

主要用途是實現(xiàn)數(shù)據(jù)壓縮。

設給出一段報文：

CASTCASTSATATATASA

字符集合是{C,A,S,T}，各個字符出現(xiàn)的頻度(次數(shù))是W＝{2,7,4,5}。

若給每個字符以等長編碼

A:00T:10C:01S:11則總編碼長度為(2+7+4+5)*2=36.

若按各個字符出現(xiàn)的概率不同而給予不等長編碼，可望減少總編碼長度。因各字符出現(xiàn)的概率為{2/18,7/18,4/18,5/18}。131化整為{2,7,4,5}，以它們?yōu)楦魅~結點上的權值，建立哈夫曼樹。左分支賦0，右分支賦1，得哈夫曼編碼(變長編碼)。

A:0T:10C:110S:111它的總編碼長度：7*1+5*2+(2+4)*3=35。比等長編碼的情形要短。哈夫曼編碼是一種無前綴的編碼。解碼時不會混淆。132哈夫曼編碼的實現(xiàn)方法假設七個字符A,B,C,D,E,F,G在某次通信中出現(xiàn)的次數(shù)為4,2,6,8,3,2,1,設計這七個字符的哈夫曼編碼。其過程如下:設置數(shù)組ht[m]表示哈夫曼樹,每個數(shù)組元素表示一個結點,每個結點由w,p,l,r組成,表示權值,雙親,左孩子和右孩子.(1)初始態(tài)時在ht[m]的前n項存放編號為1~n的權值;133(2)依次將數(shù)組ht[m]的n+1項到第2n-1項做為當前項,進行如下處理:①在前面已經(jīng)形成的項目中選擇兩個權值最小且無雙親的項做為選擇項;②將當前項的序號填入兩個選擇項做為雙親,將兩個選擇項的序號填入當前項做為左右孩子;③將兩個選擇項的權值相加后填入當前項做為當前項的權值;(3)由形成的哈夫曼樹求哈夫曼編碼:由根結點到葉結點,左分支為0,右分支為1;134初始態(tài)時在ht[m]的前n項存放編號為1~n的權值;

wplr14223648536271135①在前面已經(jīng)形成的項目中選擇兩個權值最小且無雙親的項做為選擇項;