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

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

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

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

一般的樹(shù)(b)

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

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

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

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

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

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

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

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

n-1=2n2+n1

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

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

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

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

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

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

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

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

于是有：k-1≤log2n＜k

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

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

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

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

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

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

BTNode*lch; //左指針域

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

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

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

a?

?

b?

c?

d?

e?

f??

g?T(b)二叉鏈表

a?

b?c?

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

因?yàn)閚=n0+n1+n2（1）

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

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

V

遍歷根的左子樹(shù)記作

L

遍歷根的右子樹(shù)記作

R則可能的遍歷次序有

前序VLR

中序

LVR

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

*/PreorderTraverse(T->Lchild);PreorderTraverse(T->Rchild);}}說(shuō)明：visit()函數(shù)是訪問(wèn)結(jié)點(diǎn)的數(shù)據(jù)域，其要求視具體問(wèn)題而定。樹(shù)采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)，用指針變量T來(lái)指向。第29頁(yè)，課件共87頁(yè)，創(chuàng)作于2023年2月3.3.1遍歷二叉樹(shù)第30頁(yè)，課件共87頁(yè)，創(chuàng)作于2023年2月3.3.1遍歷二叉樹(shù)－/fe-dcb*a+第31頁(yè)，課件共87頁(yè)，創(chuàng)作于2023年2月3.3.1遍歷二叉樹(shù)2非遞歸算法設(shè)T是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，非遞歸算法是：若二叉樹(shù)為空，則返回；否則，令p=T；⑴訪問(wèn)p所指向的結(jié)點(diǎn)；⑵q=p->Rchild，若q不為空，則q進(jìn)棧；⑶p=p->Lchild，若p不為空，轉(zhuǎn)(1)，否則轉(zhuǎn)(4)；⑷退棧到p，轉(zhuǎn)(1)，直到?？諡橹埂Ｋ惴▽?shí)現(xiàn)：第32頁(yè)，課件共87頁(yè)，創(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頁(yè)，課件共87頁(yè)，創(chuàng)作于2023年2月3.3.2中序遍歷二叉樹(shù)1遞歸算法算法的遞歸定義是：若二叉樹(shù)為空，則遍歷結(jié)束；否則⑴中序遍歷左子樹(shù)(遞歸調(diào)用本算法)；⑵訪問(wèn)根結(jié)點(diǎn)；⑶中序遍歷右子樹(shù)(遞歸調(diào)用本算法)。第34頁(yè)，課件共87頁(yè)，創(chuàng)作于2023年2月3.3.2中序遍歷二叉樹(shù)中序遍歷的遞歸算法voidInorderTraverse(BTNode*T){if(T!=NULL){InorderTraverse(T->Lchild);visit(T->data);/*訪問(wèn)根結(jié)點(diǎn)*/InorderTraverse(T->Rchild);}}

/*圖6-8(a)的二叉樹(shù)，輸出的次序是：cbegdfa*/第35頁(yè)，課件共87頁(yè)，創(chuàng)作于2023年2月3.3.2中序遍歷二叉樹(shù)2非遞歸算法設(shè)T是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，非遞歸算法是：若二叉樹(shù)為空，則返回；否則，令p=T⑴若p不為空，p進(jìn)棧，p=p->Lchild；⑵否則(即p為空)，退棧到p，訪問(wèn)p所指向的結(jié)點(diǎn)；⑶p=p->Rchild，轉(zhuǎn)(1)；直到?？諡橹埂Ｋ惴▽?shí)現(xiàn)：第36頁(yè)，課件共87頁(yè)，創(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頁(yè)，課件共87頁(yè)，創(chuàng)作于2023年2月3.3.3后序遍歷二叉樹(shù)1遞歸算法算法的遞歸定義是：若二叉樹(shù)為空，則遍歷結(jié)束；否則⑴后序遍歷左子樹(shù)(遞歸調(diào)用本算法)；⑵后序遍歷右子樹(shù)(遞歸調(diào)用本算法)；⑶訪問(wèn)根結(jié)點(diǎn)。第38頁(yè)，課件共87頁(yè)，創(chuàng)作于2023年2月后序遍歷的遞歸算法voidPostorderTraverse(BTNode*T){if(T!=NULL){PostorderTraverse(T->Lchild);PostorderTraverse(T->Rchild);visit(T->data);/*訪問(wèn)根結(jié)點(diǎn)*/

}}

/*圖6-8(a)

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

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

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

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

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

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

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

⑶若tag=0：對(duì)棧S1，不訪問(wèn)，不出棧；修改S2棧頂元素值(tag賦值1)，取S1棧頂元素的右子樹(shù)，即p=S1[top]->Rchild，轉(zhuǎn)(1)；⑷若tag=1：S1退棧，訪問(wèn)該結(jié)點(diǎn)；直到棧空為止。第42頁(yè)，課件共87頁(yè)，創(chuàng)作于2023年2月算法實(shí)現(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頁(yè)，課件共87頁(yè)，創(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ù)進(jìn)行而不至于死循環(huán)*/

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

按滿二叉樹(shù)方式建立(補(bǔ)充)

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

/*建立鏈?zhǔn)蕉鏄?shù)，返回指向根結(jié)點(diǎn)的指針變量*/{BTNode*T,*p,*s[MAX_NODE];charch;inti,j;while(1){cin>>i;if(i==0)break;/*以編號(hào)0作為輸入結(jié)束*/else{ch=getchar();第49頁(yè)，課件共87頁(yè)，創(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é)點(diǎn)編號(hào)*/

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

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

二叉樹(shù)T1及其擴(kuò)充二叉樹(shù)T2ABCDEFG(a)

二叉樹(shù)T1(b)

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

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

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

當(dāng)希望創(chuàng)建圖6-10(a)所示的二叉樹(shù)時(shí)，輸入的字符序列應(yīng)當(dāng)是：ABD??E?G??CF???第54頁(yè)，課件共87頁(yè)，創(chuàng)作于2023年2月3.5二叉樹(shù)遍歷算法的應(yīng)用2求二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)可以直接利用先序遍歷二叉樹(shù)算法求二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)。只要將先序遍歷二叉樹(shù)算法中vist()函數(shù)簡(jiǎn)單地進(jìn)行修改就可以。(遞歸與非遞歸)#defineMAX_NODE50intsearch_leaves(BTNode*T){BTNode*Stack[MAX_NODE],*p=T;inttop=0,num=0;if(T!=NULL)第55頁(yè)，課件共87頁(yè)，創(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頁(yè)，課件共87頁(yè)，創(chuàng)作于2023年2月3.5二叉樹(shù)遍歷算法的應(yīng)用求二叉樹(shù)的深度intDepth(BTNode*T){if(T==NULL)depthval=0;else{depthLeft=Depth(T->Lchild);depthRight=Depth(T->Rchild);depthval=1+max(depthLeft,depthRight);}

returndepthval;}

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

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

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

if(front==level)

/*正訪問(wèn)的是當(dāng)前層的最后一個(gè)結(jié)點(diǎn)*/

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

l14+l15+

l16+l17

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

完全二叉樹(shù)是路徑長(zhǎng)度最短的二叉樹(shù)。考慮帶權(quán)時(shí)：設(shè)樹(shù)中有m個(gè)葉結(jié)點(diǎn)，每個(gè)葉結(jié)點(diǎn)帶一個(gè)權(quán)值Wｉ且根到葉結(jié)點(diǎn)i的路徑長(zhǎng)度為L(zhǎng)i(ｉ=1，2，…，m），則樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉結(jié)點(diǎn)的權(quán)值與路徑長(zhǎng)度的乘積的總和。

m

即：ＷＰＬ＝∑ＷkＬk

k=1

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

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

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

756

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

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

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

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

*/

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

非葉子結(jié)點(diǎn)沒(méi)有權(quán)值*/第71頁(yè)，課件共87頁(yè)，創(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)值最小的兩個(gè)權(quán)值*/intp1=0,p2=0;

/*p1,p2保存兩個(gè)最小權(quán)值的下標(biāo)*/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頁(yè)，課件共87頁(yè)，創(chuàng)作于2023年2月

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

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

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

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

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

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

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

if(HT[fp