（2）

森林轉(zhuǎn)換為二叉樹(shù)ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法：·將各棵樹(shù)分別轉(zhuǎn)成二叉樹(shù)；·把每棵數(shù)根結(jié)點(diǎn)用線連起來(lái)；·以第一棵數(shù)根結(jié)點(diǎn)作為二叉樹(shù)根結(jié)點(diǎn)，按順時(shí)針?lè)较蛐D(zhuǎn)。1/4110/5/1將二叉樹(shù)轉(zhuǎn)換成樹(shù)加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)左孩子，則將p右孩子，右孩子右孩子，……沿分支找到全部右孩子，都與p雙親用線連起來(lái)抹線：抹掉原二叉樹(shù)中雙親與右孩子之間連線調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI2/4110/5/25.4樹(shù)和二叉樹(shù)遍歷樹(shù)遍歷遍歷——按一定規(guī)律走遍樹(shù)各個(gè)頂點(diǎn)，且使每一頂點(diǎn)僅被訪問(wèn)一次，即找一個(gè)完整而有規(guī)律走法，以得到樹(shù)中全部結(jié)點(diǎn)一個(gè)線性排列慣用方法先根（序）遍歷：先訪問(wèn)樹(shù)根結(jié)點(diǎn)，然后依次先根遍歷根每棵子樹(shù)后根（序）遍歷：先依次后根遍歷每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)按層次遍歷：先訪問(wèn)第一層上結(jié)點(diǎn)，然后依次遍歷第二層，……第n層結(jié)點(diǎn)3/4110/5/3ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO4/4110/5/4二叉樹(shù)遍歷方法先序遍歷：先訪問(wèn)根結(jié)點(diǎn),然后分別先序遍歷左子樹(shù)、右子樹(shù)中序遍歷：先中序遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最終中序遍歷右子樹(shù)后序遍歷：先后序遍歷左、右子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)按層次遍歷：從上到下、從左到右訪問(wèn)各結(jié)點(diǎn)DLRLDR、LRD、DLRRDL、RLD、DRL5/4110/5/5（2）給定先（后）序遍歷和中序遍歷，可唯一得到一棵二叉樹(shù)ADBCT1T2T3ABDCBDACDBCA6/4110/5/62.5.3哈夫曼樹(shù)及其應(yīng)用1、哈夫曼樹(shù)（最優(yōu)樹(shù)）

帶權(quán)路徑長(zhǎng)度最短樹(shù)結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度為從該結(jié)點(diǎn)到樹(shù)根之間路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)乘積。樹(shù)帶權(quán)路徑長(zhǎng)度為樹(shù)中葉子結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度之和。記作：其中：Wk為樹(shù)中每個(gè)葉子結(jié)點(diǎn)權(quán)；

Lk為每個(gè)葉子結(jié)點(diǎn)到根路徑長(zhǎng)度WPL最小二叉樹(shù)就稱作最優(yōu)二叉樹(shù)或哈夫曼樹(shù)。7/4110/5/7abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=351、哈夫曼樹(shù)（最優(yōu)樹(shù)）

公式：8/4110/5/8675cd(b)11b57cd(c)18a711cdb5624(d)abcd7524(a)2、哈夫曼樹(shù)結(jié)構(gòu)9/4110/5/9146833442200001111T;ACS例2：哈夫曼樹(shù)用于電文編碼要傳輸電文是{CAS；CAT；SAT；AT}要傳輸字符集是D={C，A，S，T，；}每個(gè)字符出現(xiàn)頻率是W={2，4，2，3，3}各字符編碼是T；ACS

000110110111上述電文編碼：1101011101110100001111100001100010/4110/5/10線索二叉樹(shù)定義：前驅(qū)與后繼：在二叉樹(shù)先序、中序或后序遍歷序列中兩個(gè)相鄰結(jié)點(diǎn)互稱為~線索：指向前驅(qū)或后繼結(jié)點(diǎn)指針?lè)Q為~線索二叉樹(shù)：加上線索二叉鏈表表示二叉樹(shù)叫~線索化：對(duì)二叉樹(shù)按某種遍歷次序使其變?yōu)榫€索二叉樹(shù)過(guò)程叫~實(shí)現(xiàn)在有n個(gè)結(jié)點(diǎn)二叉鏈表中必定有n+1個(gè)空鏈域在線索二叉樹(shù)結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域lt:若lt=0,lc域指向左孩子；若lt=1,lc域指向其前驅(qū)rt:若rt=0,rc域指向右孩子；若rt=1,rc域指向其后繼結(jié)點(diǎn)定義：typedefstructnode{intdata;intlt,rt;structnode*lc,*rc;}JD;lcltdatartrc11/4110/5/11ABCDEABDCET先序序列：ABCDE先序線索二叉樹(shù)00001111^1112/4110/5/12二叉排序樹(shù)定義：二叉排序樹(shù)或是一棵空樹(shù)，或是含有以下性質(zhì)二叉樹(shù)：若它左子樹(shù)不空，則左子樹(shù)上全部結(jié)點(diǎn)值均小于它根結(jié)點(diǎn)值若它右子樹(shù)不空，則右子樹(shù)上全部結(jié)點(diǎn)值均大于或等于它根結(jié)點(diǎn)值它左、右子樹(shù)也分別為二叉排序樹(shù)13/4110/5/13插入算法例{10，18，3，8，12，2，7，3}1010181018310183810183812101838122101838122710183812273中序遍歷二叉排序樹(shù)可得到一個(gè)關(guān)鍵字有序序列14/4110/5/142.6圖圖是一個(gè)非線性數(shù)據(jù)結(jié)構(gòu)，結(jié)點(diǎn)之間關(guān)系能夠是任意。圖中任意兩個(gè)元素之間都可能相關(guān)。圖存放結(jié)構(gòu)（1）圖鄰接矩陣表示法表示頂點(diǎn)間相鄰關(guān)系矩陣。有向：從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)有弧為1，不然為0。無(wú)向：有邊連接則為1，不然為0。（2）圖鄰接表表示法在邊少情況下，用鄰接表比鄰接矩陣節(jié)約存放空間。15/4110/5/15V1V3V2V4V1V3V2V4

V1V2V3V4

V1

0010

V20001

V30101

V41000

V1V2V3V4

V1

0111

V21011

V31100

V41100圖鄰接矩陣表示法無(wú)向圖中某頂點(diǎn)度數(shù)為矩陣中對(duì)應(yīng)該頂點(diǎn)行或列1個(gè)數(shù)有向圖中某頂點(diǎn)出度為矩陣中對(duì)應(yīng)該頂點(diǎn)行1個(gè)數(shù)有向圖中某頂點(diǎn)入度為矩陣中對(duì)應(yīng)該頂點(diǎn)列1個(gè)數(shù)16/4110/5/16V1V3V2V4V1V3V2V4432121∧113∧4∧4∧2∧1∧3∧44321圖鄰接表表示法∧417/4110/5/17V1V3V2V4∧2∧4∧343∧1∧1有向圖逆鄰接表表示法18/4110/5/18無(wú)向圖鄰接多重表表示法V1V3V2V44321221231241∧∧242∧∧19/4110/5/19深度優(yōu)先遍歷(DFS)V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7深度遍歷：V1V2V4V8V5V6V3V720/4110/5/20廣度優(yōu)先遍歷(BFS)V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8廣度遍歷：V1V2V3V4V5V6V7V821/4110/5/21結(jié)構(gòu)最小生成樹(shù)方法普里姆(Prim)算法算法思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹(shù)中邊集合從任一頂點(diǎn)出發(fā)，將此點(diǎn)包含在生成樹(shù)里在這些一個(gè)頂點(diǎn)已在生成樹(shù)里而另一頂點(diǎn)未在生成樹(shù)里邊中，找一條代價(jià)最小邊將此邊和那個(gè)頂點(diǎn)包含進(jìn)生成樹(shù)重復(fù)上述操作，每次加一個(gè)頂點(diǎn)和一個(gè)代價(jià)最小邊。直至全部頂點(diǎn)包含進(jìn)去，則得到最小生成樹(shù)拓?fù)渑判?一個(gè)AOV網(wǎng)拓?fù)湫蛄胁皇俏ㄒ?2/4110/5/2213<V0,V1>8<V0,V2>

30<V0,V4>

32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>

32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>終點(diǎn)從V0到各終點(diǎn)最短路徑及其長(zhǎng)度V1V2V3V4V5V6Vj--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>516432085623013717329最短路徑迪杰斯特拉(Dijkstra)算法23/4110/5/232.7查找2．7．1次序查找思想：對(duì)給定一關(guān)鍵字K，從線性表一端開(kāi)始，逐一進(jìn)行統(tǒng)計(jì)關(guān)鍵字和K比較，直到找到其關(guān)鍵字等于K統(tǒng)計(jì)或抵達(dá)表另一端。24/4110/5/24次序查找算法：intseqsrch(JDr[],intn,intk){inti=n;r[0].key=k;while(r[i].key!=k)i--;return(i);}2560308040201080012345672560308040201001234567256030804020109001234567（a）初態(tài)(b)K=80(c)K=90(returni=0)length=7(returni=4)25/4110/5/252．7．2折半查找思想：先確定待查找統(tǒng)計(jì)所在范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該統(tǒng)計(jì)為止。必須在含有次序存放結(jié)構(gòu)有序表中進(jìn)行。26/4110/5/26(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowmidhigh(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowmidhighmidlowhighmidmidlowhigh

折半查找例：highlow(08,14,23,37,46,55,68,79,91)midlowhigh27/4110/5/27IntSearch_Bin(SSTableST,KeyTypek){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(ST.elem[mid]==k)returnmid;elseif(k<ST.elem[mid])high=mid-1;//在前半?yún)^(qū)間繼續(xù)查找elselow=mid+1;}return0;}28/4110/5/282.7.3散列（HSAE）查找

依據(jù)關(guān)鍵字值，利用某個(gè)函數(shù)直接計(jì)算出元素所在位置。這函數(shù)稱為“哈希函數(shù)”，能用散列技術(shù)進(jìn)行查找表稱為散列表（哈希表）。1、

基本概念——哈希函數(shù)，沖突哈希表技術(shù)主要目標(biāo)是提升查找效率，即縮短查表和填表時(shí)間。沖突是指存在多個(gè)關(guān)鍵字，能計(jì)算出相同存放位置。312726211916130911050102H(K)=int(K/3)+1121110987654321表項(xiàng)序號(hào)29/4110/5/293、

處理沖突方法

（1）

開(kāi)放定址法

設(shè)散列函數(shù)H（k）=kMODm（m為表長(zhǎng),若發(fā)生沖突，設(shè)發(fā)生沖突地址為p

,則沿著一個(gè)探查序列逐一探查，那么，探查地址序列為P+1,P+2,P+3,…,m-1,0,1,…,P-1.

38291760012345678910m=11)(2)鏈地址法鏈地址法處理沖突方法：把含有相同散列地址鍵值存放在同一個(gè)鏈表中，稱為同義詞鏈表。30/4110/5/30例一組關(guān)鍵字為（21，14，19，58，65，32，72）

H(K)=KMOD11∧

∧

∧∧∧∧∧0123456789102165∧32∧19∧7214∧5831/4110/5/31排序重點(diǎn)是各種排序方法各趟排序結(jié)果以及比較次數(shù)和移動(dòng)次數(shù)32/4110/5/32待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

直接插入排序示例2.8.2插入排序直接插入、折半插入1、直接插入排序思想:從數(shù)組中第2號(hào)元素開(kāi)始,次序從數(shù)組中抽取元素并將該元素插入到其左端已排好序數(shù)組適當(dāng)位置上.33/4110/5/33例：有6個(gè)統(tǒng)計(jì)，前5個(gè)已排序基礎(chǔ)上，對(duì)第6個(gè)統(tǒng)計(jì)排序。[1527365369]42

low

mid

high[1527365369]42

low

high

mid[1527365369]42

high

low[152736425369]2、折半插入排序折半插入排序在尋找插入位置時(shí)，利用折半查找原理尋找插入位置,不是逐一比較。34/4110/5/34voidBinsertSort(Sqlist&L){for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//r[0]作為監(jiān)視哨low=1;high=i-1;

While(low<=high){m=(low+high)/2;if(L.r[0].key<L.r[m].key)high=m-1;//插入點(diǎn)在低半?yún)^(qū)elselow=m+1;}//whilefor(j=i-1;j>=high+1;

j)L.i[j+1]=L.r[j];//統(tǒng)計(jì)后移L.r[low]=L.r[0];//插入}for}//折半插入排序35/4110/5/35取d3=1三趟分組：1327485544938659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d1=5一趟分組：49

38

65

97

76

13

27

48

55

4取d2=3二趟分組：13

27

48

55

4

49

38

65

97

76希爾排序(縮小增量法)36/4110/5/362.8.3選擇排序

簡(jiǎn)單項(xiàng)選擇擇排序、堆排序。1、簡(jiǎn)單項(xiàng)選擇擇排序思想：首先從1-n個(gè)元素中選出關(guān)鍵字最小統(tǒng)計(jì)交換到第一個(gè)位置上。然后從第2個(gè)到第n個(gè)元素中選出次小統(tǒng)計(jì)交換到第2個(gè)位置上，依次類推。初態(tài)83916839168391683916ijkijkijkijk1

3986交換ijk1

3986ikj1

3986ikj第一趟第二趟1

3986ikj第三趟37/4110/5/37

2

堆排序也是一個(gè)選擇排序。是含有特定條件次序存放完全二叉樹(shù)，其特定條件是：任何一個(gè)非葉子結(jié)點(diǎn)關(guān)鍵字大于等于（或小于等于）兒女關(guān)鍵字值。

A、堆示例