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

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

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

3、結(jié)點以外,其余每個結(jié)點有且僅有一個直接前驅(qū);（3）樹中每個結(jié)點可以有多個直接后繼(孩子結(jié)點)。2. 2. 樹的邏輯結(jié)構(gòu)描述樹的邏輯結(jié)構(gòu)描述例如，對圖6-1(c )的樹結(jié)構(gòu),可以二元組表示為：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的根結(jié)點(3) Parent(T,x) 求樹T中，值為x的結(jié)點的雙親。(4) Child(T,x,i) 求樹T中，值為x的結(jié)點的第i個孩子。(5) AddChild(y,i,x) 把值為x的結(jié)點作為值為y的結(jié)點的第i個孩子插入到樹中。(6) DelChild(

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

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

6、12.樹的度樹的度 樹中結(jié)點度的最大值稱為樹的度。13. 13. 有序樹有序樹 若一棵樹中所有子樹從左到右的排序是有順序的，不能顛倒次序。稱該樹為有序樹。 14. 14. 無序樹無序樹 若一棵樹中所有子樹的次序無關(guān)緊要，則稱為無序樹。1515森林（樹林）森林（樹林） 若干棵互不相交的樹組成的集合為森林。一棵樹可以看成是一個特殊的森林。 1 1樹形結(jié)構(gòu)表示法樹形結(jié)構(gòu)表示法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 二叉樹的性質(zhì)二叉樹的性質(zhì)6.2.3 6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)6.2.1 6.2.1 二叉樹的定義二叉樹的定義1 1 二叉樹的定義二叉樹的定義 和樹結(jié)構(gòu)定義類似，二叉樹的定義也可以遞歸形式給出： 二叉樹是n（n0）個結(jié)點的有限集，它或者是空集（n=0），或者由一個根結(jié)點及兩棵不相交的左子樹和右子樹組成。 二叉樹的特點是每個結(jié)點最多有兩個孩子，或者說，在二叉樹中不存在度大于2的結(jié)點，并且二叉樹是有序樹（樹為無序樹），其子樹的順序不能顛倒。因此，二叉樹有五種不同的形態(tài)。 (a) 空二叉樹(b) 僅有

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

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

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

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

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

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

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

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

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

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

18、歷的二叉樹為空，執(zhí)行空操作；否則依次執(zhí)行下列操作：后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點。 中序遍歷序列： 先序遍歷序列： 后序遍歷序列： 二叉樹遍歷舉例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);遍歷算法的應(yīng)用遍歷算法的應(yīng)用二叉樹的遍歷算法是一個重要的應(yīng)用注意注意:1.理解訪問根結(jié)點的意義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.輸出二叉樹的結(jié)點輸出二叉樹的結(jié)點voidPreOrder(BITreeT)if(T)printf(T-data);PreOrder(T-lchild);PreOrder(T-rchild);3.3.輸出二叉樹的葉子結(jié)點輸出二叉樹的葉子結(jié)點voidPreOrder(BITreeT)if(T)if(T-lchild=NULL&T-rchild=NULL)printf(T-data);PreOrder(T-lchild);PreOrder(T-rchild);4.4.統(tǒng)計二叉樹的葉子結(jié)

21、點個數(shù)統(tǒng)計二叉樹的葉子結(jié)點個數(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 線索二叉樹線索二叉樹相關(guān)概念相關(guān)概念:在一個n結(jié)點的鏈式存儲二叉樹中，有n+1個指針域是空指針

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

25、g10LTagRTaglchildlchild域指示結(jié)點的左孩子域指示結(jié)點的左孩子lchildlchild域指示結(jié)點的前趨域指示結(jié)點的前趨rchildrchild域指示結(jié)點的右孩子域指示結(jié)點的右孩子rchildrchild域指示結(jié)點的后繼域指示結(jié)點的后繼 增加線索標志域后的結(jié)點結(jié)構(gòu)為：這種結(jié)點類型和相應(yīng)結(jié)點的指針類型定義如下：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中序遍歷線索樹思想思想: 先由頭結(jié)點指針找到根結(jié)點，從根結(jié)點起沿左指針逐結(jié)點一直向左查找，找到左線索標志為1的結(jié)點(“最左”的結(jié)點)即為遍歷中需首先訪問的結(jié)點。由此結(jié)點開始，反復進行尋找后繼結(jié)點的過程，并陸續(xù)訪問這些結(jié)點，直至結(jié)束。中序遍歷線索二叉樹非遞歸算法void thinorder(BiThrTree T)/二叉樹附加了頭結(jié)點,T指向頭結(jié)點p= T-lchild;/p指向根結(jié)點whild(p!=T)

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

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) / /* *若當前結(jié)點的左子樹為空，則建立指若當前結(jié)點的左子樹為空，則建立指向其前趨結(jié)點的前趨線索向其前趨結(jié)點的前趨線索* */ / 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) / /* *若前趨結(jié)點不為空，且其右指針域為空，則建若前趨結(jié)點不為空，且其右指針域為空，則建立該前趨結(jié)點指向當前結(jié)點的后繼線索立該前趨結(jié)點指向當前結(jié)點的后繼線索* */ / 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; /* *中序向后遍歷一個結(jié)點中序向后遍歷一個結(jié)點* */ / inthread (p-rchild,pre); inthread (p-rchild,pre); 6.4 6.4 樹和森林樹和森林6.4.1 6.4.1 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)6.4.2 6.4.2 森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換6.4.3 6.4.3 樹和森林的遍歷樹和森林的遍歷6.4.1 6.4.1 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)1 1雙親表示法雙親表示法2. 2. 孩子表示法孩子表示法 3 3孩子兄弟表示法孩子兄弟表示法 1 1雙親表示法雙親表示法這種方法用

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

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

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

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

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

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

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