數(shù)據(jù)結(jié)構(gòu)2第6章

1、6樹6.1 和、子有6.1 和和6樹6.1 和、子有6.1 和和(2（Subtree。(2（Subtree。6.2（a）是根結(jié)點(diǎn)，T T1=B，E，F(xiàn)，I，J，T2=C,T3=D,G,H。T1、T2A 的三，且本身又都是一棵樹。例如 T1，其為 B，其余結(jié)點(diǎn)可分為兩個(gè)互不相交的子集 T11=ET12=F，I，JB根結(jié)E 的樹，F(xiàn) 又有兩顆互不相交表示法外，通常還有三種表示法。例如，圖 6.2（a）所示6.2（be）則是用廣義表的形勢(shì)表示的。本書中主要采用圖 6.2表示法外，通常還有三種表示法。例如，圖 6.2（a）所示6.2（be）則是用廣義表的形勢(shì)表示的。本書中主要采用圖 6.2（a）（De

2、gree除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)之外的分支結(jié)點(diǎn)統(tǒng)稱為結(jié)之根成為該結(jié)點(diǎn)的孩子親。6.2（a）中，B 是結(jié)A T1 的根B （Sibling k1，k2，kj，使得 若樹中存在一個(gè)結(jié)點(diǎn)序是的雙親（1ij則稱該結(jié)點(diǎn)序列是的一條6.2（a）中，結(jié)A I 有一條路徑ABFI，它的長(zhǎng)度為 3。顯然，從樹的根結(jié)點(diǎn)到樹中其余結(jié)點(diǎn)均存在已條唯能從 G 出發(fā)“自上而下”地經(jīng)過若干結(jié)點(diǎn)到達(dá)B。tor，k8 （eceator，k8 （ecea6.2（a）所示的樹中，F(xiàn) A IJ余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加 1。雙親在同一層的結(jié)點(diǎn)互為堂兄弟。樹中結(jié)點(diǎn)的最大層數(shù)成為樹的高度Depth1 ，I J 4，E、F G、H

3、互為堂兄弟，Tree；否 tree 樹型結(jié)構(gòu)的邏輯特征可用樹中結(jié)點(diǎn)之間的父子關(guān)系來描述：樹中任一結(jié)點(diǎn)都可以有零個(gè)或多個(gè)直接后繼（即孩子）結(jié)點(diǎn)，但至多只能由一個(gè)直接前趨（即雙親）結(jié)點(diǎn)。定義：二叉樹（Binary Tree）n（n0）n=0不相交的、分別稱作這個(gè)根的左的二叉樹組6.4 6.6中的普通樹（作為6.2.2 二叉i層上的結(jié)點(diǎn)數(shù)目最多6.2.2 二叉i層上的結(jié)點(diǎn)數(shù)目最多為 2i-1（i1。 j 層上至多有 2j-1 個(gè)結(jié)點(diǎn)，證明j=1 時(shí)命題亦成立。 i 結(jié)點(diǎn)數(shù)，至多是第i-12倍，即j=i性質(zhì) 21證明 在具有相同深度的二叉樹中，僅當(dāng)每一層都含有度為k，滿二叉樹(FullBinary T

4、ree) k2k-1個(gè)圖 6.7(a)是一個(gè)深度為 4 的滿二叉樹。滿二叉樹的特點(diǎn) 完全二叉樹(Complete Binary 圖 6.7（b）是一棵完全二叉樹。顯然滿二叉樹是完全6.7（c）FL，故它性質(zhì)性質(zhì)Kn2k-1-1。另一方面，由性質(zhì) 2 知道n2k-1,即:因?yàn)镵-1和KK-1=lgnn 假設(shè)為i/2i=1ki 是根(1i1k 假設(shè)為i/2i=1ki 是根(1i1ki 的雙(22inki 的左孩子2i，否則，ki 無左子，即 ki 必定是葉子，因此完全二叉數(shù)(32i+1nki i 為奇數(shù)且不為1ki 的左兄弟i 為偶數(shù)且小nki 的右兄弟的則，ki無右兄弟。i-1；i+1；6.1

5、結(jié)的雙親、左右孩子分別是bt3、bt14bt15空 A、B和C lchild空 A、B和C lchild rchildTypedef char ype；/ ype 的實(shí)際B上一個(gè)指向開始結(jié)點(diǎn)（即根結(jié)點(diǎn)）的ree 型指針（即B上一個(gè)指向開始結(jié)點(diǎn)（即根結(jié)點(diǎn)）的ree 型指針（即的指針為空，具有一n 個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，子，其余的n+1 個(gè)指針而空。parent，形成一個(gè)帶雙親指針的二叉鏈表。圖 6.10(c)是圖 6.10(a)所示的二叉樹的帶雙親指針的二叉鏈63 （N（L（只LRN 結(jié)點(diǎn)的次序不同，NLR、N（N（L（只LRN 結(jié)點(diǎn)的次序不同，NLR、N、L和R。因此，又NLR、LN

6、R LRN 分別和根的；。將操作(1)和(2)次序?qū)φ{(diào)即為先序遍歷，而將(2)和(3)voidInorder reeichildichildichild/叉樹（樹中為虛結(jié)點(diǎn)）6.12 所示，圖中“&BA、 DBAEC 的 分別為 ABDCEF 和 DBEFCA。三種遍歷算法基本上相同。這說明三種遍歷的搜索路線相 后序后繼結(jié)點(diǎn)是 A。但是就該樹的邏輯結(jié)構(gòu)而言，C 的前趨結(jié)點(diǎn)是 A，后繼結(jié)點(diǎn)是 E F。voidree /構(gòu)造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實(shí)參（根指針）chari（cgecvoidree /構(gòu)造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實(shí)參（根指針）cha

7、ri（cgecr *T=NULL;/讀入空格，將相應(yīng)指針Node)；/生成點(diǎn)； ree則調(diào)用ree（&root）root直接找到該結(jié)點(diǎn)在某種遍歷序列中的前趨和后繼結(jié)點(diǎn)。為叉鏈表稱為線索鏈表， 相應(yīng)的二叉樹稱為線索二叉樹其中左標(biāo)志ltag=0：lchild左標(biāo)志ltag=1叉鏈表稱為線索鏈表， 相應(yīng)的二叉樹稱為線索二叉樹其中左標(biāo)志ltag=0：lchild左標(biāo)志ltag=1：lchild是指向結(jié)點(diǎn)的前趨的左線索。右標(biāo)志 rtag=0：rchild 是指向結(jié)點(diǎn)的右孩子的指針；右標(biāo)志 rtag=1：rchild 是指向結(jié)點(diǎn)的后繼的右線索。6.13(b)c結(jié)點(diǎn)EE將二叉樹變?yōu)榫€索二叉樹的過程稱為線索化

8、。按某種次 過的結(jié)點(diǎn)，而指針p 剛結(jié)點(diǎn)*pre 是結(jié)點(diǎn)*p 的前趨，而*p 是*pre 結(jié)點(diǎn)*p 的操作具體化為在及其中序前趨*pre（若 preNULL）之間建立線索。顯然 /枚舉值Link和Threadype StructnodehrNodeBhrNode*pre=void/將二叉樹pype StructnodehrNodeBhrNode*pre=void/將二叉樹p左線索/以下直線索化之前相當(dāng)于遍歷結(jié)點(diǎn)的操p-ltag=(p-lchild)?/左指針非空時(shí)左標(biāo)志為 Link(即0)，否則為Thread（即1） p-rtag=( p- rchild)? Link:Thread； if(pr

9、e) /若*p 的前趨*pre 存在if(pre-rtag=Thread) pre-rchild=p *p 的前趨右標(biāo)志為/ 令*pre/ *p 的左標(biāo)志為線/ 令*ppre=p；/pre 是下結(jié)點(diǎn)的中序前InorderThreeding(p-rchild)；/，因此對(duì)于n 來 （1）若*p 空（prtag Thread（1）若*p 空（prtag Thread613是Dlink，則 到一個(gè)沒有左孩子的結(jié)點(diǎn)為止。該結(jié)點(diǎn)是*p 中13 所示，*p 的中序后繼結(jié)點(diǎn)是 Rk(k1).Rk 可能有右孩子也可能無右孩子，若 Rk 無右孩子，則它必定是葉結(jié)點(diǎn)。13 中，A 的中序后繼是 F，它有右孩子；F

10、 的中序后繼是 D 相當(dāng)于是 。BhrNode*p /在中序線索樹中找結(jié)點(diǎn)*p 的中序后繼，Bif(p-/*p 的為BhrNode*p /在中序線索樹中找結(jié)點(diǎn)*p 的中序后繼，Bif(p-/*p 的為return p-rchild； /返回右線索所指的中序q=p-rchild；/從*p 的右孩子開-lchild; /q 非空時(shí)，沿左鏈為空時(shí)，它就是最左下return若*p 止。該結(jié)點(diǎn)是*p 左6.15 則*p 的中序前趨（或中序后繼）是從*p 的左孩子（）（或中序后繼；若結(jié)點(diǎn)*p （ 到*p 的中序前趨（或中序后繼 則*p 的中序前趨（或中序后繼）是從*p 的左孩子（）（或中序后繼；若結(jié)點(diǎn)*p

11、 （ 到*p 的中序前趨（或中序后繼 才能找到*p 的中序前趨（或中序后繼。由此可見，線索使在后序線索二叉樹中，查找指定結(jié)點(diǎn)*p (1若*p p- lchild 6.16中，H的后序前趨是FG(2若*p p-lchild 故*p 此，當(dāng)*p 非空時(shí)，*p (1若*p是根，則*p (1若*p是根，則*p 若*p 是其雙親的右孩子，則*p 的后序后繼結(jié)點(diǎn)就是其雙親結(jié)點(diǎn)，如圖 6。16 中，E 的后序后繼是 A。若*p是雙親的左孩子，但*p無右兄弟時(shí)，*p的后序繼結(jié)點(diǎn)是其雙親結(jié)點(diǎn)，如圖 6.16 中 F 的后序后繼是E。若*p是其雙親的左孩子，但*p有右兄弟，則*p個(gè)該 是雙親A中中可知，在后序線索

12、樹中，僅從*p 找到其后序前趨結(jié)點(diǎn)；而找*p 的后序后繼結(jié)點(diǎn)，僅當(dāng)*p 為空時(shí)，才能直接由*p 的右線索p- rchild 右 從根開始后序遍歷才能找到結(jié)點(diǎn)*p 的后序后繼。由此可看序線索二叉樹中，找某一點(diǎn)*p voidhrTree/遍歷中序線索二 voidhrTree/遍歷中序線索二if(p) /p=p-lchild; /從根往下找最左下結(jié)點(diǎn)，即中序序列的結(jié)sor(p); /找*p 的中序后（n 但因?yàn)樗欠沁f歸算法，所以在常數(shù)因子上小于遞歸樹和森在樹或森林與二叉樹之間有一個(gè)自然的一一對(duì)應(yīng)關(guān)1. 樹和森在樹或森林與二叉樹之間有一個(gè)自然的一一對(duì)應(yīng)關(guān)1. 是使用上述變換法，圖 6.17（a）所示

13、的樹就為圖（b）的的轉(zhuǎn)換結(jié)果，（c）（b）旋轉(zhuǎn)后的二叉樹。x 是其雙y 的左孩子，則x 的右孩子，右孩子的孩子的連線。圖 6.19（b）就是用這種方法將圖 6.18（c）的1. #defineMaxTreeSize/向量空間的大小，由1. #defineMaxTreeSize/向量空間的大小，由用戶/應(yīng)由用戶定typedef char typedefparent；/雙親指針，指示結(jié)點(diǎn)的雙親在向量中的typedefPtree6.17（aT.nodesi.parent=j,則 T.nodesi的雙親是 T.nodesj。例如，E1Bparent因?yàn)殡p親鏈表示法中其指針parent當(dāng)宜。若每個(gè)結(jié)點(diǎn)均

14、按樹的度k 來設(shè)置指針，則n 個(gè)結(jié)點(diǎn)的樹因?yàn)殡p親鏈表示法中其指針parent當(dāng)宜。若每個(gè)結(jié)點(diǎn)均按樹的度k 來設(shè)置指針，則n 個(gè)結(jié)點(diǎn)的樹/以下的和由用戶定義，以后這樣的說明不再給/孩子鏈表結(jié)/孩子結(jié)點(diǎn)在向量中對(duì)應(yīng)的typedefstructstructcnode* typedef/存放樹中結(jié)點(diǎn)typedefchild; /孩子鏈表的頭PTNode/n 根在向/T 為孩子鏈表表PTNode/n 根在向/T 為孩子鏈表表T.nodesi 點(diǎn)T.nodesi.data child6.21(a)child T.nodes7 、T.nodes8T.nodes96.17(a) 設(shè)樹T 6.23 所示，結(jié)點(diǎn)R

15、 是它的根，根的左到右依次為T1,T2,TK 。樹的兩種遍歷方法定義為：(1) 設(shè)樹T 6.23 所示，結(jié)點(diǎn)R 是它的根，根的左到右依次為T1,T2,TK 。樹的兩種遍歷方法定義為：(1) 從(2) T1,T2,TKABCDE和BDCEA（1）森所（2）森所（1）森所（2）森所。ABCDEFIGJH哈夫曼樹及其應(yīng)用最優(yōu)二叉樹（哈夫曼樹哈夫曼樹及其應(yīng)用最優(yōu)二叉樹（哈夫曼樹其中,n表示葉子結(jié)點(diǎn)的數(shù)目,wi和lj分別表示葉結(jié)點(diǎn)ki 的代價(jià)。w1 ,w2 ,，wn其中,n表示葉子結(jié)點(diǎn)的數(shù)目,wi和lj分別表示葉結(jié)點(diǎn)ki 的代價(jià)。w1 ,w2 ,，wn 的n 4a,b,c d（a） WP （c）(1)

16、根據(jù)給定的nw1w2nF=T1 ,T2 ,，Tn ，其中每棵二叉樹Ti wi(2在森林F中選出兩棵根結(jié)點(diǎn)的權(quán)值最小的樹（當(dāng)這樣 n n 中n個(gè)葉結(jié)點(diǎn)是初始森林中的n實(shí)際上所有具有n個(gè)葉子結(jié)點(diǎn)的嚴(yán)格二叉樹都恰有2n-1個(gè)結(jié)2n-1#definen/葉子數(shù)/樹中結(jié)點(diǎn)總/結(jié)點(diǎn)類/權(quán)#definen/葉子數(shù)/樹中結(jié)點(diǎn)總/結(jié)點(diǎn)類/權(quán)值，不妨設(shè)權(quán)值均大#definetypedefstructfloatlchild,rchild,parent; /HTNode Huffman Treem;/HuffmanTree 是向量類 樹中某結(jié)點(diǎn)的lchild、rchild和parent不等于-1時(shí)，它們分別(1) T

17、0.m-1kh 2n-1 個(gè)結(jié)點(diǎn)里的三個(gè)指針均置為空（即置為-0。讀入n個(gè)葉子的權(quán)值存于向量的前n個(gè)分量（-1）中，它們是初始森林中n Tp1Tp2parent置為iTilchild和rchildp1和p2，合并后Tp1和Tp2合并后Tp1和Tp2/T 初始/輸入葉子權(quán)值至T0.n-1的域for(i=n;im;i+)/共進(jìn)行n-1 次合并，新結(jié)點(diǎn)依次存于 Ti/在 T0.i-1中選擇兩個(gè)權(quán)最小的根結(jié)點(diǎn)，其序號(hào)分別為 p1 和 /最小權(quán)的根結(jié)點(diǎn)是新結(jié)點(diǎn)的左/最小權(quán)的根結(jié)點(diǎn)是新結(jié)點(diǎn)的右 最優(yōu)二叉樹的過程（見表 64。 T24 的結(jié)點(diǎn)已有了雙親，它們不再是根結(jié)點(diǎn)，故表中用方括號(hào) T24 的結(jié)點(diǎn)已有了雙親，它們不再是根結(jié)點(diǎn)，故表中用方括號(hào)6.455是當(dāng)前最小的兩個(gè)結(jié)在來節(jié)省數(shù)據(jù)文件的計(jì)算機(jī)空間和網(wǎng)絡(luò)的傳輸時(shí)間已愈數(shù)（簡(jiǎn)稱頻度）見表態(tài) 6.5，表中給出了兩種不同的編碼方3（通常碼300000 位。變長(zhǎng)編碼的特點(diǎn)是頻高的字符編 數(shù)（簡(jiǎn)稱頻度）見表態(tài) 6.5，表中給出了兩種不同的編碼方3（通常碼300000 位。變長(zhǎng)編碼的特點(diǎn)是頻高的字符編 E、T、ETWEW 字符集由nfi C=c1，c2，- ，cn，每個(gè)字得出每個(gè)字符ci的概率pi6.5afnfili或利用哈夫曼樹很容易求出給定字符集及其概率（或利用哈夫曼樹很容易求出給定字符集及其概率（或頻pi（fi）ci 的權(quán)，構(gòu)造一棵哈夫曼樹；