數(shù)據(jù)結(jié)構(gòu)萬扣樹

數(shù)據(jù)結(jié)構(gòu)萬扣樹第1頁，課件共87頁，創(chuàng)作于2023年2月3.1樹的定義一.樹的定義

樹是n個數(shù)據(jù)元素的有限集(記為T)，對任意一棵樹T有：⒈存在唯一一個稱為根的數(shù)據(jù)元素；⒉當n＞1時，其它數(shù)據(jù)元素可分為m(m＞0)個互不相交的有限集T1,T2,…,Tm，其中每個集合Ti(i=1,2,…,m)本身又是一棵樹，并稱樹Ti是根的子樹。第2頁，課件共87頁，創(chuàng)作于2023年2月3.1樹的定義二.樹的表示形式⑴倒懸樹。是最常用的表示形式，如圖6-1(b)。⑵嵌套集合。是一些集合的集體，對于任何兩個集合，或者不相交，或者一個集合包含另一個集合。圖6-2(a)是圖6-1(b)樹的嵌套集合形式。⑶廣義表形式。圖6-2(b)是樹的廣義表形式。⑷凹入法表示形式。見P120

樹的表示方法的多樣化說明了樹結(jié)構(gòu)的重要性。第3頁，課件共87頁，創(chuàng)作于2023年2月3.1樹的定義ABDCEGFHIMJNKL(a)

一般的樹(b)

嵌套集合形式HIJDFBKLECMNGA(c)廣義表形式A(B(E(K,L),F),C(G(M,N)),D(H,I,J)）第4頁，課件共87頁，創(chuàng)作于2023年2月3.1樹的定義三.樹的基本術(shù)語1.樹的結(jié)點:包含一個DE和指向其子樹的所有分支;2.結(jié)點的度:一個結(jié)點擁有的子樹的個數(shù)；度為零的結(jié)點稱為葉結(jié)點;3.樹的度:樹中所有結(jié)點的度的最大值Max(D(I))

含義:樹中最大分支數(shù)為樹的度4.結(jié)點的層次及樹的深度:根為第一層,根的孩子為第二層,若某結(jié)點為第k層,則其孩子為k+1層；樹中結(jié)點的最大層次稱為樹的深度或高度；5.森林:是m(m>=0)棵互不相的樹的集合；森林與樹概念相近,相互很容易轉(zhuǎn)換；第5頁，課件共87頁，創(chuàng)作于2023年2月3.1樹的定義1層2層4層3層depth=4DACBIJHGFEMLKheight=4第6頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹一.二叉樹的概念二叉樹是結(jié)點數(shù)為0或每個結(jié)點最多只有左右兩棵子樹的樹。二叉樹是一種特殊的樹結(jié)構(gòu)，它的特點是：⑴每個結(jié)點最多只有兩棵子樹，即不存在結(jié)點度大于2的結(jié)點；⑵子樹有左右之分，不能顛倒。問題：二叉樹和度為2的樹有何不同？第7頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹二.二叉樹的性質(zhì)性質(zhì)1.

在二叉樹的第i層上至多有2i-1個結(jié)點(i≥1)。證明:用歸納法1.當i=1,即第一層只有一個根結(jié)點,顯然2i-1=

20=1成立2.假設對所有的j上述性質(zhì)成立,即第j層上至多有2j-1個結(jié)點3.要證明i=j+1時,命題也成立。由歸納假設：第j層上至多有2j-1個結(jié)點，又由于二叉樹每個結(jié)點的度最大為2，所以第j+1層上結(jié)點總數(shù)最多為第j層上最大結(jié)點數(shù)的2倍。即2*2j-1=2(j+1)-1第8頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹性質(zhì)2.深度為k的二叉樹至多有2k-1個結(jié)點(k≥1)。（深度一定，二叉樹的最大結(jié)點數(shù)也確定）證明：深度為k的二叉樹的最大結(jié)點數(shù)是二叉樹中每層上結(jié)點的最大數(shù)之和。即

k∑（第i層上結(jié)點的最大數(shù)）i=1k=∑2i-1=1+2+22+……+2k-1=2k-1(等比級數(shù)求和)

i=1第9頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹性質(zhì)3.二叉樹中,終端結(jié)點數(shù)n0與度為2的結(jié)點數(shù)n2有如下關(guān)系:n0=n2+1證明:設二叉樹中度為i的結(jié)點數(shù)為ni,

則結(jié)點總數(shù)n=n0+n1+n2

除根結(jié)點外,每個結(jié)點都是另一結(jié)點的孩子孩子數(shù)=n-1；度為i（i=0，1，2）的結(jié)點，有i個孩子。孩子數(shù)=2n2+n1

n-1=2n2+n1

即n0+n1+n2-1=2n2+n1故n0=

n2+1第10頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹滿二叉樹:深度為k，且有2k-1個結(jié)點的二叉樹。特點：（1）每一層上結(jié)點數(shù)都達到最大（2）度為1的結(jié)點數(shù)n1=0

結(jié)點層序編號方法：從根結(jié)點起從上到下逐層（層內(nèi)從左到右）對二叉樹的結(jié)點進行連續(xù)編號。1237654k=3n=23-1=7

滿二叉樹第11頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹完全二叉樹:深度為k，結(jié)點數(shù)為n的二叉樹，當且僅當每個結(jié)點的編號都與相同深度的滿二叉樹中從1到n的結(jié)點一一對應時，稱為完全二叉樹。452131237654k=3n=23-1=7

滿二叉樹完全二叉樹第12頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹LH2=0RH2=11324653241LH1=3RH1=1LH1-RH1=2

非完全二叉樹非完全二叉樹LH2-RH2=0-1=-1第13頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹性質(zhì)4.

結(jié)點數(shù)為n的完全二叉樹，其深度為└log2n┘+1證明：設深度為k，則由性質(zhì)2和完全二叉樹定義有：結(jié)點數(shù)n滿足：2k-1-1＜n≤2k-1

或?qū)憺?k-1≤n＜2k

于是有：k-1≤log2n＜k

因為k-1和k均為整數(shù)顯然有└log2n┘=k-1,故k=└log2n┘+1第14頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹性質(zhì)5.在按層序編號的n個結(jié)點的完全二叉樹中，任意一結(jié)點i(1≤i≤n)有：⑴i=1時，結(jié)點i是樹的根；否則(i>1)，結(jié)點i的雙親為結(jié)點└i/2┘。⑵2i＞n時，結(jié)點i無左孩子，為葉結(jié)點；否則，結(jié)點i的左孩子為結(jié)點2i。⑶2i+1＞n時，結(jié)點i無右孩子；否則，結(jié)點i的右孩子為結(jié)點2i+1。第15頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹三、二叉樹的存儲結(jié)構(gòu)⒈順序存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元，以層序順序存放二叉樹的數(shù)據(jù)元素，結(jié)點的相對位置蘊含著結(jié)點之間的關(guān)系。

完全二叉樹DCGFEBAbt[3]的雙親為└3/2┘=1，即在bt[1]中；其左孩子在bt[2i]=bt[6]中；其右孩子在bt[2i+1]=bt[7]中。1234567891011ABCDEFG0000bt第16頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹一般二叉樹也按完全二叉樹形式存儲,沒結(jié)點處用0表示D

二叉樹CGFEBA1234567891011ABCDE0000FG0000這種存儲結(jié)構(gòu)適合于完全二叉樹，既不浪費存儲空間，又能很快確定結(jié)點的存放位置、以及結(jié)點的雙親和左右孩子的存放位置，但對一般二叉樹，可能造成存儲空間的浪費。第17頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹例如，深度為k，且只有k個結(jié)點的右單枝樹(每個非葉結(jié)點只有右孩子)，需2k-1個單元，即有2k-1-k個單元被浪費。1k第18頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹⒉鏈式存儲結(jié)構(gòu)設計不同的結(jié)點結(jié)構(gòu)，可以構(gòu)成不同的鏈式存儲結(jié)構(gòu)。常用的有：二叉鏈表三叉鏈表線索鏈表用空鏈域存放指向前驅(qū)或后繼的線索

第19頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹D

二叉樹CEBAACBDE∧∧∧∧∧∧二叉鏈表leftChilddatarightChilddataleftChildrightChild用于二叉樹存儲的鏈表結(jié)構(gòu)，常見的有二叉鏈表和三叉鏈表

二叉鏈表的每個結(jié)點的結(jié)構(gòu)描述如下：structBTNode{intdata; //數(shù)據(jù)域

BTNode*lch; //左指針域

BTNode*rch; //右指針域}第20頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹三叉鏈表的每個結(jié)點的結(jié)構(gòu)描述如下：structnode3{intdata; //數(shù)據(jù)域

node3*lch,*par，*rch;//par是雙親指針域

};leftChilddataparentrightChildparentdataleftChildrightChild第21頁，課件共87頁，創(chuàng)作于2023年2月(2)二叉樹的鏈式存儲形式例有一棵一般的二叉樹，如圖6-8(a)所示。以二叉鏈表和三叉鏈表方式存儲的結(jié)構(gòu)圖分別如圖6-8(b)、6-8(c)所示。圖6-8二叉樹及其鏈式存儲結(jié)構(gòu)(a)二叉樹afedcbg(c)三叉鏈表

a?

?

b?

c?

d?

e?

f??

g?T(b)二叉鏈表

a?

b?c?

d?e?g??f?T第22頁，課件共87頁，創(chuàng)作于2023年2月3.2二叉樹性質(zhì)6.含有n個結(jié)點的二叉鏈表中，有n+1個空鏈域。證明：空鏈域數(shù)=2n0+n1

因為n=n0+n1+n2（1）

又有n0=n2+1即-1=n2-n0（2）（1）-（2）得n+1=2n0+n1

故空鏈域數(shù)=n+1第23頁，課件共87頁，創(chuàng)作于2023年2月3.3遍歷二叉樹二叉樹最主要、最基本的運算是遍歷。遍歷二叉樹是指以一定的次序訪問二叉樹中的每個結(jié)點，并且每個結(jié)點僅被訪問一次。訪問結(jié)點是指對結(jié)點進行各種操作的簡稱。例如，查詢結(jié)點數(shù)據(jù)域的內(nèi)容，或輸出它的值，或找出結(jié)點位置，或是執(zhí)行對結(jié)點的其他操作。遍歷二叉樹的過程實質(zhì)是把二叉樹的結(jié)點進行線性排列的過程。第24頁，課件共87頁，創(chuàng)作于2023年2月3.3遍歷二叉樹二叉樹的遍歷就是按某種次序訪問樹中的結(jié)點，要求每個結(jié)點訪問一次且僅訪問一次。設訪問根結(jié)點記作

V

遍歷根的左子樹記作

L

遍歷根的右子樹記作

R則可能的遍歷次序有

前序VLR

中序

LVR

后序LRV第25頁，課件共87頁，創(chuàng)作于2023年2月3.3遍歷二叉樹對于二叉樹的遍歷，分別討論遞歸遍歷算法和非遞歸遍歷算法。遞歸遍歷算法具有非常清晰的結(jié)構(gòu)，但初學者往往難以接受或懷疑，不敢使用。實際上，遞歸算法是由系統(tǒng)通過使用堆棧來實現(xiàn)控制的。而非遞歸算法中的控制是由設計者定義和使用堆棧來實現(xiàn)的。第26頁，課件共87頁，創(chuàng)作于2023年2月3.3遍歷二叉樹第27頁，課件共87頁，創(chuàng)作于2023年2月3.3.1先序遍歷二叉樹1遞歸算法算法的遞歸定義是：若二叉樹為空，則遍歷結(jié)束；否則⑴訪問根結(jié)點；⑵先序遍歷左子樹(遞歸調(diào)用本算法)；⑶先序遍歷右子樹(遞歸調(diào)用本算法)。第28頁，課件共87頁，創(chuàng)作于2023年2月3.3.1遍歷二叉樹先序遍歷的遞歸算法voidPreorderTraverse(BTNode*T){if(T!=NULL){visit(T->data);/*訪問根結(jié)點

*/PreorderTraverse(T->Lchild);PreorderTraverse(T->Rchild);}}說明：visit()函數(shù)是訪問結(jié)點的數(shù)據(jù)域，其要求視具體問題而定。樹采用二叉鏈表的存儲結(jié)構(gòu)，用指針變量T來指向。第29頁，課件共87頁，創(chuàng)作于2023年2月3.3.1遍歷二叉樹第30頁，課件共87頁，創(chuàng)作于2023年2月3.3.1遍歷二叉樹－/fe-dcb*a+第31頁，課件共87頁，創(chuàng)作于2023年2月3.3.1遍歷二叉樹2非遞歸算法設T是指向二叉樹根結(jié)點的指針變量，非遞歸算法是：若二叉樹為空，則返回；否則，令p=T；⑴訪問p所指向的結(jié)點；⑵q=p->Rchild，若q不為空，則q進棧；⑶p=p->Lchild，若p不為空，轉(zhuǎn)(1)，否則轉(zhuǎn)(4)；⑷退棧到p，轉(zhuǎn)(1)，直到棧空為止。算法實現(xiàn)：第32頁，課件共87頁，創(chuàng)作于2023年2月#defineMAX_NODE50voidPreorderTraverse(BTNode*T){BTNode*Stack[MAX_NODE],*p=T,*q;inttop=0;if(T==NULL)cout<<“BinaryTreeisEmpty!\n”;else{do{visit(p->data);q=p->Rchild;if(q!=NULL)stack[++top]=q;p=p->Lchild;if(p==NULL&&top>0){p=stack[top];top--;}}while(p!=NULL);}}第33頁，課件共87頁，創(chuàng)作于2023年2月3.3.2中序遍歷二叉樹1遞歸算法算法的遞歸定義是：若二叉樹為空，則遍歷結(jié)束；否則⑴中序遍歷左子樹(遞歸調(diào)用本算法)；⑵訪問根結(jié)點；⑶中序遍歷右子樹(遞歸調(diào)用本算法)。第34頁，課件共87頁，創(chuàng)作于2023年2月3.3.2中序遍歷二叉樹中序遍歷的遞歸算法voidInorderTraverse(BTNode*T){if(T!=NULL){InorderTraverse(T->Lchild);visit(T->data);/*訪問根結(jié)點*/InorderTraverse(T->Rchild);}}

/*圖6-8(a)的二叉樹，輸出的次序是：cbegdfa*/第35頁，課件共87頁，創(chuàng)作于2023年2月3.3.2中序遍歷二叉樹2非遞歸算法設T是指向二叉樹根結(jié)點的指針變量，非遞歸算法是：若二叉樹為空，則返回；否則，令p=T⑴若p不為空，p進棧，p=p->Lchild；⑵否則(即p為空)，退棧到p，訪問p所指向的結(jié)點；⑶p=p->Rchild，轉(zhuǎn)(1)；直到棧空為止。算法實現(xiàn)：第36頁，課件共87頁，創(chuàng)作于2023年2月#defineMAX_NODE50voidInorderTraverse(BTNode*T){BTNode*Stack[MAX_NODE],*p=T;inttop=0,bool=1;if(T==NULL)printf(“BinaryTreeisEmpty!\n”);else{do{while(p!=NULL){stack[++top]=p;p=p->Lchild;}if(top==0)bool=0;else{p=stack[top];--top;visit(p->data);p=p->Rchild;}}while(bool!=0);}}第37頁，課件共87頁，創(chuàng)作于2023年2月3.3.3后序遍歷二叉樹1遞歸算法算法的遞歸定義是：若二叉樹為空，則遍歷結(jié)束；否則⑴后序遍歷左子樹(遞歸調(diào)用本算法)；⑵后序遍歷右子樹(遞歸調(diào)用本算法)；⑶訪問根結(jié)點。第38頁，課件共87頁，創(chuàng)作于2023年2月后序遍歷的遞歸算法voidPostorderTraverse(BTNode*T){if(T!=NULL){PostorderTraverse(T->Lchild);PostorderTraverse(T->Rchild);visit(T->data);/*訪問根結(jié)點*/

}}

/*圖6-8(a)

的二叉樹，輸出的次序是：cgefdba*/遍歷二叉樹的算法中基本操作是訪問結(jié)點，因此，無論是哪種次序的遍歷，對有n個結(jié)點的二叉樹，其時間復雜度均為O(n)。第39頁，課件共87頁，創(chuàng)作于2023年2月3.3.3后序遍歷二叉樹

如圖6-9所示的二叉樹表示表達式：(a+b*(c-d)-e/f)按不同的次序遍歷此二叉樹，將訪問的結(jié)點按先后次序排列起來的次序是：其先序序列為：-+a*b-cd/ef

其中序序列為：a+b*c-d-e/f

其后序序列為：abcd-*+ef/-－/fe-dcb*a+圖6-9

表達式(a+b*(c-d)-e/f)二叉樹第40頁，課件共87頁，創(chuàng)作于2023年2月3.3.3后序遍歷二叉樹2非遞歸算法在后序遍歷中，根結(jié)點是最后被訪問的。因此，在遍歷過程中，當搜索指針指向某一根結(jié)點時，不能立即訪問，而要先遍歷其左子樹，此時根結(jié)點進棧。當其左子樹遍歷完后再搜索到該根結(jié)點時，還是不能訪問，還需遍歷其右子樹。所以，此根結(jié)點還需再次進棧，當其右子樹遍歷完后再退棧到到該根結(jié)點時，才能被訪問。因此，設立一個狀態(tài)標志變量tag：0：結(jié)點暫不能訪問1：結(jié)點可以被訪問tag=第41頁，課件共87頁，創(chuàng)作于2023年2月其次，設兩個堆棧S1、S2

，S1保存結(jié)點，S2保存結(jié)點的狀態(tài)標志變量tag。S1和S2共用一個棧頂指針。設T是指向根結(jié)點的指針變量，非遞歸算法是：若二叉樹為空，則返回；否則，令p=T；⑴第一次經(jīng)過根結(jié)點p，不訪問：

p進棧S1，tag賦值0，進棧S2，p=p->Lchild。⑵若p不為空，轉(zhuǎn)(1)，否則，取狀態(tài)標志值tag：

⑶若tag=0：對棧S1，不訪問，不出棧；修改S2棧頂元素值(tag賦值1)，取S1棧頂元素的右子樹，即p=S1[top]->Rchild，轉(zhuǎn)(1)；⑷若tag=1：S1退棧，訪問該結(jié)點；直到棧空為止。第42頁，課件共87頁，創(chuàng)作于2023年2月算法實現(xiàn)：#defineMAX_NODE50voidPostorderTraverse(BTNode*T){BTNode*S1[MAX_NODE],*p=T;intS2[MAX_NODE],top=0,bool=1;if(T==NULL)cout<<“BinaryTreeisEmpty!\n”;else{do{while(p!=NULL){S1[++top]=p;S2[top]=0;p=p->Lchild;}if(top==0)bool=0;第43頁，課件共87頁，創(chuàng)作于2023年2月

elseif(S2[top]==0){p=S1[top]->Rchild;S2[top]=1;}else{p=S1[top];top--;visit(p->data);p=NULL;

/*使循環(huán)繼續(xù)進行而不至于死循環(huán)*/

}}while(bool!=0);}}第44頁，課件共87頁，創(chuàng)作于2023年2月3.4層次遍歷二叉樹層次遍歷二叉樹，是從根結(jié)點開始遍歷，按層次次序“自上而下，從左至右”訪問樹中的各結(jié)點。為保證是按層次遍歷，必須設置一個隊列，初始化時為空。設T是指向根結(jié)點的指針變量，層次遍歷非遞歸算法是：若二叉樹為空，則返回；否則，令p=T，p入隊；⑴隊首元素出隊到p；⑵訪問p所指向的結(jié)點；⑶將p所指向的結(jié)點的左、右子結(jié)點依次入隊。直到隊空為止。第45頁，課件共87頁，創(chuàng)作于2023年2月#defineMAX_NODE50voidLevelorderTraverse(BTNode*T){BTNode*Queue[MAX_NODE],*p=T;intfront=0,rear=0;if(p!=NULL){Queue[++rear]=p;/*根結(jié)點入隊*/while(front<rear){p=Queue[++front];visit(p->data);if(p->Lchild!=NULL)Queue[++rear]=p->Lch;/*左結(jié)點入隊*/if(p->Rchild!=NULL)Queue[++rear]=p->Rch;/*右結(jié)點入隊*/}}}第46頁，課件共87頁，創(chuàng)作于2023年2月3.5二叉樹遍歷算法的應用“遍歷”是二叉樹最重要的基本操作，是各種其它操作的基礎(chǔ)，二叉樹的許多其它操作都可以通過遍歷來實現(xiàn)。如建立二叉樹的存儲結(jié)構(gòu)、求二叉樹的結(jié)點數(shù)、求二叉樹的深度等。第47頁，課件共87頁，創(chuàng)作于2023年2月3.5二叉樹遍歷算法的應用1二叉樹的二叉鏈表創(chuàng)建⑴

按滿二叉樹方式建立(補充)

在此補充按滿二叉樹的方式對結(jié)點進行編號建立鏈式二叉樹。對每個結(jié)點，輸入i、ch。i：結(jié)點編號，按從小到大的順序輸入ch：結(jié)點內(nèi)容，假設是字符在建立過程中借助一個一維數(shù)組S[n]，編號為i的結(jié)點保存在S[i]中。算法實現(xiàn)：第48頁，課件共87頁，創(chuàng)作于2023年2月#defineMAX_NODE50structBTNode{chardata;structBTNode*Lchild,*Rchild;};BTNode*Create_BTree(void)

/*建立鏈式二叉樹，返回指向根結(jié)點的指針變量*/{BTNode*T,*p,*s[MAX_NODE];charch;inti,j;while(1){cin>>i;if(i==0)break;/*以編號0作為輸入結(jié)束*/else{ch=getchar();第49頁，課件共87頁，創(chuàng)作于2023年2月

p=newBTNode;

p–>data=ch;p–>Lchild=p–>Rchild=NULL;s[i]=p;if(i==1)T=p;else{j=i/2;/*j是i的雙親結(jié)點編號*/

if(i%2==0)s[j]->Lchild=p;elses[j]->Rchild=p;}}}return(T);}第50頁，課件共87頁，創(chuàng)作于2023年2月3.5二叉樹遍歷算法的應用⑵

按先序遍歷方式建立對一棵二叉樹進行“擴充”，就可以得到有該二叉樹所擴充的二叉樹。有兩棵二叉樹T1及其擴充的二叉樹T2如圖6-10所示。圖6-10

二叉樹T1及其擴充二叉樹T2ABCDEFG(a)

二叉樹T1(b)

T1的擴充二叉樹T2ABCDEFG????????第51頁，課件共87頁，創(chuàng)作于2023年2月3.5二叉樹遍歷算法的應用二叉樹的擴充方法是：在二叉樹中結(jié)點的每一個空鏈域處增加一個擴充的結(jié)點(總是葉子結(jié)點，用方框“□”表示)。對于二叉樹的結(jié)點值：◆

是char類型：擴充結(jié)點值為“？”；◆是int類型：擴充結(jié)點值為0或-1；下面的算法是二叉樹的前序創(chuàng)建的遞歸算法，讀入一棵二叉樹對應的擴充二叉樹的前序遍歷的結(jié)點值序列。每讀入一個結(jié)點值就進行分析：◆若是擴充結(jié)點值：令根指針為NULL；◆若是(正常)結(jié)點值：動態(tài)地為根指針分配一個結(jié)點，將該值賦給根結(jié)點，然后遞歸地創(chuàng)建根的左子樹和右子樹。第52頁，課件共87頁，創(chuàng)作于2023年2月#defineNULLKY‘?’#defineMAX_NODE50structBTNode{chardata;structBTNode*Lchild,*Rchild;};BTNode*Preorder_Create_BTree(BTNode*T)

/*建立鏈式二叉樹，返回指向根結(jié)點的指針變量*/{charch;ch=getchar();getchar();if(ch==NULLKY){T=NULL;return(T);}第53頁，課件共87頁，創(chuàng)作于2023年2月3.5二叉樹遍歷算法的應用else{T=newBTNode;T–>data=ch;Preorder_Create_BTree(T->Lchild);Preorder_Create_BTree(T->Rchild);return(T);}}

當希望創(chuàng)建圖6-10(a)所示的二叉樹時，輸入的字符序列應當是：ABD??E?G??CF???第54頁，課件共87頁，創(chuàng)作于2023年2月3.5二叉樹遍歷算法的應用2求二叉樹的葉子結(jié)點數(shù)可以直接利用先序遍歷二叉樹算法求二叉樹的葉子結(jié)點數(shù)。只要將先序遍歷二叉樹算法中vist()函數(shù)簡單地進行修改就可以。(遞歸與非遞歸)#defineMAX_NODE50intsearch_leaves(BTNode*T){BTNode*Stack[MAX_NODE],*p=T;inttop=0,num=0;if(T!=NULL)第55頁，課件共87頁，創(chuàng)作于2023年2月{stack[++top]=p;while(top>0){p=stack[top--];if(p->Lchild==NULL&&p->Rchild==NULL)num++;if(p->Rchild!=NULL)stack[++top]=p->Rchild;if(p->Lchild!=NULL)stack[++top]=p->Lchild;

}}return(num);}第56頁，課件共87頁，創(chuàng)作于2023年2月3.5二叉樹遍歷算法的應用求二叉樹的深度intDepth(BTNode*T){if(T==NULL)depthval=0;else{depthLeft=Depth(T->Lchild);depthRight=Depth(T->Rchild);depthval=1+max(depthLeft,depthRight);}

returndepthval;}

第57頁，課件共87頁，創(chuàng)作于2023年2月3.5二叉樹遍歷算法的應用3求二叉樹的深度

利用層次遍歷算法可以直接求得二叉樹的深度。#defineMAX_NODE50intsearch_depth(BTNode*T){

BTNode*Stack[MAX_NODE],*p=T;intfront=0,rear=0,depth=0,level;/*level總是指向訪問層的最后一個結(jié)點在隊列的位置*/if(T!=NULL){Queue[++rear]=p;/*根結(jié)點入隊*/level=rear;/*根是第1層的最后一個節(jié)點*/第58頁，課件共87頁，創(chuàng)作于2023年2月while(front<rear){p=Queue[++front];if(p->Lchild!=NULL)Queue[++rear]=p->Lchild;/*左結(jié)點入隊*/if(p->Rchild!=NULL)Queue[++rear]=p->Rchild;/*右結(jié)點入隊*/

if(front==level)

/*正訪問的是當前層的最后一個結(jié)點*/

{depth++;level=rear;}}}}第59頁，課件共87頁，創(chuàng)作于2023年2月3.6哈夫曼樹的構(gòu)造哈夫曼樹（Huffman）樹是一類帶權(quán)路徑長度最短的樹一、Huffman樹（最優(yōu)二叉樹）1、概念兩結(jié)點間的路徑：從一個結(jié)點到另一個結(jié)點之間的分支路徑長度：路徑上的分支數(shù)目樹的路徑長度：從根到每一結(jié)點的路徑長度之和2763415例⑴-⑵-⑸為結(jié)點1到5之間的路徑，其路徑長度為2，樹的路徑長度=l12+l13+

l14+l15+

l16+l17

=1+1+2+2+2+2=10第60頁，課件共87頁，創(chuàng)作于2023年2月3.6哈夫曼樹的構(gòu)造

完全二叉樹是路徑長度最短的二叉樹?？紤]帶權(quán)時：設樹中有m個葉結(jié)點，每個葉結(jié)點帶一個權(quán)值Wｉ且根到葉結(jié)點i的路徑長度為Li(ｉ=1，2，…，m），則樹的帶權(quán)路徑長度為樹中所有葉結(jié)點的權(quán)值與路徑長度的乘積的總和。

m

即：ＷＰＬ＝∑ＷkＬk

k=1

第61頁，課件共87頁，創(chuàng)作于2023年2月3.6哈夫曼樹的構(gòu)造

例：使WPL最小的二叉樹稱為最優(yōu)二叉樹(Huffman樹)完全二叉樹dcab7524

cdba2475WPLa=2*7+2*5+2*2+2*4WPLb=7*3+5*3+2*1+4*2=36=46第62頁，課件共87頁，創(chuàng)作于2023年2月3.6哈夫曼樹的構(gòu)造Huffman樹WPLc=7*1+5*2+2*3+4*3=35bdca7524（1）完全二叉樹并不一定是Huffman樹；（2）HT是權(quán)值越大的越靠近根結(jié)點；（3）HT不唯一，但WPL一定相等。第63頁，課件共87頁，創(chuàng)作于2023年2月3.6哈夫曼樹的構(gòu)造2．構(gòu)造Huffman樹算法(1)以權(quán)值分別為W1,W2．．．Ｗｎ的ｎ個結(jié)點，構(gòu)成n棵二叉樹T1,T2,．．．Tn并組成森林F={T1,T2,．．．Tn},其中每棵二叉樹Ti僅有一個權(quán)值為Wi的根結(jié)點；(2)在F中選取兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造一棵新二叉樹，并且置新二叉樹根結(jié)點權(quán)值為左右子樹上根結(jié)點的權(quán)值之和（根結(jié)點的權(quán)值=左右孩子權(quán)值之和，葉結(jié)點的權(quán)值=Wi）；(3)從F中刪除這兩棵二叉樹，同時將新二叉樹加入到F中;(4)重復(2)．(３)直到F中只含一棵二叉樹為止，這棵二叉樹就是Huffman樹。第64頁，課件共87頁，創(chuàng)作于2023年2月3.6哈夫曼樹的構(gòu)造abcd7524例:F={}abF={}cd

756

24F={}abcd116425F={}abcd1164257187第65頁，課件共87頁，創(chuàng)作于2023年2月3.6哈夫曼樹的構(gòu)造HT不唯一性,可能出現(xiàn)在:（1）構(gòu)造新樹時，左、右孩子未作規(guī)定。（2）當有多個權(quán)值相同的樹，可作為候選樹時，選擇誰未作規(guī)定。第66頁，課件共87頁，創(chuàng)作于2023年2月3.6哈夫曼樹的構(gòu)造1Huffman編碼在電報收發(fā)等數(shù)據(jù)通訊中，常需要將傳送的文字轉(zhuǎn)換成由二進制字符0、1組成的字符串來傳輸。為了使收發(fā)的速度提高，就要求電文編碼要盡可能地短。此外，要設計長短不等的編碼，還必須保證任意字符的編碼都不是另一個字符編碼的前綴，這種編碼稱為前綴編碼。

Huffman樹可以用來構(gòu)造編碼長度不等且譯碼不產(chǎn)生二義性的編碼。設電文中的字符集C={c1,c2,?,ci,?,cn}，各個字符出現(xiàn)的次數(shù)或頻度集W={w1,w2,?,wi,?,wn}。第67頁，課件共87頁，創(chuàng)作于2023年2月3.6哈夫曼樹的構(gòu)造Huffman編碼方法以字符集C作為葉子結(jié)點，次數(shù)或頻度集W作為結(jié)點的權(quán)值來構(gòu)造Huffman樹。規(guī)定Huffman樹中左分支代表“0”，右分支代表“1”。

從根結(jié)點到每個葉子結(jié)點所經(jīng)歷的路徑分支上的“0”或“1”所組成的字符串，為該結(jié)點所對應的編碼，稱之為Huffman編碼。由于每個字符都是葉子結(jié)點，不可能出現(xiàn)在根結(jié)點到其它字符結(jié)點的路徑上，所以一個字符的Huffman編碼不可能是另一個字符的Huffman編碼的前綴。第68頁，課件共87頁，創(chuàng)作于2023年2月若字符集C={a,b,c,d,e,f}所對應的權(quán)值集合為W={8,3,4,6,5,5}，如圖6-25所示，則字符a,b,c,d,e,f所對應的Huffman編碼分別是：10，010，011，00，110，111。2Huffman編碼算法實現(xiàn)(1)數(shù)據(jù)結(jié)構(gòu)設計

Huffman樹中沒有度為1的結(jié)點棵有n個葉子結(jié)點的Huffman樹共有2n-1個結(jié)點，則可存儲在大小為2n-1的一維數(shù)組中。實現(xiàn)編碼的結(jié)點結(jié)構(gòu)如圖6-26所示。原因：◆求編碼需從葉子結(jié)點出發(fā)走一條從葉子到根的路徑；第69頁，課件共87頁，創(chuàng)作于2023年2月◆譯碼需從根結(jié)點出發(fā)走一條到葉子結(jié)點的路徑。結(jié)點類型定義：#defineMAX_NODE200/*Max_Node>2n-1

*/

typedefstruct{unsignedintWeight;/*權(quán)值域*/unsingedintParent,Lchild,Rchild;}HTNode;WeightParentLchildRchildWeight：權(quán)值域；Parent：雙親結(jié)點下標Lchild,Rchild：分別標識左、右子樹的下標圖6-26Huffman編碼的結(jié)點結(jié)構(gòu)第70頁，課件共87頁，創(chuàng)作于2023年2月(2)Huffman樹的生成算法實現(xiàn)voidCreate_Huffman(unsignedn,HTNodeHT[],unsignedm)/*創(chuàng)建一棵葉子結(jié)點數(shù)為n的Huffman樹*/{unsignedintw;intk,j;for(k=1;k<m;k++){if(k<=n){printf(“\nPleaseInputWeight:w=?”);scanf(“%d”,&w);HT[k].weight=w;}/*輸入時，所有葉子結(jié)點都有權(quán)值*/elseHT[k].weight=0;/*

非葉子結(jié)點沒有權(quán)值*/第71頁，課件共87頁，創(chuàng)作于2023年2月HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;}/*初始化向量HT*/for(k=n+1;k<m;k++){unsignedw1=32767,w2=w1;

/*w1,w2分別保存權(quán)值最小的兩個權(quán)值*/intp1=0,p2=0;

/*p1,p2保存兩個最小權(quán)值的下標*/for(j=1;j<=k-1;j++){if(HT[k].Parent==0)/*尚未合并*/{if(HT[j].Weight<w1){w2=w1;p2=p1;w1=HT[j].Weight;p1=j;}第72頁，課件共87頁，創(chuàng)作于2023年2月

elseif(HT[j].Weight<w2){w2=HT[j].Weight;p2=j;}}/*

找到權(quán)值最小的兩個值及其下標*/}HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].weight=w1+w2;HT[p1].Parent=k;HT[p2].Parent=k;}}說明：生成Huffman樹后，樹的根結(jié)點的下標是2n-1，即m-1。第73頁，課件共87頁，創(chuàng)作于2023年2月(3)Huffman編碼算法根據(jù)出現(xiàn)頻度(權(quán)值)Weight，對葉子結(jié)點的Huffman編碼有兩種方式：①從葉子結(jié)點到根逆向處理，求得每個葉子結(jié)點對應字符的Huffman編碼。②從根結(jié)點開始遍歷整棵二叉樹，求得每個葉子結(jié)點對應字符的Huffman編碼。由Huffman樹的生成知，n個葉子結(jié)點的樹共有2n-1個結(jié)點，葉子結(jié)點存儲在數(shù)組HT中的下標值為1∽n。①編碼是葉子結(jié)點的編碼，只需對數(shù)組HT[1…n]的n個權(quán)值進行編碼；②每個字符的編碼不同，但編碼的最大長度是n。第74頁，課件共87頁，創(chuàng)作于2023年2月求編碼時先設一個通用的指向字符的指針變量，求得編碼后再復制。算法實現(xiàn)voidHuff_coding(unsignedn,HnodeHT[],unsignedm)/*m應為n+1,編碼的最大長度n加1

*/{intk,sp,fp;char*cd,*HC[m];cd=(char*)malloc(m*sizeof(char));/*動態(tài)分配求編碼的工作空間*/cd[n]=‘\0’

/*編碼的結(jié)束標志

*/for(k=1;k<n+1;k++)/*逐個求字符的編碼*/{sp=n;p=k;fp=HT[k].parent;

第75頁，課件共87頁，創(chuàng)作于2023年2月for(;fp!=0;p=fp,fp=HT[p].parent)

/*從葉子結(jié)點到根逆向求編碼*/

if(HT[fp