數(shù)據(jù)結(jié)構(gòu)C++ppt課件

1、125.1 定義及主要特性3基本形態(tài)空二叉樹A只有根結(jié)點(diǎn)的二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空4二叉樹的相關(guān)術(shù)語5二叉樹的相關(guān)術(shù)語6二叉樹的相關(guān)術(shù)語7二叉樹的相關(guān)術(shù)語8完全二叉樹12311458912136710141512345671231145891267101234569二叉樹性質(zhì)10二叉樹的性質(zhì)11二叉樹的性質(zhì)12二叉樹的性質(zhì)13二叉樹的性質(zhì)14二叉樹的抽象數(shù)據(jù)類型155.2 周游二叉樹16先序遍歷ADBCD L RAD L RD L RBDCD L R17中序遍歷ADBCL D RBL D RL D RADCL D R18后序遍歷ADBC L R DL R DL

2、R DADCL R DB19舉例-+/a*b-efcd中序遍歷：后序遍歷：層次遍歷：-+a*b-cd/ef-+a*b-cd/ef- +a *b - c d/e f-+a*b-cd/ef先序遍歷：20前序遍歷算法21遍歷算法應(yīng)用225.3 二叉樹的實(shí)現(xiàn)23二叉樹的存儲24二叉樹存儲（區(qū)別葉和分支）25表達(dá)式樹：聯(lián)合實(shí)現(xiàn)方法26用不同的類實(shí)現(xiàn)分支和葉27不同類實(shí)現(xiàn)的分支結(jié)點(diǎn)285.3.2 結(jié)構(gòu)性空間開銷分析29結(jié)構(gòu)性空間開銷分析(2 )2(2 )2nppnpdpdn305.3.3 使用數(shù)組實(shí)現(xiàn)完全二叉樹31順序存儲32完全二叉樹的下標(biāo)對應(yīng)關(guān)系00000000000033完全二叉樹的下標(biāo)公式345.

3、4 二叉查找樹35BST圖示36檢索37二叉檢索樹類的定義38二叉檢索樹類的定義39檢索40插入41BST插入圖示42刪除43刪除子樹中最小值圖示44刪除右子樹中最小值結(jié)點(diǎn)45BST Remove（1）46BST Remove（2）475.5 堆與優(yōu)先隊(duì)列48最小值堆49最大值堆的實(shí)現(xiàn)50建堆圖示51堆的形成52Shiftdown操作53舉例4965382713769750496538271376509749133827657650974913382765765097132738496576509754Shiftdown55Remove Max Value56建堆操作的效率575.6 Huff

4、man編碼樹58數(shù)據(jù)壓縮和不等長編碼595.6.1 建立Huffman編碼樹10niiilw這個擴(kuò)充二叉樹的葉結(jié)點(diǎn)帶權(quán)外部路徑長度總和這個擴(kuò)充二叉樹的葉結(jié)點(diǎn)帶權(quán)外部路徑長度總和最?。ㄗ⒁獠还軆?nèi)部結(jié)點(diǎn)，也不用有序）。權(quán)越大的葉結(jié)點(diǎn)離根越近；如果某個葉的權(quán)最?。ㄗ⒁獠还軆?nèi)部結(jié)點(diǎn)，也不用有序）。權(quán)越大的葉結(jié)點(diǎn)離根越近；如果某個葉的權(quán)較小，可能就會離根較遠(yuǎn)。較小，可能就會離根較遠(yuǎn)。60建立Huffman樹的過程61Huffman建樹圖示62Huffman建樹圖示63Huffman建樹圖示64Huffman樹結(jié)點(diǎn)的實(shí)現(xiàn)65Huffman樹葉節(jié)點(diǎn)的實(shí)現(xiàn)66Huffman樹分支結(jié)點(diǎn)的實(shí)現(xiàn)67元素/頻率對的類

5、聲明68Huffman樹的類聲明69Huffman樹的類聲明70Huffman樹構(gòu)建函數(shù)/ Build a Huffman tree from list fltemplate HuffTree*buildHuff(SLListHuffTree*, HHCompare * fl) HuffTree *temp1, *temp2, *temp3; for (fl-setStart(); fl-leftLength()+fl-rightLength()1; fl-setStart() / While at least two items left fl-remove(temp1); / Pull first two trees fl-remove(temp2); / off the list temp3 = new HuffTree(temp1, temp2); fl-insert(temp3); / Put the new tree back on list delete temp1; / Must delete the remnants delete temp2; / of the trees we created return temp3;71編碼結(jié)果平均代碼長度是平均代碼長度是2