工程09級使用數(shù)據(jù)結構第6章

返回主目錄

本章說明6.1樹的基本定義6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.6赫夫曼樹及其應用

本章小結

學習目標領會樹和二叉樹的類型定義，理解樹和二叉樹的結構差別熟記二叉樹的主要特性，并掌握它們的證明方法熟練掌握二叉樹的各種遍歷算法，并能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作理解二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅和后繼的方法熟練掌握二叉樹和樹的各種存儲結構及其建立的算法學會編寫實現(xiàn)樹的各種操作的算法了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。本章說明本章說明

重點和難點二叉樹和樹的遍歷及其應用是本章的學習重點，而編寫實現(xiàn)二叉樹和樹的各種操作的遞歸算法也恰是本章的難點所在。知識點樹的類型定義、二叉樹的類型定義、二叉樹的存儲表示、二叉樹的遍歷以及其它操作的實現(xiàn)、線索二叉樹、樹和森林的存儲表示、樹和森林的遍歷以及其它操作的實現(xiàn)、最優(yōu)樹和赫夫曼編碼學習指南本章是整個課程的第二個學習重點，也是整個課程中的一大難點。在本章的學習過程中主要應該學會如何根據(jù)二叉樹和樹的結構及其操作的遞歸定義編寫遞歸算法。6.1樹的定義和基本術語

樹是一類重要的非線性數(shù)據(jù)結構，是以分支關系定義的層次結構1、樹的定義定義：樹(tree)是n(n>0)個結點的有限集T，其中：有且僅有一個特定的結點，稱為樹的根(root)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2,……Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)特點：樹中至少有一個結點——根樹中各子樹是互不相交的集合6.1樹的定義和基本術語A只有根結點的樹ABCDEFGHIJKLM有子樹的樹根子樹ADTTree

數(shù)據(jù)對象D：數(shù)據(jù)關系R：基本操作P：InitTree(&T);DestroyTree(&T);CreateTree(&T,definition);ClearTree(&T);……2、樹的抽象數(shù)據(jù)類型的定義P1186.1樹的定義和基本術語樹形表示法：自然界倒長的樹(Knuth開初用正長的樹表示)文氏表示法：用嵌套集合表示(a)嵌套括號表示法：廣義表表示法凹入表示法：類似書目3、樹的表示方法6.1樹的定義和基本術語KLEADJIMHGCBF(a)ACDBEKLFGHMIJ(c)(b)(A(B(E(K,L),F),C(G),D(H(M),I,J)))4、樹的術語6.1樹的定義和基本術語結點(node)——表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支結點的度(degree)——結點擁有的子樹數(shù)葉子(leaf)——度為0的結點孩子(child)——結點子樹的根稱為該結點的孩子雙親(parents)——孩子結點的上層結點叫該結點的~兄弟(sibling)——同一雙親的孩子樹的度——一棵樹中最大的結點度數(shù)結點的層次(level)——從根結點算起，根為第一層，它的孩子為第二層……堂兄——其父母為兄弟的結點互稱堂兄祖先——結點的祖先是從根到該結點所經分支上的所有結點子孫——以某結點為根的子樹中的任一結點都稱為該結點的子孫有序樹——結點的子樹從左到右有順序，否則，稱為無序樹深度(depth)——樹中結點的最大層次數(shù)森林(forest)——m(m

0)棵互不相交的樹的集合6.1樹的定義和基本術語6.1樹的定義和基本術語ABCDEFGHIJKLM結點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為堂兄弟結點A是結點F，G的祖先6.2二叉樹1、二叉樹定義定義：二叉樹是n(n0)個結點的有限集，它或為空樹(n=0)，或由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成特點每個結點至多有二棵子樹(即不存在度大于2的結點)二叉樹的子樹有左、右之分，且其次序不能任意顛倒基本形態(tài)A只有根結點的二叉樹

空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空證明：用歸納法證明之

i=1時，只有一個根結點，顯然，2i-1=20=1

是對的假設對所有j,(1j<i)命題成立，即第j層上

至多有2j-1個結點，可證明j=i命題成立

③那么，第i-1層至多有2i-2個結點

又二叉樹每個結點的度至多為2

第i層上最大結點數(shù)是第i-1層的2倍，即

2×2i-2=2i-1

故命題得證2、二叉樹的性質6.2二叉樹性質1：性質2：深度為k的二叉樹至多有2k-1個結點(k1)6.2二叉樹證明：由性質1，可得深度為k的二叉樹最大結點數(shù)是性質3：對任何一棵二叉樹T，如果其終端結點數(shù)為n0，度為2的結點數(shù)為n2，則n0=n2+1證明：設n1為二叉樹T中度為1的結點數(shù)

因為：二叉樹中所有結點的度均小于或等于2

所以：其結點總數(shù)n=n0+n1+n2

又二叉樹中，除根結點外，其余結點都只有一

個分支進入，設B為分支總數(shù)，則n=B+1

又：分支由度為1和度為2的結點射出，

B=n1+2n2

于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1特點：每一層上的結點數(shù)都是最大結點數(shù)完全二叉樹定義：深度為k，有n個結點的二叉樹當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱為~特點葉子結點只可能在層次最大的兩層上出現(xiàn)對任一結點，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l或l+16.2二叉樹幾種特殊形式的二叉樹滿二叉樹定義：6.2二叉樹1231145891213671014151231145891267101234567123456思考：滿二叉樹與完全二叉樹的關系？性質4：具有n個結點的完全二叉樹的深度為

log2n+1

證明：設深度為k，則由性質2和完全二叉樹定義

(k-1層)2k-1-1<n≤2k-1(k層）或2k-1≤n<2k

于是k-1≤log2n<k

又k是整數(shù)

k=log2n+1性質5：對于一棵完全二叉樹，從上到下從左至右對結點進行編號,根結點為1,則對任一結點i(1<=i<=n)，有：若i=1,則結點是二叉樹的根，無雙親，否則其雙親是

i/2如果2i>n，則結點i無左子女，否則，其左子女為2i如果2i+1>n，則結點i無右子女，否則，其右子女為2i+16.2二叉樹3、二叉樹的存儲結構順序的存儲結構實現(xiàn)：按滿二叉樹的結點層次編號，依次存放二叉樹中的數(shù)據(jù)元素特點：結點間關系蘊含在其存儲位置中浪費空間，適于存滿二叉樹和完全二叉樹abcdefgabcde0000fg12345678910116.2二叉樹浪費空間二叉樹的順序存儲表示

#defineMAX_TREE_SIZE100TypedefTElemTypeSqBiTree[MAX_TREE_SIZE];//

0號單元存儲根結點

SqBiTreebt;缺點：按完全二叉樹形式存儲，浪費空間。例如，在最壞情況下，n個結點的單枝樹，要占用2n-1個元素的存儲空間。6.2二叉樹順序存儲結構適用于滿二叉樹和完全二叉樹的存儲。鏈式存儲結構二叉鏈表表示typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;lchilddatarchildABCDEFG在n個結點的二叉鏈表中，有n+1個空指針域ABCDEFG^^^^^^^^6.2二叉樹三叉鏈表表示typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild,*parent;}BiTNode,*Bitree;lchilddataparentrchildABCDEFGABCDEFG^^^^^^^^^6.2二叉樹6.3遍歷二叉樹和線索二叉樹

問題的提出

先左后右的遍歷算法

算法的遞歸描述

遍歷算法的應用舉例1、遍歷二叉樹

算法的非遞歸描述

順著某一條搜索路徑巡訪二叉樹中的結點，使得每個結點均被訪問一次，而且僅被訪問一次。

問題的提出“訪問”的含義可以很廣，如：輸出結點的信息等。6.3遍歷二叉樹和線索二叉樹6.3遍歷二叉樹和線索二叉樹

“遍歷”是任何類型均有的操作，對線性結構而言，只有一條搜索路徑(因為每個結點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結構，

每個結點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑進行遍歷的問題。6.3遍歷二叉樹和線索二叉樹

對“二叉樹”而言，可以有三條搜索路徑：（1）先上后下的按層次遍歷；（2）先左（子樹）后右（子樹）的遍歷；（3）先右（子樹）后左（子樹）的遍歷。6.3遍歷二叉樹和線索二叉樹

先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法根左子樹右子樹根根根根根訪問根結點、遍歷左子樹、遍歷右子樹6.3遍歷二叉樹和線索二叉樹

若二叉樹為空樹，則空操作；否則，（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：6.3遍歷二叉樹和線索二叉樹

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。中（根）序的遍歷算法：6.3遍歷二叉樹和線索二叉樹

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。后（根）序的遍歷算法：6.3遍歷二叉樹和線索二叉樹ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A6.3遍歷二叉樹和線索二叉樹

算法的遞歸描述（6.1）6.3遍歷二叉樹和線索二叉樹voidpreorder(BiTree*T){if(T){printf("%d\t",T->data);preorder(T->lchild);preorder(T->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC6.3遍歷二叉樹和線索二叉樹

算法的非遞歸描述

二叉樹表示表達式

基本思想

若表達式為數(shù)或簡單變量，則相應二叉樹只有根結點，其數(shù)據(jù)域存放表達式信息；否則，表達式均可寫成<第一操作數(shù)>（運算符）<第二操作數(shù)>形式，其中，“運算符”可用二叉樹的根結點表示，“第一操作數(shù)”用二叉樹的左子樹表示，“第二操作數(shù)”用二叉樹的右子樹表示。操作數(shù)本身可以是表達式。6.3遍歷二叉樹和線索二叉樹表達式=(操作數(shù)1)(運算符)(操作數(shù)2)運算符操作數(shù)1操作數(shù)26.3遍歷二叉樹和線索二叉樹例如：a+b*(c-d)-e/f的二叉樹表示。abcef-+*/d-先序（前綴表達式）中序（中綴表達式）后序（后綴表達式）-+a*b-cd/efa+b*c-d-e/fabcd-*+ef/-6.3遍歷二叉樹和線索二叉樹abc-*-*cab-*abc先序遍歷：-*abc6.3遍歷二叉樹和線索二叉樹abc-*-*cab中序遍歷：

a*b-ca*bc-6.3遍歷二叉樹和線索二叉樹abc-*-*cab后序遍歷：

ab*c-ab*c-6.3遍歷二叉樹和線索二叉樹

二叉樹遍歷的非遞歸算法6.2ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問：C(4)6.3遍歷二叉樹和線索二叉樹pABCDEFGiP->A訪問：CB(5)ABCDEFGiP->AP->D訪問：CBp(6)ABCDEFGiP->AP->DP->E訪問：CBp(7)ABCDEFGiP->AP->D訪問：CBEp(8)6.3遍歷二叉樹和線索二叉樹ABCDEFGiP->AP->DP->G訪問：CBEP=NULL(9)ABCDEFGiP->A訪問：CBEGDp(11)ABCDEFGiP->AP->F訪問：CBEGDp(12)ABCDEFGiP->AP->D訪問：CBEGp(10)6.3遍歷二叉樹和線索二叉樹ABCDEFGiP->A訪問：CBEGDFp=NULL(13)ABCDEFGi訪問：CBEGDFAp(14)ABCDEFGi訪問：CBEGDFAp=NULL(15)6.3遍歷二叉樹和線索二叉樹

建立二叉樹的存儲結構

遍歷算法的應用舉例

統(tǒng)計二叉樹中葉子結點的個數(shù)

求二叉樹的深度

二叉樹表示表達式6.3遍歷二叉樹和線索二叉樹

統(tǒng)計二叉樹中葉子結點的個數(shù)

算法基本思想:

先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結點，并計數(shù)。由此，需在遍歷算法中增添一個“計數(shù)”的參數(shù)，并將算法中“訪問結點”的操作改為:若是葉子，則計數(shù)器增1。算法實現(xiàn)6.3遍歷二叉樹和線索二叉樹否則，整個二叉樹中的葉子結點個數(shù)等于其左子樹中的葉子結點個數(shù)和其右子樹中的葉子結點個數(shù)之和。

另一種算法思想分析方法:若二叉樹為空，則葉子結點的個數(shù)為零;若二叉樹中只有一個(根)結點，則葉子結點的個數(shù)為1;(后序遍歷)算法實現(xiàn)6.3遍歷二叉樹和線索二叉樹

求二叉樹的深度算法基本思想:若二叉樹為空樹，則深度為0;否則，二叉樹的深度應為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度。

首先分析二叉樹的深度和它的左、右子樹深度之間的關系(后序遍歷)6.3遍歷二叉樹和線索二叉樹intDepth(BiTreeT){//返回二叉樹的深度

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}returndepthval;}6.3遍歷二叉樹和線索二叉樹也可以從另一角度去分析:

從二叉樹深度的定義還可知，二叉樹的深度即為其葉子結點所在層次的最大值。由此，可通過遍歷求得二叉樹中所有結點的“層次”，從中取其最大值。算法中需引入一個計結點層次的參數(shù)。

首先分析二叉樹的深度和結點的“層次”間的關系。6.3遍歷二叉樹和線索二叉樹voidDepth(BiTreeT,intlevel,int&dval){if(T){if(level>dval)dval=level;

Depth(T->lchild,level+1,dval);

Depth(T->rchild,level+1,dval);}}//調用之前l(fā)evel的初值為1。

//dval的初值為0.6.3遍歷二叉樹和線索二叉樹

建立二叉樹的存儲結構

不同的定義方法相應有不同的存儲結構的建立算法6.3遍歷二叉樹和線索二叉樹

以字符串的形式“根左子樹右子樹”定義一棵二叉樹（算法6.4）例如:A(B(,C(,)),D(,))以字符串“A”表示ABCD以空白字符“”表示空樹只含一個根結點的二叉樹A以下列字符串表示6.3遍歷二叉樹和線索二叉樹void

CreateBiTree(BiTree&T)

{

scanf(&ch);if(ch=='')T=NULL;else{

T=(BiTNode*)malloc(sizeof(BiTNode));T->data=ch;//生成根結點

CreateBiTree(T->lchild);//構造左子樹

CreateBiTree(T->rchild);//構造右子樹

}}//CreateBiTree6.3遍歷二叉樹和線索二叉樹AB

C

D

ABCD上頁算法執(zhí)行過程舉例如下:ATBCD^^^^^scanf(&ch);if(ch=='')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));T->data=ch;CreateBiTree(T->lchild);

CreateBiTree(T->rchild);}6.3遍歷二叉樹和線索二叉樹

二叉樹的遍歷有許多重要性質，現(xiàn)以例子加以說明。例如：僅知二叉樹的先序序列“abcdefg”不能唯一確定一棵二叉樹，如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列6.3遍歷二叉樹和線索二叉樹此例推論可知，二叉樹遍歷的重要性質：若已知二叉樹的先序序列和中序序列，可唯一確定一棵二叉樹；若已知二叉樹的后序序列和中序序列，也可唯一確定一棵二叉樹。6.3遍歷二叉樹和線索二叉樹6.3遍歷二叉樹和線索二叉樹2、線索二叉樹

線索二叉樹定義

線索二叉樹的遍歷

中序遍歷二叉線索樹的算法6.3遍歷二叉樹和線索二叉樹

二叉樹的遍歷本質上是將一個復雜的非線性結構轉換為線性結構，使每個結點都有了唯一前驅和后繼（第一個結點無前驅，最后一個結點無后繼）。對于二叉樹的一個結點，查找其左、右孩子是方便的，其前驅后繼只有在遍歷中得到。為了容易找到前驅和后繼，有兩種方法：在結點結構中增加向前和向后的指針fwd和bkd，這種方法增加了存儲開銷

利用二叉樹的空鏈指針。

線索二叉樹定義n個結點的二叉鏈表有n+1個空鏈域證明：因除了根結點外，每個結點都有一指針射入。

n個結點便有n-1個指針，即有n-1個非空鏈域。因有2n個鏈域

空鏈域個數(shù)為：2n-(n-1)=n+16.3遍歷二叉樹和線索二叉樹

為了節(jié)省存貯空間，我們可以利用這些空鏈域來存放結點的前趨和后繼的信息。為避免混淆，需在結點中增加兩個標志域：lchildltagdatartagrchild(特征位)0lchild域指示結點的左孩子ltag=1lchild域指示結點的前趨

rtag=0rchild域指示結點的右孩子

1rchild域指示結點的后繼6.3遍歷二叉樹和線索二叉樹

線索鏈表：以上述結點結構構成的二叉鏈表其中指向結點前趨和后繼的指針，叫做線索

線索二叉樹：加上線索的二叉樹對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。例如：中序線索二叉樹作業(yè)：畫先序，后序線索樹！6.3遍歷二叉樹和線索二叉樹6.3遍歷二叉樹和線索二叉樹abcef-+*/d-NILNIL中序線索二叉樹6.3遍歷二叉樹和線索二叉樹010-00+00/01a10*01e11b10-01c11d11f1thrtbt中序線索鏈表頭結點：lt=0,lc指向根結點rt=1,rc指向遍歷序列中最后一個結點遍歷序列中第一個結點的lc域和最后一個結點的rc域都指向頭結點

只要先找到序列中的第一個結點，依次找結點的后繼直到其后繼為空為止。6.3遍歷二叉樹和線索二叉樹

線索二叉樹的遍歷

在中序線索樹中找結點的后繼：

(1)若結點的rtag為1（葉子），則其后繼為線索rchild所指結點（2）（否則）若結點的rtag為0（非葉子），則其后繼為“從其右孩子沿著左鏈找到ltag為1的那個結點”

(即右子樹最左下的結點）6.3遍歷二叉樹和線索二叉樹

在中序線索樹中找結點的前驅：

(1)若結點的ltag為1（葉子），則其前驅為線索lchild所指結點（2）（否則）若結點的ltag為0（非葉子），則其前驅為“從其左孩子沿著右鏈找到rtag為1的那個結點”(即左子樹最右下的結點）

在后序線索二叉樹中查找結點的前驅和后繼要知道其雙親的信息，要使用棧，所以說后序線索二叉樹是不完善的。6.3遍歷二叉樹和線索二叉樹

二叉樹的二叉線索存儲表示Typedefenum{Link,Thread}pointerTag;//Link==0:指針，Thread==1：線索TypedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;PointerTagLtag,Rtag;}BiThrNode,*BiThrTree;二叉樹的線索化：是在遍歷的過程中，將二叉鏈表中的空指針改為線索中序遍歷的線索化算法在二叉樹的線索鏈表上加一個頭結點，令其lchild指向二叉樹的根結點，rchild指向中序遍歷時訪問的最后一個結點令二叉樹中序序列中的第一個結點的lchild和最后一個結點的rchild均指向頭結點（象雙向鏈表，可雙向遍歷）設指針p指向當前訪問結點，pre指向其前驅結點6.3遍歷二叉樹和線索二叉樹

中序遍歷二叉線索樹的算法

中序遍歷二叉線索樹T的非遞歸算法思想：找左子樹的最左葉子結點，訪問訪問后繼結點6.3遍歷二叉樹和線索二叉樹

學習線索化時，有三點必須注意：

何種序的線索化，是先序、中序還是后序要前驅線索化、后繼線索化還是全線索化（前驅后繼都要）只有空指針處才能加線索;6.4

樹和森林1、樹的三種存儲結構

雙親表示法

孩子鏈表表示法

樹的二叉鏈表(孩子-兄弟）存儲表示法6.4

樹和森林ABCDEFGr=0n=60

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent

雙親表示法雙親位置缺點：只反映了雙親位置6.4

樹和森林

typedefstructPTNode{ElemTypedata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結點結構:C語言的類型描述:6.4

樹和森林typedefstruct{

PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結點的位置和結點個數(shù)

}PTree;樹結構:6.4

樹和森林r=0n=6

datafirstchildABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4645

123

孩子鏈表表示法-1000224parent6.4

樹和森林typedefstructCTNode{

intchild;

structCTNode*next;}*ChildPtr;孩子結點結構:

childnextchildC語言的類型描述:6.4

樹和森林

typedefstruct{ElemTypedata;ChildPtrfirstchild;//孩子鏈的頭指針

}CTBox;雙親結點結構

datafirstchild6.4

樹和森林typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

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

}CTree;樹結構:6.4

樹和森林ABCDEFGrootABCEDFGABCEDFG

樹的二叉鏈表(孩子-兄弟）存儲表示法root6.4

樹和森林typedefstructCSNode{ElemTypedata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C語言的類型描述:結點結構:

firstchilddatanextsibling6.4

樹和森林2、森林與二叉樹的轉換

森林和二叉樹的對應關系

森林轉換成二叉樹

二叉樹轉換成森林6.4

樹和森林

森林和二叉樹的對應關系設森林

F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉樹

B=(LBT,Node(root),RBT);6.4

樹和森林T1T11,T12,…,T1mT2,…,TnLBTRBTroot6.4

樹和森林BCADEBACDE二叉鏈表作為中間媒介6.4

樹和森林BCADBACDFEGHIJACDBGHIJEFFEHIJG樹與二叉樹對應樹根相連森林與二叉樹對應6.4

樹和森林由森林轉換成二叉樹的轉換規(guī)則為:若F=Φ，即m=0，則B=Φ;

由ROOT(T1)

對應得到Node(root);否則，即m

0由(T2,T3,…,Tn)

對應得到RBT。RBT是由(T2,T3,…,Tn)

轉換的二叉樹若F={T1,T2,T3,…,Tn},則按如下規(guī)則轉換二叉樹B=(root,LBT,RBT)：6.4

樹和森林由二叉樹轉換為森林的轉換規(guī)則為:由LBT

對應得到(t11,t12,…，t1m);若B=Φ,則F=Φ;否則，由Node(root)

對應得到ROOT(T1

);由RBT

對應得到(T2,T3,…,Tn)。6.4

樹和森林

由此，樹和森林的各種操作均可與二叉樹的各種操作相對應。

應當注意的是，和樹對應的二叉樹，其左、右子樹的概念已改變?yōu)椋?/p>

左是孩子，右是兄弟6.4

樹和森林

樹的遍歷

森林的遍歷3、樹和森林的遍歷6.4

樹和森林樹的遍歷可有2條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:

若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹。

若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。

若樹不空，則自上而下自左至右訪問樹中每個結點。6.4

樹和森林ABCDEFGHIJK層次遍歷時頂點的訪問次序：

先根遍歷時頂點的訪問次序：ABEFCDGHIJK后根遍歷時頂點的訪問次序：EFBCIJKHGDAABCDEFGHIJK6.4

樹和森林

層次遍歷時頂點的訪問次序：ABCDEFGHIJK

先根遍歷時頂點的訪問次序：ABEFCDGHIJK

后根遍歷時頂點的訪問次序：EFBCIJKHGDAABCDEFGHIJK6.4

樹和森林

BCDEFGHIJK（1）森林中第一棵樹的根結點；（2）森林中第一棵樹的子樹森林；（3）森林中其它樹構成的森林?？梢苑纸獬扇糠郑荷?.4

樹和森林

若森林不空，則訪問森林中第一棵樹的根結點;先序遍歷森林中第一棵樹的子樹森林;先序遍歷森林中(除第一棵樹之外)其余樹構成的森林。先序遍歷

森林的遍歷即：依次從左至右對森林中的每一棵樹進行先根遍歷。6.4

樹和森林

中序遍歷

若森林不空，則中序遍歷森林中第一棵樹的子樹森林;訪問森林中第一棵樹的根結點;中序遍歷森林中(除第一棵樹之外)其

余樹構成的森林。即：依次從左至右對森林中的每一棵樹進行后根遍歷。6.4

樹和森林

樹的遍歷和二叉樹遍歷的對應關系？先根遍歷后根遍歷樹二叉樹森林先序遍歷先序遍歷中序遍歷中序遍歷6.6

赫夫曼樹及其應用

最優(yōu)二叉樹（赫夫曼樹）

如何構造最優(yōu)二叉樹

赫夫曼樹應用

最優(yōu)二叉樹的定義樹的路徑長度定義為：

樹中每個結點的路徑長度之和。

結點的路徑長度定義為：

從根結點到該結點的路徑上分支的數(shù)目。6.6

赫夫曼樹及其應用

樹的帶權路徑長度定義為：

樹中所有葉子結點的帶權路徑長度之和

WPL(T)=

wklk(對所有葉子結點)

其中：wk——權值

lk——結點到根的路徑長度

在所有含n個葉子結點、并帶相同權值的m叉樹中，必存在一棵其帶權路徑長度取最小值的樹，稱為“最優(yōu)二叉樹”。例如：6.6

赫夫曼樹及其應用WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=896.6赫夫曼樹及其應用2475979542

根據(jù)給定的n個權值{w1,w2,…,wn}，構造n棵二叉樹的集合

F={T1,T2,…,Tn}

其中每棵二叉樹中均只含一個帶權值為wi的根結點，其左、右子樹為空樹;

如何構造最優(yōu)二叉樹(1)(赫夫曼算法)以二叉樹為例:6.6赫夫曼樹及其應用

在F中選取其根結點的權值為最小的兩棵二叉樹，分別作為左、右子樹構造一棵新的二叉樹，并置這棵新的二叉樹根結點的權值

為其左、右子樹根結點的權值之和;(2)6.6赫夫曼樹及其應用

從F中刪去這兩棵樹，同時加入剛生成的新樹;

重復(2)和(3)兩步，直至F中只含一棵樹為止。(3)(4)6.6赫夫曼樹及其應用9例如:已知權值W={5,6,2,9,7}5627527697671395276.6赫夫曼樹及其應用67139527952716671329000011110001111001016.6赫夫曼樹及其應用

利用赫夫曼樹解決判別問題分數(shù)0-5960-6970-7980-8990-100比例樹0.050.150.400.300.10A<60A<70A<80A<90不及格及格中等良好優(yōu)秀NNNNYYYY6.6赫夫曼樹及其應用(a)10000個輸入比較31500次利用赫夫曼樹構造最佳判定樹6.6赫夫曼樹及其應用70A<80不及格及格中等良好優(yōu)秀NNYNYYY80A<90A<6060A<70N(b)僅比較22000次A<80不及格及格中等良好優(yōu)秀NNYNYYYNA<70A<90A<60(c)拆分條件515403010

Huffman編碼構造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。6.6赫夫曼樹及其應用

數(shù)據(jù)通信用的二進制編碼思想：根據(jù)字符出現(xiàn)頻率編碼，利