數據結構C++ppt課件

1、125.1 定義及主要特性3基本形態(tài)空二叉樹A只有根結點的二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空4二叉樹的相關術語5二叉樹的相關術語6二叉樹的相關術語7二叉樹的相關術語8完全二叉樹12311458912136710141512345671231145891267101234569二叉樹性質10二叉樹的性質11二叉樹的性質12二叉樹的性質13二叉樹的性質14二叉樹的抽象數據類型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遍歷算法應用225.3 二叉樹的實現23二叉樹的存儲24二叉樹存儲（區(qū)別葉和分支）25表達式樹：聯合實現方法26用不同的類實現分支和葉27不同類實現的分支結點285.3.2 結構性空間開銷分析29結構性空間開銷分析(2 )2(2 )2nppnpdpdn305.3.3 使用數組實現完全二叉樹31順序存儲32完全二叉樹的下標對應關系00000000000033完全二叉樹的下標公式345.

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

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

5、聲明68Huffman樹的類聲明69Huffman樹的類聲明70Huffman樹構建函數/ 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編碼結果平均代碼長度是平均代碼長度是2