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

1、第第 6 6 章樹和二叉樹章樹和二叉樹6.1 6.1 樹的定義和基本術語樹的定義和基本術語6.2 6.2 二叉樹二叉樹 6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 6.4 6.4 樹和森林樹和森林 6.5 6.5 赫夫曼樹及其應用赫夫曼樹及其應用6.1 6.1 樹的定義和基本術語樹的定義和基本術語6.1.1 6.1.1 樹的定義樹的定義6.1.2 6.1.2 基本術語基本術語6.1.3 6.1.3 樹的表示樹的表示1.1.樹的定義樹的定義 樹是由n（n0）個結點組成的有限集合。若n=0，稱為空樹；若n0，則：（1）有且僅有一個特定的稱為根根（root）的結點。它只有直接后繼，

2、但沒有直接前驅；（2）當n1時,其余結點可以劃分為m（m0）個互不相交的有限集合T1，T2，Tm，每個集合又是一棵樹，稱為根的子樹子樹，每棵子樹的根結點有且僅有一個直接前驅，但可以有0個或多個直接后繼。由此可知，樹的定義是一個遞歸的定義，即樹的定義中又用到了樹的概念。樹的結構參見圖6-1。6.1.1 6.1.1 樹的定義樹的定義一棵樹的邏輯結構可以用二元組描述為：tree =(k,R) k=ki1in;n0,kielemtype R=r其中，n為樹中結點個數(shù)，若 n=0，則為一棵空樹， n0時稱為一棵非空樹，而關系 r 應滿足下列條件：（1）有且僅有一個結點沒有前驅,稱該結點為樹根;（2）除根

3、結點以外,其余每個結點有且僅有一個直接前驅;（3）樹中每個結點可以有多個直接后繼(孩子結點)。2. 2. 樹的邏輯結構描述樹的邏輯結構描述例如，對圖6-1(c )的樹結構,可以二元組表示為：K=A，B，C，D，E，F(xiàn)，G，H，I，J，K，L，MR=rr=，(1) InitTree(&T) 初始化樹T。(2) Root(T) 求樹T的根結點(3) Parent(T,x) 求樹T中，值為x的結點的雙親。(4) Child(T,x,i) 求樹T中，值為x的結點的第i個孩子。(5) AddChild(y,i,x) 把值為x的結點作為值為y的結點的第i個孩子插入到樹中。(6) DelChild(

4、x,i) 刪除值為x的結點的第i個孩子。(7) TraverseTree(T) 遍歷或訪問樹T。 3. 3. 樹的基本運算樹的基本運算1.1.結點結點: : 樹的結點包含一個數(shù)據(jù)元素及若干指向其子樹的分支2.2.度度: : 一個結點包含子樹的數(shù)目，稱為該結點的度。3.3.葉子（終端）結點葉子（終端）結點度為0的結點，稱為葉子結點或樹葉，也叫終端結點。 4.4.孩子結點孩子結點 若結點X有子樹，則子樹的根結點為X的孩子結點，也稱為孩子，兒子，子女等。如圖6-1（c）中A的孩子為B，C，D。 5.5.雙親結點雙親結點 若結點X有子女Y，則X為Y的雙親結點。6.1.2 6.1.2 基本術語基本術語

5、6.6.祖先結點祖先結點 從根結點到該結點所經過分支上的所有結點為該結點的祖先，如圖6-1（c）中M的祖先有A，D ，H 。7.7.子孫結點子孫結點 某一結點的子女及子女的子女都為該結點子孫。 8.8.兄弟結點兄弟結點 具有同一個雙親的結點，稱為兄弟結點。9.9.分支結點分支結點 除葉子結點外的所有結點，為分支結點，也叫非終端結點。(度不為0的結點)1010層數(shù)層數(shù)( (層次層次) ) 根結點的層數(shù)為1，其它結點的層數(shù)為從根結點到該結點所經過的分支數(shù)目再加1。11. 11. 樹的高度（深度）樹的高度（深度） 樹中結點所處的最大層數(shù)稱為樹的高度，如空樹的高度為0，只有一個根結點的樹高度1。12.

6、12.樹的度樹的度 樹中結點度的最大值稱為樹的度。13. 13. 有序樹有序樹 若一棵樹中所有子樹從左到右的排序是有順序的，不能顛倒次序。稱該樹為有序樹。 14. 14. 無序樹無序樹 若一棵樹中所有子樹的次序無關緊要，則稱為無序樹。1515森林（樹林）森林（樹林） 若干棵互不相交的樹組成的集合為森林。一棵樹可以看成是一個特殊的森林。 1 1樹形結構表示法樹形結構表示法6.1.3 6.1.3 樹的表示樹的表示2. 2. 凹入法表示法凹入法表示法 3. 3. 嵌套集合表示法嵌套集合表示法4. 4. 廣義表表示法廣義表表示法（A（B（E（J，K，L），F(xiàn)），C（G），D（H（M），I） 6.2 二

7、叉樹二叉樹6.2.1 6.2.1 二叉樹的定義二叉樹的定義6.2.2 6.2.2 二叉樹的性質二叉樹的性質6.2.3 6.2.3 二叉樹的存儲結構二叉樹的存儲結構6.2.1 6.2.1 二叉樹的定義二叉樹的定義1 1 二叉樹的定義二叉樹的定義 和樹結構定義類似，二叉樹的定義也可以遞歸形式給出： 二叉樹是n（n0）個結點的有限集，它或者是空集（n=0），或者由一個根結點及兩棵不相交的左子樹和右子樹組成。 二叉樹的特點是每個結點最多有兩個孩子，或者說，在二叉樹中不存在度大于2的結點，并且二叉樹是有序樹（樹為無序樹），其子樹的順序不能顛倒。因此，二叉樹有五種不同的形態(tài)。 (a) 空二叉樹(b) 僅有

8、一個根結點的二叉樹(c) 右子樹為空的二叉樹(d) 左子樹為空的二叉樹(e) 左、右子樹均非空的二叉樹二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài)（1）InitBitree(&T) 二叉樹的初始化。 （2）Root(T) 求二叉樹的根結點（3）Parent(T,x) 求二叉樹T中值為x的結點的雙親（4）Lchild(T,x) 求二叉樹T中值為x的結點的左孩子。 （5）Rchild(T,x) 求二叉樹T中值為x的結點的右孩子。 （6）Lbrother(T,x) 求二叉樹T中值為x的結點的左兄弟。 （7）Rbrother(T,x) 求二叉樹T中值為x的結點的右兄弟。2. 2. 二叉樹的基本運算

9、二叉樹的基本運算（8）Traverse(T) 遍歷二叉樹T。（9）CreateBiTree(&T) 建立一棵二叉樹T。（10）AddLchild(&T,x,y) 在二叉樹T中，將值為y的結點作為值為x的結點的左孩子插入。 （11）AddRchild(&T,x,y) 在二叉樹T中，將值為y的結點作為值為x的結點的右孩子插入。 （12） DelLchild(&T,x) 在二叉樹T中，刪除值為x 的結點的左孩子。 （13）DelRchild(&T,x) 在二叉樹T中，刪除值為x 的結點的右孩子。 性質性質1 1 若二叉樹的層數(shù)從1開始，則二叉樹的第i層結點數(shù)，

10、最多為2 2i-1i-1個（i1）。6.2.2 6.2.2 二叉樹的性質二叉樹的性質20=121=222=423=8 深度（高度）為k的二叉樹最大結點數(shù)為2 2k k-1-1（k1）。證明:最大結點個數(shù)=20+21+22+2k-1=2k-1性質性質2 2 對任意一棵二叉樹，如果葉子結點個數(shù)為n0，度為2的結點個數(shù)為n2，則有n0=n2+1。證明：設n0,n1和n2分別為二叉樹中度為0,度為1和度為2的結點個數(shù)，則二叉樹中總的結點個數(shù)n滿足： n=n0+n1+n2 再有除了根結點之外，每個結點都由一個分支射入，則分支數(shù)B與總的結點數(shù)之間的關系為： n=B+1 另外，由于這些分支是由度為1或2的結

11、點射出的，則有 B=n1+2n2則由上三式得： n0=n2+1性質性質3 3 為繼續(xù)給出二叉樹的其它性質，先定義兩種特殊的二叉樹：滿二叉樹滿二叉樹 深度為k具有2 2k k-1-1個結點的二叉樹，稱為滿二叉樹。完全二叉樹完全二叉樹 如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1- n的結點一一對應，則稱這棵二叉樹為完全二叉樹。 11 12 13 14 15 具有n個結點的完全二叉樹完全二叉樹的深度深度為 log2n +1 +1證明：設深度為k,則由性質2和完全二叉樹的性質有： 2k-1-1n2k-1即 2k-1 n 2k 則有 k-1 log2n 1，則

12、其父結點編號為 i/2 。(2) 如果2in，則其左兒子結點編號為2i；若2in，則無左兒子結點。(3) 如果（2i+1）n，則其右兒子結點編號為（2i+1）；反之，則無右兒子結點。性質性質5 5 11 12 13 14 15 6.2.3 6.2.3 二叉樹的存儲結構二叉樹的存儲結構1.1.順序存儲結構順序存儲結構2.2.鏈式存儲結構鏈式存儲結構1.1.順序存儲結構順序存儲結構思想思想:用一個一維數(shù)組來存儲二叉樹的各個結點C C語言表示語言表示#define MAX_TREE_SIZE 100/二叉樹的最大結點數(shù)typedef TElemType SqBiTreeMAX_TREE_SIZE;

13、/0號單元存儲根結點SqBiTree bt; 分析分析: :顯然，二叉樹的結點必須按某種次序分別存入數(shù)組的各個單元，這種次序應能反映結點間的邏輯關系，否則二叉樹上的各種基本運算在順序存儲結構上很難實現(xiàn)。對于完全二叉樹來說，可以采用“以編號為地址”的方法，將編號為i的結點存入一維數(shù)組的第i個單元(下標為i-1)。例:對應的順序存儲結構:下標123456789100123456789完全二叉樹的順序表示:例:對應的順序存儲結構:一維數(shù)組的21單元中只用上了7個.最壞情況下,一個深度為k且只有k個結點的單支樹,卻需要長度為2k-1的一維數(shù)組.非完全二叉樹的順序表示: A B C E F G D A

14、B D C E G F 總結總結: :順序存儲結構適合存儲完全二叉樹對于非完全二叉樹，采用鏈式存儲結構更合適2. 2. 二叉鏈表二叉鏈表結點結構結點結構: :通常每個結點中設置三個域,即值域、左指針域和右指針域，其結點結構如下：其中data表示值域，用于存儲放入結點的數(shù)據(jù)，lchild和rchild分別表示左指針域和右指針域，用以分別存儲指向左兒子結點和右兒子結點的指針。 lchilddatarchild 存儲表示存儲表示typedef struct BiTNodetypedef struct BiTNode TElemType data; TElemType data; struct BiT

15、Node struct BiTNode * *lchild, lchild, * *rchild;rchild; BiTNode, BiTNode, * *BITreeBITree; 這里的TElemType可以是任何相應的數(shù)據(jù)類型如int、float或char等。 二叉鏈表例: 鏈式存儲: A B E C D G F 3. 3. 三叉鏈表三叉鏈表通常每個結點中設置四個域,即值域、左指針域、右指針域和雙親指針域，其結點結構如下：其中data表示值域，用于存儲放入結點的數(shù)據(jù)，lchild和rchild分別表示左指針域和右指針域，用以分別存儲指向左兒子結點和右兒子結點的指針,parent指向雙親結

16、點。 lchilddata rchildparent 6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.3.1 6.3.1 遍歷二叉樹遍歷二叉樹定義定義:二叉樹的遍歷(Traverse)是指按一定的規(guī)律訪問二叉樹的每個結點，且每個結點只被訪問一次的過程。對二叉樹的遍歷過程實際上是將非線性結構的二叉樹中的結點排列成一個線性序列的過程。本節(jié)僅討論二叉鏈表的遍歷過程。 一個非空的二叉樹由根結點及左、右子樹這三個基本部分組成，因此若能依次遍歷這三部分，便是遍歷了整個二叉樹。在任一給定結點上，可以按某種次序執(zhí)行三個操作：訪問結點本身，遍歷該結點左子樹，遍歷該結點右子樹，操作排列次序：左、根

17、、右左、根、右；根、左、右根、左、右；左、右、根左、右、根；右、根、左；根、右、左；右、左、根；由于實際問題一般都是要求左子樹較右子樹先遍歷，故只采用其中、三種遍歷次序，分別稱為中序遍歷中序遍歷、先序遍歷先序遍歷和后序遍歷后序遍歷。(1) 中序（InOrder）遍歷若遍歷的二叉樹為空，執(zhí)行空操作；否則依次執(zhí)行下列操作：中序遍歷左子樹；訪問根結點；中序遍歷右子樹。(2) 先序（PreOrder）遍歷若遍歷的二叉樹為空，執(zhí)行空操作；否則依次執(zhí)行下列操作：訪問根結點；先序遍歷左子樹；先序遍歷右子樹。三種遍歷次序以遞歸的形式定義：三種遍歷次序以遞歸的形式定義：(3) 后序（PostOrder）遍歷若遍

18、歷的二叉樹為空，執(zhí)行空操作；否則依次執(zhí)行下列操作：后序遍歷左子樹；后序遍歷右子樹；訪問根結點。 中序遍歷序列： 先序遍歷序列： 后序遍歷序列： 二叉樹遍歷舉例HDIBEAFCG B C D E F G A H I ABDHIECFGHIDEBFGCA中序遍歷遞歸算法voidInOrder(BITreeT)if(T)InOrder(T-lchild);visit(T-data);InOrder(T-rchild);先序遍歷遞歸算法voidPreOrder(BITreeT)if(T)visit(T-data);PreOrder(T-lchild);PreOrder(T-rchild);后序遍歷遞歸

19、算法voidPostOrder(BITreeT)if(T)PostOrder(T-lchild);PostOrder(T-rchild);visit(T-data);遍歷算法的應用遍歷算法的應用二叉樹的遍歷算法是一個重要的應用注意注意:1.理解訪問根結點的意義2.對具體問題需要考慮遍歷的順序1.1.先序創(chuàng)建二叉鏈表先序創(chuàng)建二叉鏈表StatusCreateBiTree(BITree&T)scanf(&ch);if(ch=)T=Null;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;Creat

20、eBiTree(T-lchild);CreateBiTree(T-rchild);returnOK;2.2.輸出二叉樹的結點輸出二叉樹的結點voidPreOrder(BITreeT)if(T)printf(T-data);PreOrder(T-lchild);PreOrder(T-rchild);3.3.輸出二叉樹的葉子結點輸出二叉樹的葉子結點voidPreOrder(BITreeT)if(T)if(T-lchild=NULL&T-rchild=NULL)printf(T-data);PreOrder(T-lchild);PreOrder(T-rchild);4.4.統(tǒng)計二叉樹的葉子結

21、點個數(shù)統(tǒng)計二叉樹的葉子結點個數(shù)intn=0;voidleafcount(BITreeT)if(T)if(T-lchild=NULL&T-rchild=NULL)n+;leafcount(T-lchild);leafcount(T-rchild);5.5.求二叉樹的高度求二叉樹的高度intPostTreeDepth(BITreeT)if(T)hl=PostTreeDepth(T-lchild);hr=PostTreeDepth(T-rchild);max=hlhr?hl:hr;return(max+1);elsereturn0;二叉樹的非遞歸遍歷可利用堆棧將遞歸算法改寫成非遞歸的形式。下

22、面以中序遍歷為例來具體說明。T-*caba*-cb&-&*&a&b&ca*b -c中序非遞歸遍歷算法分析：1.棧初始化,根指針入棧2.當棧非空時 (1)當棧頂元素非空時,左指針入棧向左走向盡頭 (2)棧頂空指針出棧 (3)當棧非空時, 棧頂元素出棧并訪問且將其右指針入棧算法實現(xiàn)算法實現(xiàn)：void InOrder(BiTree T)void InOrder(BiTree T)InitStack(S);Push(S,T);InitStack(S);Push(S,T);while (!StackEmpty(S)while (!StackEmpty(S) whi

23、le(GetTop(S,p)&p) while(GetTop(S,p)&p) Push(S,p-lchild); Push(S,p-lchild); Pop(S,p); Pop(S,p); if(!StackEmpty(S) if(!StackEmpty(S) Pop(S,p);visit(p-data); Pop(S,p);visit(p-data); Push(S,p-rchild);/if Push(S,p-rchild);/if/while/while 6.3.2 6.3.2 線索二叉樹線索二叉樹相關概念相關概念:在一個n結點的鏈式存儲二叉樹中，有n+1個指針域是空指針

24、域，可以把每個空指針域用于存放分別指向某種遍歷次序的前趨和后繼結點的指針。線索線索:在結點的空指針域中存放的該結點在某遍歷次序下的前趨結點和后繼結點的指針叫做線索。線索二叉樹線索二叉樹:對一個二叉樹中的所有結點的空指針域按照某種遍歷次序加線索的過程叫作線索化，被線索化了的二叉樹稱作線索二叉樹。在一個線索二叉樹中，必須設法將線索與指向結點左、右兒子結點的指針加以區(qū)別。可給每個結點增加兩個標志域，即左線索標志域LTag，右線索標志域RTag。左線索域是指向其前驅結點的的指針域是指向其左兒子結點leftleftltag10右線索域是指向其后繼結點的的指針域是指向其右兒子結點rightrightrta

25、g10LTagRTaglchildlchild域指示結點的左孩子域指示結點的左孩子lchildlchild域指示結點的前趨域指示結點的前趨rchildrchild域指示結點的右孩子域指示結點的右孩子rchildrchild域指示結點的后繼域指示結點的后繼 增加線索標志域后的結點結構為：這種結點類型和相應結點的指針類型定義如下：typedef enum PointerTagLink,Thread; typedef struct BiThrNode ElemType data; PointerTag LTag,RTag; /*ltag和rtag只能取值為0或1*/ struct BiThrNode

26、 *lchild,*rchild; BiThrNode,*BiThrTree; lchild LTag data RTag rchild 中序線索樹 A C F G B D E H I T11中序遍歷線索樹思想思想: 先由頭結點指針找到根結點，從根結點起沿左指針逐結點一直向左查找，找到左線索標志為1的結點(“最左”的結點)即為遍歷中需首先訪問的結點。由此結點開始，反復進行尋找后繼結點的過程，并陸續(xù)訪問這些結點，直至結束。中序遍歷線索二叉樹非遞歸算法void thinorder(BiThrTree T)/二叉樹附加了頭結點,T指向頭結點p= T-lchild;/p指向根結點whild(p!=T)

27、 /*空樹或遍歷結束時,p=T*/ while(p-LTag=Link) p=p-lchild; /*從根往下找到最左的結點，即中序序列的開始結點*/ visit(p-data);/訪問左子樹為空結點 while(p-Rtag=Thread&p-rchild!=T) p=p-rchild;visit(p-data);/*訪問后繼結點*/ p=p-rchild; return OK; 中序線索化思想思想：一邊中序遍歷一邊建立線索。若訪問結點的左兒子結點為空，則建立前趨線索；若右兒子結點為空，則建立后繼線索。 為此附設一個指針pre始終指向剛剛訪問過的結點，而用指針p指示當前正在訪問的結點

28、。pre的初始值為NULL。中序線索化算法void inthread (BiThrTree &p,void inthread (BiThrTree &p,* *pre)pre) if(p) if(p) inthread(p-lchild,pre); / inthread(p-lchild,pre); /* *左子樹線左子樹線索化索化* */ / if(p-lchild=NULL) if(p-lchild=NULL) / /* *若當前結點的左子樹為空，則建立指若當前結點的左子樹為空，則建立指向其前趨結點的前趨線索向其前趨結點的前趨線索* */ / p-ltag=1; p-lta

29、g=1; p-lchild=pre; p-lchild=pre; else else p-ltag=0; p-ltag=0; 中序線索化算法續(xù) if (pre!=NULL & pre-right=NULL) if (pre!=NULL & pre-right=NULL) / /* *若前趨結點不為空，且其右指針域為空，則建若前趨結點不為空，且其右指針域為空，則建立該前趨結點指向當前結點的后繼線索立該前趨結點指向當前結點的后繼線索* */ / pre-RTag=1; pre-RTag=1; pre-rchild=p; pre-rchild=p; else else pre-RTa

30、g=0; pre-RTag=0; pre=p; / pre=p; /* *中序向后遍歷一個結點中序向后遍歷一個結點* */ / inthread (p-rchild,pre); inthread (p-rchild,pre); 6.4 6.4 樹和森林樹和森林6.4.1 6.4.1 樹的存儲結構樹的存儲結構6.4.2 6.4.2 森林與二叉樹的轉換森林與二叉樹的轉換6.4.3 6.4.3 樹和森林的遍歷樹和森林的遍歷6.4.1 6.4.1 樹的存儲結構樹的存儲結構1 1雙親表示法雙親表示法2. 2. 孩子表示法孩子表示法 3 3孩子兄弟表示法孩子兄弟表示法 1 1雙親表示法雙親表示法這種方法用

31、一組連續(xù)的空間來存儲樹中的結點，在保存每個結點的同時附設一個指示器來指示其雙親結點在表中的位置 .其結點的結構如下： 數(shù)據(jù)域雙親位置域dataparent雙親表示法的形式說明如下：#define MAX 100#define MAX 100typedef struct PTNode /typedef struct PTNode /結點結構結點結構 TElemType data; TElemType data; int parent; int parent;PTNode;PTNode;typedef struct /typedef struct /樹結構樹結構 PTNode nodesMAX;

32、PTNode nodesMAX; int r,n; / int r,n; /根的位置和結點數(shù)根的位置和結點數(shù)PTree;PTree;雙親表示法舉例2. 2. 孩子表示法孩子表示法這種方法通常是把每個結點的孩子結點排列起來，構成一個單鏈表，稱為孩子鏈表。n個結點共有n個孩子鏈表（葉結點的孩子鏈表為空表），而n個結點的數(shù)據(jù)和n個孩子鏈表的頭指針又組成一個順序表. 類型說明類型說明 typedef struct CTNode/ 孩子鏈表結點的定 int child; / 該孩子結點在線性表中的位置 struct CTNode * next;/指向下一個孩子結點 *ChildPtr; typedef

33、struct/ 順序表結點的結構定義 TElemType data;/ 結點的信息 ChildPtr firstChild ; / 孩子鏈表的頭指針CTBox;typedef struct / 樹的定義 CTBox nodesMAX; / 順序表 int n,r;/ 結點數(shù)和根的位置 CTree;孩子表示法舉例674563. 3. 孩子兄弟表示法孩子兄弟表示法這種表示法又稱為樹的二叉表示法，或者二叉鏈表表示法，即以二叉鏈表作為樹的存儲結構。鏈表中每個結點設有兩個鏈域，分別指向該結點的第一個孩子結點和下一個兄弟（右兄弟）結點。形式說明typedef struct CSNode ElemType

34、data; /*結點信息*/ Struct CSNode *firstChild, *Nextsibling; /*第一個孩子,下一個兄弟*/CSNode, *CSTree;孩子兄弟表示法舉例6.4.2 6.4.2 森林與二叉樹的轉換森林與二叉樹的轉換樹的孩子兄弟鏈表結構與二叉樹的二叉鏈表結構在物理結構上是完全相同的，只是它們的邏輯含義不同，所以樹和森林與二叉樹之間必然有著密切的關系。本節(jié)我們就介紹樹和森林與二叉樹之間的相互轉換方法。方法如下： (1)在所有兄弟結點之間加一連線； (2) 對樹中的每個結點，只保留其與第一個孩子結點之間的連線，刪去其與其它孩子結點之間的連線。 (3)以樹的根結點

35、為軸心，將整棵樹順時針旋轉一定的角度，使之結構層次分明。1樹轉換為二叉樹樹轉換成二叉樹舉例森林是若干棵樹的集合。樹可以轉換為二叉樹，森林同樣也可以轉換為二叉樹。因此，森林也可以方便地用孩子兄弟鏈表表示。方法如下方法如下：（1） 將森林中的每棵樹轉換成相應的二叉樹。（2）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連在一起后，所得到的二叉樹就是由森林轉換得到的二叉樹。2.森林轉換為二叉樹森林轉換成二叉樹舉例6.4.3 樹與森林的遍歷1.1.樹的遍歷樹的遍歷方法主要有以下兩種：（1） 先根遍歷若樹非空，則遍歷方法為：訪問根結點。從左到

36、右，依次先根遍歷根結點的每一棵子樹。（2）后根遍歷若樹非空，則遍歷方法為：從左到右，依次后根遍歷根結點的每一棵子樹。訪問根結點。樹的遍歷舉例如右圖樹先根遍歷序列為ABECFHGD后根遍歷序列為EBHFGCDA2.2.森林的遍歷森林的遍歷森林的遍歷方法主要有以下兩種：(1) 先序遍歷若森林非空，則遍歷方法為：訪問森林中第一棵樹的根結點。先序遍歷第一棵樹的根結點的子樹森林。先序遍歷除去第一棵樹之后剩余的樹構成的森林。 (2) 后序遍歷若森林非空，則遍歷方法為： 后序遍歷森林中第一棵樹的根結點的子樹森林。 訪問第一棵樹的根結點。 后序遍歷除去第一棵樹之后剩余的樹構成的森林。森林的遍歷舉例如右圖森林先

37、序遍歷序列為ABCDEFGHIJ后序遍歷序列為BCDAFEHJIG6.5 6.5 赫夫曼樹及其應用赫夫曼樹及其應用6.5.1赫夫曼樹赫夫曼樹( (最最優(yōu)優(yōu)二叉樹二叉樹) )6.5.2赫夫曼編碼赫夫曼編碼6.5.1赫夫曼樹赫夫曼樹( (最優(yōu)二叉樹最優(yōu)二叉樹) )1. 1. 基本術語基本術語：路徑路徑：從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑。路徑長度路徑長度：路徑上的分支數(shù)稱為這兩點之間的路徑長度。樹的路徑長度樹的路徑長度：樹的路徑長度是從樹的根到每一結點的路徑長度之和，一般記作pl。 在結點數(shù)目相同的二叉樹中，完全二叉樹或滿二叉樹的路徑長度最短。pl=0+1+1+2+2+2+2=10 pl=0+1+1+2+2+2+3=11 結點的權結點的權：在許多實際應用中，常常將樹中結點賦予一個有某種意義的實