1、第六章 二叉樹n6.1 二叉樹的定義與性質n6.2 二叉樹的基本操作與存儲實現n6.3 二叉樹的遍歷n6.4 線索二叉樹n6.5 樹和森林n6.6 哈夫曼樹（赫夫曼樹）6.1.1 二叉樹的基本概念1、定義：二叉樹是由n(n=0)個結點的有限集合構成，此集合或者為空集，或者由一個根結點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。 二叉樹是有序的，將左右子樹顛倒，就形成 一個不同的二叉樹。二叉樹具有5種基本形態，如下圖：n6.1 樹的定義與性質(a)空二叉樹A(b)左右子樹為空的樹AB(c)右子樹為空的二叉樹AB(d) 左子樹為空的二叉樹ACB (e)包含左右子樹的二叉樹2、二叉樹的相關

2、概念：l結點的度：結點擁有的子樹的個數稱為該結點的度。l葉結點:度為0的結點稱為葉結點，或者稱為終端結點。l分支結點：度不為0的結點稱為分支結點，或者稱為非終端結點。一棵樹的結點除葉子節點外，其余的都是分支結點。l左孩子、右孩子、雙親、兄弟：樹中一個結點的子樹的根節點稱為這個結點的孩子。在二叉樹中，左子樹的根稱為左孩子，右子樹的根稱為右孩子。這個結點稱為他孩子結點的雙親。具有同一個雙親的孩子結點互稱為兄弟。l路徑、路徑長度：如果一棵樹的一串結點n1,n2,nk有如下關系：結點ni是ni+1的父結點(1i k)，就把n1,n2,nk稱為一條由n1 nk的路徑，這條路徑的長度是k-1.l祖先、子孫

3、：在樹中，如果有一條路徑從結點M到結點N,那么M就稱為N的祖先，而N就稱為M的子孫。l結點的層數：規定樹的根結點的層數為1，其余結點的層數等于它的雙親結點的層數加1.l樹的深度：樹中所有結點的最大層數稱為數的深度。l樹的度：樹中所有結點度的最大值稱為該樹的度。l滿二叉樹：滿二叉樹：在一棵二叉樹中，如果所有分支結點都存在左在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子結點都在同一層上，這樣的子樹和右子樹，并且所有葉子結點都在同一層上，這樣的一棵二叉樹稱為滿二叉樹。一棵二叉樹稱為滿二叉樹。123456789 10 11 12 13 14 15l完全二叉樹：深度為k的，有n個結點

4、的二叉樹，對樹中的結點按從上到下、從左到右的順序進行編號，如果編號為i的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同，則這棵二叉樹稱為滿二叉樹。abcdefghij完全二叉樹的特點：完全二叉樹的特點：(1)(1)葉子結點只能在層次最大的兩層上出現。葉子結點只能在層次最大的兩層上出現。(2)(2)對任一結點，若其右分支下的子孫的最大層次對任一結點，若其右分支下的子孫的最大層次 為為m m，則其左分支下的子孫上的最大層次必為，則其左分支下的子孫上的最大層次必為m+1m+1。6.1.2 二叉樹的性質n性質1：一棵非空二叉樹的第i層上至多有2i-1個結點(i=1)。采用歸納法證明此性質。 當i=

5、1時，只有一個根結點，2i-1=20 =1,命題成立。 現在假定對所有的j，1=j=1)。 分析：深度為k的二叉樹的最大的結點為二叉樹中每層上的最大結點數之和。 由性質1得到每層i上的最大結點數為2i-1，那么 所有結點數為 = 2k 1k11 - i2in性質3：對任何一棵二叉樹，如果葉子結點數為n0，度為2的結點數為n2，則n0n21。 設二叉樹中度為1的結點數為n1，二叉樹中總結點數為N，因為二叉樹中所有結點的度均小于或等于2，所以其結點總數：Nn0n1n2 （61) 再看二叉樹中的分支數，除根結點外，其余結點都有一個進入分支，設B為二叉樹中的分支總數，則有：NB1。由于這些分支都是由度

6、為1和2的結點發出的，所以有： Bn1+2*n2即得，NB1n12*n21 （62)由式（61）和（62）得到： n0+n1+n2=n1+2*n2+1 n0n21n性質4：具有n個結點的完全二叉樹的深度為 1 符號 x 表示不大于x的最大整數。 證明：假設此二叉樹的深度為k，則根據性質2及完全二叉樹的定義得到： 2k-11n2k-1 或 2k-1n2k 取對數得到：k1log2nk 因為k是整數。所以有： k 1。logn2 logn2n性質5：如果對一棵有n個結點的完全二叉樹的結點按層序編號（從第1層到第 +1層，每層從左到右),則對任一結點i（1=i1，則其雙親是結點 i/2 。 （2）如

7、果2in，則結點i為葉子結點，無左孩子；否則，其左孩子是結點2i。 （3）如果2i1n，則結點i無右孩子；否則，其右孩子是結點2i1。logn2例1：二叉樹的第k層的結點數最多為( ). A2k-1 B.2K+1 C.2K-1 D. 2k-1例2：一棵高度為5的二叉樹中最少含有_ 個結點，最多含有_個結點；例3：在一棵非空二叉樹中,度為2的結點個數為5,度為0的結點個數 ( ) A4 B5 C6 D7例4：9根據二叉樹的定義可知二叉樹共有（ ）種不同的形態。(A) 4 (B) 5 (C) 6 (D) 7D531性質性質2性質性質1性質性質3CBn6.2 二叉樹的基本操作與存儲實現6.2.1二叉

8、樹的存儲1、順序存儲結構、順序存儲結構 它是用一組連續的存儲單元存儲二叉樹的數據元素。一般它是用一組連續的存儲單元存儲二叉樹的數據元素。一般是按照二叉樹結點從上至下，從左到右的順序存儲。是按照二叉樹結點從上至下，從左到右的順序存儲。ABCDEFGHIJABD EFG HCIJ01345 67892完全二叉樹的順序存儲 對于一般的二叉樹，如果仍按從上到下和從左到右的順序將樹中的結點順序存儲在一維數組中，需添加一些不存在的空節點，使它變成一個完全二叉樹。ABCEFGJAB D E C F一般二叉樹的順序存儲 GABCDEFG 結論：顯然這種需增加許多空結點才能將一棵二叉樹改造成一棵完全二叉樹的存儲

9、，會造成空間的大量浪費，不宜采用順序存儲結構，滿二叉樹和完全二叉樹比較適合順序存儲。2、鏈式存儲結構 所謂二叉鏈表存儲結構，是指用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。通常有下面兩種形式：（1）二叉鏈表存儲 鏈中每個結點由3個域組成，除了數據域外，還有兩個指針域，分別用來給出結點的左孩子和右孩子。結點存儲結構：lchild data rchild 存儲二叉樹經常用二叉鏈表法，如下圖：ABC D E F GH lchildDatarchild頭指針bt不帶頭結點的二叉鏈表 二叉鏈表也可以帶頭結點的方式存放，如下圖：ABC D E F GH lchildDatarchild頭結點指針b

10、t帶頭結點的二叉鏈表 二叉鏈表存儲表示為：typedef struct BiTNode / 結點結構結點結構 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree 結點結構：lchild data rchild（2）三叉鏈表存儲 鏈中每個結點由4個域組成，結點存儲結構： 其中，data、lchild以及rchild這三個域和二叉鏈表結構相同；parent域向該結點雙親結點的指針。這種結構既便于查找孩子結點，又便于查找雙親結點；但是相對于二叉鏈表，三叉鏈表增加了空間開銷。lchild data rch

11、ildparent 三叉鏈表存儲 lchild data rchildparentADEBCF typedef struct TriTNode / 結點結構結點結構 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指針 struct TriTNode *parent; /雙親指針 TriTNode, *TriTree;parent lchild data rchild結點結構結點結構: :三叉鏈表的存儲表示可描述為: :6.2.2二叉樹的基本操作及實現1、二叉樹的基本操作 InitBiTree(bt); /建立一棵空二叉樹建立一棵

12、空二叉樹 Create(x,lbt,rbt); /生成一棵以生成一棵以x為根結點的數據域為根結點的數據域信息，以二叉樹信息，以二叉樹lbt和和rbt為左子樹和右子樹的二叉為左子樹和右子樹的二叉樹。樹。 InsertLChild(bt, x, parent); /將數據信息為將數據信息為x的結的結點插入到二叉樹點插入到二叉樹bt中作為結點中作為結點parent的左孩子結點。的左孩子結點。如果原來結點如果原來結點parent原來有左孩子結點，則將結點原來有左孩子結點，則將結點parent原來的左孩子結點作為結點原來的左孩子結點作為結點x的左孩子結點。的左孩子結點。DeleteLChild(bt,

13、parent); /在結點在結點bt中刪除結點中刪除結點parent的左子樹。的左子樹。 Search(bt，x); /在二叉樹在二叉樹bt中查找數據元素中查找數據元素x。 Traverse(bt); /按某種方式遍歷二叉樹按某種方式遍歷二叉樹bt的全部結點。的全部結點。2、算法實現、算法實現 int InitBiTree(BiTNode bt); /建立一棵空二叉樹建立一棵空二叉樹 bt = new BiNode; if(!bt) return 0; /沒有存儲空間返回0 bt-lchild=NULL; bt-rchild=NULL; return 1; /返回成功代碼1main() BiT

14、ree t; Initiate(&t); 二叉樹的遍歷是按照某種順序訪問二叉樹的每個結點，是每個結點被訪問一次且僅被訪問一次。 二叉樹的三個基本組成單元是：根結點、左子樹和右子樹。 假如以L、D、R分別表示遍歷左子樹、遍歷根結點和遍歷右子樹，遍歷整個二叉樹則有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。若規定先左后右，則只有前三種情況，分別規定為： DLR先（根）序遍歷， LDR中（根）序遍歷， LRD后（根）序遍歷。n6.3二叉樹的遍歷1、先序遍歷二叉樹的操作定義為：若二叉樹為空，則遍歷結束；否則（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。例如圖中所示的二叉

15、樹表達式若先序遍歷此二叉樹,按訪問結點的先后次序將結點排列起來,其先序序列為： -+a*b-cd/ef*a/b-dcfe2、中序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。例如圖中所示的二叉樹表達式按中序遍歷,其中序序列為： a+b*c-d-e/f*a/b-dcfe3、后序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。例如圖中所示的二叉樹表達式按后序遍歷,其后序序列為： abcd-*+ef/-*a/b-dcfe4、層次遍歷二叉樹的操作定義為： 從二叉樹的第一

16、層開始，從上至下逐層遍歷，在同一層中，按從左到右的順序對結點逐個訪問。例如圖中所示的二叉樹表達式按層次遍歷,其層次序列為： -+/a*efb-cd*a/b-dcfeABCDEFGHK例如:先序先序序列: A B C D E F G H K中序中序序列: B D C A H G K F E后序后序序列: D C B H K G F E A 當以二叉鏈表作為存儲結構時,只能找到結點的左右孩子的信息,而不能在任一序列中找到結點的前驅與后繼信息,這種信息只有在遍歷的動態過程中才能得到,為了能保存所需的信息,可增加兩個標志域。 若該結點的左子樹不空，若該結點的左子樹不空，則Lchild域的指針指向其左子

17、樹，且左標志域的值為“指針 Link”或0；否則，Lchild域的指針指向其“前驅”，且左標志的值為“線索 Thread”或1 。n6.4線索二叉樹lchildLTagdataRTagrchild 若該結點的右子樹不空，若該結點的右子樹不空，則rchild域的指針指向其右子樹，且右標志域的值為 “指針 Link”或0；否則，rchild域的指針指向其“后繼”，且右標志的值為“線索 Thread”或1。即: 0 lchild 域指示結點的左孩子 1 lchild 域指示結點的前驅 0 rchild 域指示結點的右孩子 1 rchild 域指示結點的后繼 以這種結構構成的二叉鏈表作為二叉樹的存儲結

18、構,叫做線索鏈表,其中指向結點前驅與后繼的指針叫做線索。加上線索的二叉樹稱之為線索二叉樹。n6.4線索二叉樹ltag =rtag= n6.4線索二叉樹ABDCGFE(a)先序線索二叉樹GABDCFE(b)中序線索二叉樹ABDCGFE(c)后序線索二叉樹例如：例如：0100A01B10D11G00C11E11Fbt中序線索二叉樹存儲n6.5 樹和森林6.5.1 樹的定義及相關術語 樹是n(n0)個有限數據水元素的集合。當n=0時稱這棵樹為空樹。在一棵非空樹T中 : 有一個特殊的數據元素稱為樹的根結點，根結點沒有前驅結點。 若n1,除根結點以外的其余數據元素被分成m(m0) 個互不相交的集合T1,

19、T2,Tm，其中每一個集合Ti(1i m)本身又是一棵樹。樹T1,T2,Tm稱為這個根節點的子樹。 樹的定義可以描述為二元組的形式 T=(D,R) 其中，D為樹T中結點的集合，R為樹中結點之間關系的集合。n6.5 樹和森林 6.5.1 樹的定義 當樹為空樹時，D=；當樹T不為空樹時，有 D=root DF 其中，D為樹T中結點的集合，R為樹中結點之間關系的集合。DF可由下式表示 DF= D1 D2 Dm且且Di Dj=(ij,1i m, 1j m)當樹T中結點個數n 1時，時，R=；當樹T中結點個數n1時，有R=,1,2,m,其中，root為樹T的根結點root的子樹的Ti的根結點。 如圖是一

20、棵有9個結點的樹，即T=A,B,C,H,I,結點A為樹T的根結點，除根結點A的其余結點分為兩個不相交的集合T1=B,D,E,F,H,I和T2=C，G，構成了結點A的兩棵子樹，T1和T2本身也分別是一棵樹。例如，子樹T1的根結點為B，其余結點又分為3個不相交的集合：T11=D, T12=F,H,I和T13=E。 T11, , T12, T13構成了子樹T1的根結點B的三棵子樹。如此繼續分為更小的樹。ABCDFGHIE 從樹的定義和上圖的示例可以看出，樹具有下面兩個特點： 樹的根結點沒有前驅結點，除根結點之外的所有結點有且只有一個前驅結點。樹中所有結點可以有零個或者多個后繼結點。由此可知下圖均不是

21、樹結構：ABDECGFABDECGF 6.5.2 相關術語 (1)有序樹和無序樹，如果一棵樹中結點的各子樹從左到右是有次序的，即若交換了某結點各子樹的相對位置，則構成不同的樹，稱這棵樹為有序樹；反之，則稱為無序樹。 (2)森林，零棵或有限棵不相交的樹的集合稱為森林。 任何一棵樹，刪去根結點就變成了森林。 6.5.3 樹的表示 1、直觀表示法 ABCDEF G H I JMKL2、嵌套集合表示法 所謂嵌套集合是指一些集合的集體，對于其中任何兩個集合，或者不相交，或者一個包含另一個。用嵌套集合的形式表示樹，就是將根節點視為一個大的集合，其若干棵樹、子樹構成這個大集合中若干個互不相交的子集，如此嵌套

22、下去，即構成了一棵樹的嵌套集合表示。 ABKELFDHMJICG嵌套集合表示法嵌套集合表示法ABCDEF G H I JMKL3、廣義表表示法 將根作為由子樹森林組成的表的名字寫在表的左邊，這樣依次將樹表示出來。ABCDEF G H I JMKL（A(B(E,F(K,L),C(G),D(H,I,J(M)廣義表表示法廣義表表示法4、凹入表示法 每個結點對應一個矩形，所有結點的矩形都是右對齊，根結點用最長的矩形表示，同一層的結點的矩形長度相同，層次越高，矩形長度越短。 ABCDEF G H I JMKLABCDEKLFGHIJM凹入表示法凹入表示法6.5.4樹的存儲結構 樹的存儲有多種方式，既可以

23、采用順序存儲結構，也可以采用鏈式存儲結構，存儲結構不但要求存儲結點本身的數據信息，還要能唯一反應樹中各節點之間的邏輯關系。1、雙親表示法 用一組連續的存儲空間(一維數組)存儲樹中各個結 點，數組中的一個元素表示樹中一個結點，數組元素 為結構體類型，其中包括結點本身的信息和結點的雙 親結點在數組中的序號。雙親表示法雙親表示法:序號dataABCDEFGHIparent-100111244ABCDEFGHI一棵樹結構data parent結點結構：結點結構：#define MAX_TREE_SIZE 100 typedef struct PTNode Elem data; int parent;

24、/ 雙親位置域 PTNode; 樹結構樹結構:typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; / 根結點的位置和結點個數 PTree;存儲表示如下：存儲表示如下：2、孩子表示法(1)多重鏈表法 每個結點包括一個結點信息域和多個指針域，每 個指針域指向該結點的一個孩子結點，通過各個指針 域值反應出樹中各節點之間的邏輯關系。結點的指針域的設置有兩種方法： 每個結點指針域的個數等于該結點的度數。 每個結點指針域的個數等于樹的度。每個節點指針域的個數等于該結點的度數。ABCDEABCDEFGHI一棵樹結構每個節點指針域的個數等于樹的度數。AF (

25、2)孩子鏈表表示法由一個與結點數一樣大小的一維數組存放結點，數組的每個元素有兩個域組成，一個域用來存放結點信息，另一個域用來存放指針，這個指針指向由該結點孩子組成的單鏈表的首地址。 序號 data firstchildABCDEFGHI12345678typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子結點結構孩子結點結構: :孩子鏈表存儲表示孩子鏈表存儲表示描述為描述為: :child nextdata firstchild typedef struct Elem data; ChildPtr firstchil

26、d; / 孩子鏈的頭指針 CTBox;雙親結點結：雙親結點結： 3、雙親孩子表示法是將雙親表示法和孩子鏈表法相結合的結果。孩子結點組成單鏈表，同時用一維數組順序存儲樹中的各結點，數組元素包括結點本身信息和結點孩子結點鏈表頭指針和雙親結點在數組中的序號。 序號datafirstchildABCDEFGHI12345678parent-100111244 3、孩子兄弟表示法在樹中每個結點除其信息域外，再增加兩個分別指向該結點的第一個孩子結點和下一個兄弟結點的指針。 AFtypedef struct CSNode Elem data; struct CSNode *firstchild, *next

27、sibling; CSNode, *CSTree;結點存儲表示結點存儲表示描述為描述為: :結點結構結點結構: : firstchild data nextsibling6.5.5樹、森林與二叉樹的轉換 1、樹轉換為二叉樹 對于一棵無序樹，樹中結點的各孩子的次序是無關緊要的，而二叉樹終結點的左、右孩子結點是有區別的。為了避免發生混淆，約定樹的每一個孩子結點按從左到右的順序編號。如下圖，根結點A有B、C、D三個孩子，可以認為結點B為A的第一個孩子結點，結點C為A的第二個孩子結點，結點D為A的第三個孩子結點。ABDCEFG 將一棵樹轉換為二叉樹的方法如下： (1)樹中所有相鄰兄弟之間加一條連線 (

28、2)對樹中每個結點，只保留它與第一個孩子結點之間的連線。 (3)以樹的根結點為軸心，將整棵樹順時針轉動一定的角度，使之結構層次分明。ABDCEFGABDCEFGABDCEFG 由轉換可知，在二叉樹中，左分支上的各由轉換可知，在二叉樹中，左分支上的各節點在原來的樹中是父子關子，而右分支上的節點在原來的樹中是父子關子，而右分支上的各結點在原來的樹中是兄弟關系。由于樹的根各結點在原來的樹中是兄弟關系。由于樹的根結點沒有兄弟，所以變換后的二叉樹的根結點結點沒有兄弟，所以變換后的二叉樹的根結點的右孩子必為空。的右孩子必為空。2、森林轉換為二叉樹方法描述為： F = ( T1, T2, , Tm )是森林

29、，則可按如下規則轉換成一棵二叉樹B = (root，LB, RB)。l若 F = ，m=0,則 B = ；l若F ，B的根root即為森林中第一棵樹的根ROOT( T1 ) ； B的左子樹LB是從T1中根結點的子樹森林F1=T11, T12, , T1m 轉換成的二叉樹；其右子樹RB是從森林F= T1, T2, , Tm 轉換而成的二叉樹。 將森林轉換為二叉樹的方法如下： (1)將森林中的每棵樹轉換成相應的二叉樹 (2)第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連起來以后，此時所得到的二叉樹就是森林轉換得到的二叉樹。ABCDFE

30、JGHIKABCDFEJGHIKABCDFEJGHIK3、由二叉樹轉換為森林方法描述為：如果B=(root,LB,RB)是一棵二叉樹，則按如下規則轉換成森林F= ( T1, T2, , Tm )l若 B = B = ， 則 F = F = ；l若 B ，則森林中的第一棵樹T1的根ROOT(TROOT(T1 1) )即即是B的根root；T1中根結點的子樹森林F1是由B的左子樹LB轉換而成的森林；F中除T T1 1外其余樹組成的森林F= T1, T2, , Tm 是由B的右子樹RB轉換而成的森林。具體方法為：（1）結點是其雙親的左孩子，則把該結點的右孩子、右孩子的右孩子都與該節點的雙親結點用線連

31、起來。（2）刪去原二叉樹中所有的雙親結點與右孩子節點的連線。（3）整理（1）、（2）兩步所得到的樹或森林，使之結構層次分明。由二叉樹轉換為森林由二叉樹轉換為森林的轉換過程：ABCDFEGHIABCDFEGHI(a)一棵二叉樹(b)加連線ABCDFEGHI(c)去掉與右孩子的連線FEGHIABC D(d)還原后的森林樹的遍歷可有三條搜索路徑樹的遍歷可有三條搜索路徑: :按層次遍歷按層次遍歷: :先根先根( (次序次序) )遍歷遍歷: :后根后根( (次序次序) )遍歷遍歷: : 若樹不空，則先訪問根結點，然后依次先根若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹。遍歷各棵子樹。 若樹不空，則

32、先依次后根遍歷各棵子樹，然若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。后訪問根結點。 若樹不空，則自上而下自左至右訪問樹若樹不空，則自上而下自左至右訪問樹中每個結點。中每個結點。6.5.6樹和森林的遍歷樹和森林的遍歷1 1、樹的遍歷、樹的遍歷先根遍歷時頂點的訪問次序：先根遍歷時頂點的訪問次序：A B C E F G D后根遍歷時頂點的訪問次序：后根遍歷時頂點的訪問次序：B E G F C D A層次遍歷時頂點的訪問次序：層次遍歷時頂點的訪問次序：A B C D E F G ABCDEFG B C DE F G H I J K1 1森林中第一棵樹的根森林中第一棵樹的根結點；結點；2 2森

33、林中第一棵樹的子森林中第一棵樹的子樹森林；樹森林；3 3森林中其它樹構成的森森林中其它樹構成的森林。林。森林由三部分構成：森林由三部分構成：2 2、森林的遍歷、森林的遍歷 若森林不空，則若森林不空，則l訪問訪問森林中第一棵樹的根結點；l先序遍歷先序遍歷森林中第一棵樹的子樹森林；l先序遍歷先序遍歷森林中(除第一棵樹之外)其余樹構成的森林。(1)(1)先序遍歷森林先序遍歷森林即：依次從左至右依次從左至右對森林中的每一棵樹樹進行先先根遍歷根遍歷。(2)(2)中序遍歷中序遍歷若森林不空，則若森林不空，則l中序遍歷中序遍歷森林中第一棵樹的子樹森林；l訪問訪問森林中第一棵樹的根結點；l中序遍歷中序遍歷森林

34、中(除第一棵樹之外)其 余樹構成的森林。即：依次從左至右依次從左至右對森林中的每一棵樹樹進行后根后根遍歷遍歷。 B C DE F G H I J K例如例如： 先序遍歷時頂點的訪問次序：先序遍歷時頂點的訪問次序：B E F C D G H I J K后序遍歷時頂點的訪問次序：后序遍歷時頂點的訪問次序：E F B C I J K H G Dn6.6哈夫曼樹(霍夫曼樹) 6.6.1 哈夫曼樹的基本概念 哈夫曼樹，也稱最優二叉樹，是指對于一組帶有確定權值的葉子結點，構造的具有最小帶權路徑長度的二叉樹。l路徑長度路徑長度：從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑，路徑上的分支數目稱

35、做路徑長度。l樹的路徑長度樹的路徑長度：是從樹根到每一結點的路徑長度之和。l結點的帶權路徑長度結點的帶權路徑長度：從根結點到該結點的路徑長度與結點上權的乘積。l樹的帶權路徑長度樹的帶權路徑長度：根結點到各個葉子結點的路徑長度與相應結點權值的乘積之和 WPL(T) = wklk (對所有葉子結點) 在所有含 n 個葉子結點、并帶相同權值的 m 叉樹中，必存在一棵其帶權路徑長度取最小值帶權路徑長度取最小值的樹，稱為“最優樹最優樹”或者“哈夫曼樹哈夫曼樹”。(a)WPL(T)= 72+52+22+42=36(b)WPL(T)= 73+53+42+21=46(c)WPL(T)= 71+52+23+43

36、=35 如何構建最優樹？樹的帶全路徑長度：樹的帶全路徑長度： 哈夫曼樹依據這一特點提出了這種方法，基本思想是：n根據給定的 n 個權值 w1, w2, , wn，構造 n 棵只有一個葉子結點的二叉樹，從而得到一個二叉樹的集合F = T1, T2, , Tn。n在 F 中選取其根結點的權值為最小和次小的兩棵二叉樹作為左、右子樹構造一棵新的二叉樹，這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和；n從F中刪去這兩棵樹，同時將新建立的二叉樹加入到集合F中；n重復(2)和(3)兩步，直至 F 中只含一棵樹為止。這棵樹便是哈夫曼樹。9例如: 已知權值 W= 5, 6, 2, 9, 7 56275

37、2769779613527 7575796713527 757 720952720671329注意：注意： 初始森林中的初始森林中的n n棵二叉樹，每棵樹有一個孤立的棵二叉樹，每棵樹有一個孤立的結點，它們既是根，又是葉子結點，它們既是根，又是葉子 n n個葉子的哈夫曼樹要經過個葉子的哈夫曼樹要經過n-1n-1次合并，產生次合并，產生n-1n-1個新結點。最終求得的哈夫曼樹中共有個新結點。最終求得的哈夫曼樹中共有2n-12n-1個結個結點。點。 哈夫曼樹是嚴格的二叉樹，沒有度數為哈夫曼樹是嚴格的二叉樹，沒有度數為1 1的分支的分支結點。結點。6.6.2 6.6.2 哈夫曼編碼哈夫曼編碼1 1、不

38、等長編碼、不等長編碼 這種編碼方式的特點這種編碼方式的特點: :每個字符的編碼每個字符的編碼長度相同長度相同。 設字符集只含有設字符集只含有4 4個字符個字符A A，B B，C C，D D，用兩位二進，用兩位二進制表示的編碼分別為制表示的編碼分別為0000，0101，1010，1111。若現在電文為：。若現在電文為：ABACCDAABACCDA，則應發送二進制序列：，則應發送二進制序列：0001001010110000010010101100，總長度為總長度為1414位。當接收方接收到這段電文后，將按兩位位。當接收方接收到這段電文后，將按兩位一段進行譯碼。一段進行譯碼。這種編碼的特點這種編碼的

39、特點: : 譯碼簡單且具有唯一性，但編碼長度并不是最短的。譯碼簡單且具有唯一性，但編碼長度并不是最短的。2. 2. 不等長編碼不等長編碼 在傳送電文時，為了使其二進制位數盡可能地少，在傳送電文時，為了使其二進制位數盡可能地少，可以將每個字符的編碼設計為不等長的，使用頻度較可以將每個字符的編碼設計為不等長的，使用頻度較高高的字符分配一個相對比較的字符分配一個相對比較短短的編碼，使用頻度較的編碼，使用頻度較低低的字符分配一個比較的字符分配一個比較長長的編碼。的編碼。例如，可以為例如，可以為A A，B B，C C，D D四個字符分別分配四個字符分別分配0 0，0000，1 1，0101，并可將上述電

40、文用二進制序列：，并可將上述電文用二進制序列：000011010000011010發送，發送，其長度只有其長度只有9 9個二進制位。個二進制位。 但隨之帶來了一個問題，接收方接到這段電文后但隨之帶來了一個問題，接收方接到這段電文后無法進行譯碼，因為無法斷定前面無法進行譯碼，因為無法斷定前面4 4個個0 0是是4 4個個A A，1 1個個B B、2 2個個A A，還是，還是2 2個個B B，即譯碼不唯一，因此這種編碼，即譯碼不唯一，因此這種編碼方法不可使用。方法不可使用。3 3、哈夫曼編碼、哈夫曼編碼 利用哈夫曼樹可以構造一種不等長的二進制編利用哈夫曼樹可以構造一種不等長的二進制編碼，并且構造所

41、得的碼，并且構造所得的哈夫曼編碼哈夫曼編碼是一種是一種最優前綴編碼最優前綴編碼，即：使所傳即：使所傳電文的總長度最短電文的總長度最短。哈夫曼編碼的構造方法：哈夫曼編碼的構造方法：（1 1）利用字符集中每個字符的使用頻率作為權值構造）利用字符集中每個字符的使用頻率作為權值構造一個哈夫曼樹；一個哈夫曼樹；（2 2）從根結點開始，為到每個葉子結點路徑上的左分）從根結點開始，為到每個葉子結點路徑上的左分支賦予支賦予0 0，右分支賦予，右分支賦予1 1，并從根到葉子方向形成該葉，并從根到葉子方向形成該葉子結點的編碼。子結點的編碼。1152978142331000115582900011184219000

42、11100010011001111110111111010Weight parent lchild rchild 1 2 3 4 5 6 7 8 9101112131415529870000000000000000000000000000000000000000000001423311999178101034151111128191414121313151552942581002101161412130HTHT數組數組哈夫曼編碼存儲結構哈夫曼編碼存儲結構: :HCHC12345678001111111111111110000000015, 29, 7, 8, 14, 23, 3, 111. 熟

43、練掌握二叉樹的結構特性二叉樹的結構特性，了解相應的證明方法。2. 熟悉二叉樹的各種存儲結構存儲結構的特點及適用范圍。3. 遍歷二叉樹遍歷二叉樹是二叉樹各種操作的基礎。實現二叉樹遍歷的具體算法與所采用的存儲結構有關。掌握各種遍歷策略的遞歸算法遞歸算法，靈活運用遍靈活運用遍歷算法歷算法實現二叉樹的其它操作。層次遍歷層次遍歷是按另一種搜索策略進行的遍歷。4. 理解二叉樹線索化的實質線索化的實質是建立結點與其在相應序列中的前驅或后繼之間的直接聯系，熟練掌握二叉樹的線索化過程線索化過程以及在中序線索化樹上找給定結點的前驅和后繼的方法。二叉樹的線索化過程線索化過程是基于基于對二叉樹進行遍歷遍歷，為相應的遍

44、歷提供為相應的遍歷提供了方便方便。5. 熟悉樹的樹的各種存儲結構存儲結構及其特點，掌握樹和森林與二叉樹的轉換樹和森林與二叉樹的轉換方法。建立存儲結構是進行其它操作的前提，因此讀者應掌握掌握 1 至 2 種建立建立二叉樹和樹的存儲結構的方法存儲結構的方法。6. 學會編寫實現樹的各種操作實現樹的各種操作的算法。7. 了解最優樹的特性最優樹的特性，掌握建立最優樹建立最優樹和哈夫曼編碼和哈夫曼編碼的方法。n1 1）在一棵二叉樹上第）在一棵二叉樹上第4 4層的結點數最多是層的結點數最多是_。 A.4 B.8 C.32 D.12A.4 B.8 C.32 D.12n2) 2) 在深度為在深度為5 5的滿二叉樹中，葉子結點的個數為的滿二叉樹中，葉子結點的個數為_。 A.32 B.31 C.16 D.15A.32 B.31 C.16 D.15n3) 3) 在深度為在深度為5 5的二叉樹中，至多有的二叉樹中，至多有_個結點。個結點。n A.32 B.31 C.16 D.15A.32 B.31 C.16 D.15n4 4）在具有）在具有10 10 個結點的樹中，其邊的樹目為個結點的