數(shù)據(jù)結(jié)構(gòu)CPPT5

1、25.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 r

2、 dadcl r db19舉例-+/a*b-efcd中序遍歷：后序遍歷：層次遍歷：-+a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e f先序遍歷：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完全二叉樹

3、的下標(biāo)公式345.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建堆操作的效率5

4、75.6 huffman編碼樹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é)最小（注意不管內(nèi)部結(jié)點(diǎn)，也不用有序）。權(quán)越大的葉結(jié)點(diǎn)離根越近；如果某個葉的權(quán)較小，可能就會離根較遠(yuǎn)。點(diǎn)離根越近；如果某個葉的權(quá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元素/頻率對的類聲明68huffman樹的類聲明69huffman樹的類聲明70huffman樹構(gòu)建函數(shù)71編碼結(jié)果平均代碼長度是平均代碼長度是2.565362.56536。725.6.2 hu