數(shù)據(jù)結(jié)構(gòu)導(dǎo)論第四章

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論第四章第一頁，共一百四十九頁，2022年，8月28日1第4章樹4.1樹的基本概念4.2二叉樹4.3二叉樹的存儲結(jié)構(gòu)4.4二叉樹的遍歷4.5遞歸消除4.6樹和林4.7判定樹和哈夫曼樹第二頁，共一百四十九頁，2022年，8月28日本章項目：電文編碼第三頁，共一百四十九頁，2022年，8月28日文字電文編碼電波譯碼摩爾斯電碼（又譯為摩斯電碼）是一種時通時斷的信號代碼，這種信號代碼通過不同的排列順序來表達不同的英文字母、數(shù)字和標(biāo)點符號等。它由美國人艾爾菲德·維爾發(fā)明（1835年）。第四頁，共一百四十九頁，2022年，8月28日網(wǎng)絡(luò)信息傳輸：文字數(shù)字編碼電信號電文編碼發(fā)送者數(shù)字編碼文字電文編碼接收者你好0101010101你好核心問題：電文如何編碼稱為01串？？第五頁，共一百四十九頁，2022年，8月28日本章項目：電文編碼問題涉及知識點：1、樹的概念2、樹的專業(yè)術(shù)語3、二叉樹的概念4、哈夫曼樹和哈夫曼編碼核心問題：如何將電報文字轉(zhuǎn)換成可傳送編碼第六頁，共一百四十九頁，2022年，8月28日自然中的樹抽象的樹知識點1：樹的概念第七頁，共一百四十九頁，2022年，8月28日旋轉(zhuǎn)后第八頁，共一百四十九頁，2022年，8月28日適當(dāng)進行調(diào)整ABCDEFGHI第九頁，共一百四十九頁，2022年，8月28日數(shù)據(jù)結(jié)構(gòu)中樹的形態(tài)，具有分層特點ABCDEFGHI第十頁，共一百四十九頁，2022年，8月28日某姓氏族譜第十一頁，共一百四十九頁，2022年，8月28日ABCDEFGHIJKLMNOPQRSTUVWXYZ……..對樹中的結(jié)點給定一個符號名稱，具有一對多的特點第十二頁，共一百四十九頁，2022年，8月28日樹描述的是一種層次結(jié)構(gòu)，是一種一對多的邏輯關(guān)系FGIJABCEDH第十三頁，共一百四十九頁，2022年，8月28日樹(Tree)是n(n>=0)個結(jié)點的有限集。n=0時稱為空樹。n>1時，有且僅有一個稱為根的結(jié)點；其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm,其中每個集合又是一棵樹，稱為子樹知識點1：樹的概念FGIJABCEDH根根第十四頁，共一百四十九頁，2022年，8月28日樹的其他表示形式ABCDEFHGM第十五頁，共一百四十九頁，2022年，8月28日結(jié)點：數(shù)據(jù)元素的內(nèi)容及其指向其子樹根的分支結(jié)點的度：結(jié)點擁有的子樹的數(shù)目。樹的度：樹內(nèi)各結(jié)點的度的最大值；知識點2：樹的專業(yè)術(shù)語ABCDEFHGMA、B、C、D、E、F、G、H、M均稱為結(jié)點A結(jié)點的度為2C結(jié)點的度為3M結(jié)點的度為0樹的度為3第十六頁，共一百四十九頁，2022年，8月28日葉子（終端結(jié)點），非終端結(jié)點：度為0的結(jié)點稱為葉子結(jié)點；度不為0的結(jié)點稱為非終端結(jié)點。ABCDEFHGM第十七頁，共一百四十九頁，2022年，8月28日結(jié)點的層數(shù)：樹中根結(jié)點的層次為1，根結(jié)點子樹的根為第2層，以此類推。樹的高度（深度）：樹中所有結(jié)點層次的最大值A(chǔ)BCDEFHGM第十八頁，共一百四十九頁，2022年，8月28日孩子，雙親，兄弟，堂兄：結(jié)點的子樹的根稱為該結(jié)點的孩子；該結(jié)點稱為孩子的雙親；同一個雙親的孩子之間互稱兄弟；雙親在同一層的結(jié)點互為堂兄弟。ABCDEFHGMA是B、C的雙親B、C是A的孩子B、C是兄弟關(guān)系E、F是堂兄弟關(guān)系第十九頁，共一百四十九頁，2022年，8月28日路徑：若樹中存在一個序列k1，k2…kn，使得ki是ki+1的雙親，則稱該結(jié)點序列為k1到kn的一條路徑。路徑長度：這些節(jié)點經(jīng)過的邊的條數(shù)ABCDEFHGM序列：ABDME序列：ABDM序列：ACF是路徑非路徑是路徑第二十頁，共一百四十九頁，2022年，8月28日子孫，祖先：以某結(jié)點為根的子樹中的所有結(jié)點都被稱為是該結(jié)點的子孫。從根結(jié)點到該結(jié)點路徑上的所有結(jié)點稱為該結(jié)點的祖先。ABCDEFHGM第二十一頁，共一百四十九頁，2022年，8月28日森林：多棵互不相交的樹的集合構(gòu)成森林ABCDEFHGM三棵樹構(gòu)成的森林第二十二頁，共一百四十九頁，2022年，8月28日結(jié)點結(jié)點的度(Degree)葉子（Leaf)或終端結(jié)點分支結(jié)點或非終端結(jié)點樹的度層次(Level)樹的深度(Depth)孩子（child)雙親（Parent)兄弟(Sibling)祖先子孫路徑ABCDEFHGM第二十三頁，共一百四十九頁，2022年，8月28日知識點3：二叉樹的概念二叉樹(BinaryTree)：或者是一棵空樹，或者是一棵由一個根結(jié)點和兩棵互不相交的左子樹和右子樹所組成的非空樹，左子樹和右子樹同樣也都是二叉樹ABCDEFHM第二十四頁，共一百四十九頁，2022年，8月28日特征：每個結(jié)點最多只有兩棵子樹子樹有左右之分，次序不能任意顛倒，只有一棵子樹時也必須分清是左子樹還是右子樹ABCACB第二十五頁，共一百四十九頁，2022年，8月28日網(wǎng)絡(luò)信息傳輸：文字數(shù)字編碼電信號電文編碼發(fā)送者數(shù)字編碼文字電文編碼接收者你好0101010101你好核心問題：電文如何編碼稱為01串？？第二十六頁，共一百四十九頁，2022年，8月28日項目實現(xiàn)的進一步分析：項目核心問題：如何將電報文字轉(zhuǎn)換成01編碼擴展問題：電文傳送時的高效性第二十七頁，共一百四十九頁，2022年，8月28日擴展問題：電文傳送時的高效性在計算機及通信中，常用二進制編碼來表示字符，假設(shè)某電文通信中只使用ABCD四個字符每個字母用兩位二進制數(shù)表示，例如傳輸100個字母需要用200個二進制位此種編碼方式為等長編碼，此時電文長度由電文字符數(shù)決定對于電文：DABC可翻譯為編碼：對于編碼：01001110可準(zhǔn)確翻譯為：00表示A01表示B10表示C11表示DBADC11000110第二十八頁，共一百四十九頁，2022年，8月28日實際情況：字符在實際使用中出現(xiàn)頻率不一樣！新問題1：如何讓電文編碼縮短為提高電文傳送效率，應(yīng)讓電文編碼盡量短考慮問題：出現(xiàn)頻率高的字符編碼位數(shù)少出現(xiàn)頻率低的字符編碼位數(shù)多以此降低電文總長度常用漢字6335個，最常用字560個，常用字807個，次常用字1033個，共2400個。這些字占了書刊物漢字出現(xiàn)次數(shù)的99%A8.19B1.47C3.83D3.91E12.25F2.26G1.71H4.57I7.10J0.14K0.41L3.77………

前面十位是：ETAOINRSDC第二十九頁，共一百四十九頁，2022年，8月28日假定：某電文通信中只由ABCD四個字符構(gòu)成且出現(xiàn)頻率分別為：000011001000考慮問題：出現(xiàn)頻率高的字符編碼位數(shù)少出現(xiàn)頻率低的字符編碼位數(shù)多以此降低電文總長度000表示A001表示B01表示C1表示DA5%B10%C15%D70%假定：問題：傳輸100個字母所用的二進制位為電文：ACDBA翻譯成編碼：編碼：000011001翻譯成電文:3×5+3×10+2×151×70+=145ACDB第三十頁，共一百四十九頁，2022年，8月28日此種編碼方式為不等長編碼，采用不等長編碼可縮短電文編碼長度，從而提高電文傳送效率假定：某電文通信中只由ABCD四個字符構(gòu)成且出現(xiàn)頻率分別為：考慮問題：出現(xiàn)頻率高的字符編碼位數(shù)少出現(xiàn)頻率低的字符編碼位數(shù)多以此降低電文總長度000表示A001表示B01表示C1表示DA5%B10%C15%D70%假定：第三十一頁，共一百四十九頁，2022年，8月28日假定：翻譯：CBDB翻譯：CBDCD新問題2：隨意的不等長編碼可能導(dǎo)致編碼翻譯時出現(xiàn)歧義編碼：000011001問題：編碼是任意給定的嗎？000表示A001表示B00表示C1表示D假定：某電文通信中只由ABCD四個字符構(gòu)成且出現(xiàn)頻率分別為：A5%B10%C15%D70%000011001000011001000011001錯誤！錯誤！第三十二頁，共一百四十九頁，2022年，8月28日新知識：設(shè)計不等長編碼時，必須做到：任何一個字符的編碼不能是另一個字符編碼的前綴，這種編碼為前綴碼新問題2：隨意的不等長編碼可能導(dǎo)致編碼翻譯時出現(xiàn)歧義000表示A001表示B01表示C1表示D我們設(shè)計的第一種編碼是前綴碼新問題3：如何設(shè)計前綴碼第三十三頁，共一百四十九頁，2022年，8月28日知識點4：哈夫曼樹與哈夫曼編碼樹的路徑長度：樹的根結(jié)點到樹中每一個結(jié)點的路徑長度之和。結(jié)點的帶權(quán)的路徑長度：該結(jié)點到根結(jié)點之間的路程長度與該結(jié)點上權(quán)的乘積路徑：若樹中存在一個序列k1，k2…kn，使得ki是ki+1的雙親，則稱該結(jié)點序列為k1到kn的一條路徑。路徑長度：這些節(jié)點經(jīng)過的邊的條數(shù)第三十四頁，共一百四十九頁，2022年，8月28日知識點4：哈夫曼樹與哈夫曼編碼樹的路徑長度：樹的根結(jié)點到樹中每一個結(jié)點的路徑長度之和。結(jié)點的帶權(quán)的路徑長度：該結(jié)點到根結(jié)點之間的路程長度與該結(jié)點上權(quán)的乘積樹的路徑長度：1+1+2+2+3+3結(jié)點a的帶權(quán)路徑長度：7*3dcab2475第三十五頁，共一百四十九頁，2022年，8月28日樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)的路徑長度的和。通常記為：WPL(WeightedPathLength)。樹的帶權(quán)路徑長度：4*2+7*3+5*3+2*1dcab2475第三十六頁，共一百四十九頁，2022年，8月28日樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)的路徑長度的和。通常記為：WPL(WeightedPathLength)。由n個帶權(quán)值的葉子結(jié)點構(gòu)成的二叉樹中，WPL最小的二叉樹稱為最優(yōu)二叉樹，或哈夫曼（Huffman）樹。WPL=4*2+7*3+5*3+2*1=46dcab2475第三十七頁，共一百四十九頁，2022年，8月28日abcd7524WPL=7*2+5*2+2*2+4*2=36abcd7524WPL=7*1+5*2+2*3+4*3=35WPL=7*1+4*3+2*3+5*2=35abdc7425第三十八頁，共一百四十九頁，2022年，8月28日1、根據(jù)給定的n個權(quán)值{w1,w2,…,wn}，構(gòu)造n棵只有根結(jié)點的二叉樹，令其權(quán)值為wj;2、在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和;3、從森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中;4、重復(fù)上述兩步，直到森林中只含一棵樹為止，這棵樹即哈夫曼樹。哈夫曼樹的構(gòu)造方法第三十九頁，共一百四十九頁，2022年，8月28日9例如:已知權(quán)值W={5,6,2,9,7}構(gòu)造以權(quán)值為葉子的哈夫曼樹5627第一步：把每個權(quán)值看作只有一個結(jié)點的樹第四十頁，共一百四十九頁，2022年，8月28日9例如:已知權(quán)值W={5,6,2,9,7}構(gòu)造以權(quán)值為葉子的哈夫曼樹5267第二步：取權(quán)值最小的兩棵樹，合并成，新樹的權(quán)值為兩棵子樹權(quán)值之和7第四十一頁，共一百四十九頁，2022年，8月28日9例如:已知權(quán)值W={5,6,2,9,7}構(gòu)造以權(quán)值為葉子的哈夫曼樹5267第三步：從森林中去掉被合并的結(jié)點，并將新合并的樹加入到森林中，繼續(xù)執(zhí)行第二步，直到森林合并成為一棵樹7第四十二頁，共一百四十九頁，2022年，8月28日9例如:已知權(quán)值W={5,6,2,9,7}構(gòu)造以權(quán)值為葉子的哈夫曼樹5267713第三步：從森林中去掉被合并的結(jié)點，并將新合并的樹加入到森林中，繼續(xù)執(zhí)行第二步，直到森林合并成為一棵樹第四十三頁，共一百四十九頁，2022年，8月28日9例如:已知權(quán)值W={5,6,2,9,7}構(gòu)造以權(quán)值為葉子的哈夫曼樹526771316第三步：從森林中去掉被合并的結(jié)點，并將新合并的樹加入到森林中，繼續(xù)執(zhí)行第二步，直到森林合并成為一棵樹第四十四頁，共一百四十九頁，2022年，8月28日9例如:已知權(quán)值W={5,6,2,9,7}構(gòu)造以權(quán)值為葉子的哈夫曼樹526771316第三步：從森林中去掉被合并的結(jié)點，并將新合并的樹加入到森林中，繼續(xù)執(zhí)行第二步，直到森林合并成為一棵樹第四十五頁，共一百四十九頁，2022年，8月28日9例如:已知權(quán)值W={5,6,2,9,7}構(gòu)造以權(quán)值為葉子的哈夫曼樹52677131629第三步：從森林中去掉被合并的結(jié)點，并將新合并的樹加入到森林中，繼續(xù)執(zhí)行第二步，直到森林合并成為一棵樹構(gòu)造完成第四十六頁，共一百四十九頁，2022年，8月28日設(shè)計電文編碼時，隨意的不等長編碼可能導(dǎo)致編碼翻譯時出現(xiàn)歧義使用前綴碼，可解決不等長編碼出現(xiàn)的歧義利用哈夫曼樹可構(gòu)造前綴碼構(gòu)造方法：1，將字符集中的每個字符作為節(jié)點2，每個字符的出現(xiàn)頻率作為節(jié)點的權(quán)值3，構(gòu)造哈夫曼樹4，令哈夫曼樹中的左分支為0，右分支為1從根到葉子節(jié)點的01序列即為葉子節(jié)點的編碼第四十七頁，共一百四十九頁，2022年，8月28日假定：某電文通信中只由ABCD四個字符構(gòu)成且出現(xiàn)頻率分別為：A5%B10%C15%D70%0.050.10.150.7第四十八頁，共一百四十九頁，2022年，8月28日假定：某電文通信中只由ABCD四個字符構(gòu)成且出現(xiàn)頻率分別為：A5%B10%C15%D70%0.050.10.150.70.15第四十九頁，共一百四十九頁，2022年，8月28日假定：某電文通信中只由ABCD四個字符構(gòu)成且出現(xiàn)頻率分別為：A5%B10%C15%D70%0.050.10.150.70.150.3第五十頁，共一百四十九頁，2022年，8月28日假定：某電文通信中只由ABCD四個字符構(gòu)成且出現(xiàn)頻率分別為：A5%B10%C15%D70%0.050.10.150.70.150.31ABCD010101A的編碼：000B的編碼：001C的編碼：01D的編碼：1電文：DABC編碼：100000101每個字符的編碼都不是另一字符編碼的前綴第五十一頁，共一百四十九頁，2022年，8月28日項目完成，總結(jié)：1，樹的概念2，專業(yè)術(shù)語的定義3，二叉樹的概念4，哈夫曼樹和哈夫曼編碼下節(jié)內(nèi)容：1，二叉樹的性質(zhì)2，二叉樹基本操作3，二叉樹的應(yīng)用作業(yè)：P996.21第五十二頁，共一百四十九頁，2022年，8月28日n(n>0)個結(jié)點的樹的高度:最低是多少？最高是多少？答案：1，n練習(xí)ABD第五十三頁，共一百四十九頁，2022年，8月28日答案：√一棵樹應(yīng)滿足下列條件：（1）有且僅有一個結(jié)點沒有前驅(qū)（雙親）,稱該結(jié)點為樹根;（2）除根結(jié)點以外,其余每個結(jié)點有且僅有一個直接前驅(qū);（3）樹中每個結(jié)點可以有多個直接后繼(孩子結(jié)點)。判斷第五十四頁，共一百四十九頁，2022年，8月28日1、哈夫曼樹只有度為0和2的結(jié)點，無度為1的結(jié)點；2、n個葉子的哈夫曼樹的形態(tài)一般不唯一，但WPL是相同的；3、n個葉子的哈夫曼樹共有2n-1個結(jié)點。判斷答案：正確第五十五頁，共一百四十九頁，2022年，8月28日0.10.20.301練習(xí)：假設(shè)有字符集{A，B，C，D}其在電文中的使用頻率分別為{0.1，0.4，0.3，0.2}請給出該字符集中每個字符的哈夫曼編碼并將AABCDD電文翻譯為哈夫曼編碼0.30.6010.4101ADCB編碼：A100B0C11D101AABBCDD翻譯：第五十六頁，共一百四十九頁，2022年，8月28日2009年10月考題：第五十七頁，共一百四十九頁，2022年，8月28日4.2二叉樹二叉樹(BinaryTree)：或者是一棵空樹，或者是一棵由一個根結(jié)點和兩棵互不相交的左子樹和右子樹所組成的非空樹，左子樹和右子樹同樣也都是二叉樹123456789101112131415第五十八頁，共一百四十九頁，2022年，8月28日特征：每個結(jié)點最多只有兩棵子樹子樹有左右之分，其次序不能任意顛倒，只有一棵子樹時也必須分清是左、右子樹。ACBABC第五十九頁，共一百四十九頁，2022年，8月28日二叉樹的五種形態(tài)(a)(b)(c)(d)(e)第六十頁，共一百四十九頁，2022年，8月28日（1）初始化INITIATE(BT)（2）求根ROOT(BT)（3）求雙親PARENT(BT,x)（4）求左孩子、右孩子Child(BT,x),RChild(BT,x)（5）建樹CREAT(x,LBT,RBT)（6）剪枝DELLEFT(BT,x)和DELRIGHT(BT,x)二叉樹的基本運算第六十一頁，共一百四十九頁，2022年，8月28日1.一個非空二叉樹的第i層上至多有2i-1個結(jié)點（i1）證明：i=1,只有根結(jié)點，顯然成立 設(shè)i=k時成立，最多有2k-1個結(jié)點 當(dāng)i=k+1時，最多的結(jié)點個數(shù)：

2k-1*2=2k-1+1=2k=2(

k+1)-1二叉樹的性質(zhì)123456789101112131415第六十二頁，共一百四十九頁，2022年，8月28日2.深度為k的二叉樹至多有2k-1個結(jié)點(k1)

證明：二叉樹的結(jié)點個數(shù)為： 1+2+…+2k-1=2k-1123456789101112131415第六十三頁，共一百四十九頁，2022年，8月28日3.對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。證明：設(shè)n1為T中度為1的結(jié)點數(shù)，則總結(jié)點數(shù)： n=n0+n1+n2(1)另：根據(jù)各個結(jié)點的前驅(qū)和后繼情況分支條數(shù)=n-1分支條數(shù)=n1+2*n2(2)由(1)和(2)有：n1+2*n2=n0+n1+n2-1故n0=n2+1;第六十四頁，共一百四十九頁，2022年，8月28日考慮到有序性，任一結(jié)點在樹中都有確切的位置，因此可以對滿二叉樹進行編號。編號方式為：從上到下，從左到右。滿二叉樹深度為k且有2k-1個結(jié)點的二叉樹123456789101112131415第六十五頁，共一百四十九頁，2022年，8月28日完全二叉樹深度為k，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹編號從1到n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。abcdefghij第六十六頁，共一百四十九頁，2022年，8月28日1.滿二叉樹一定是一棵完全二叉樹，反之完全二叉樹不一定是一棵滿二叉樹。(√)2.滿二叉樹的葉子結(jié)點全部在最底層，而完全二叉樹的葉子結(jié)點可以分布在最下面兩層。

(√)判斷題第六十七頁，共一百四十九頁，2022年，8月28日4.具有n個結(jié)點的完全二叉樹的深度:k=log2(n)+1證明：假設(shè)n個結(jié)點的完全二叉樹的深度為k，則n的值應(yīng)大于深度為k-1的滿二叉樹的結(jié)點數(shù)2k-1-1，小于等于深度為k的滿二叉樹的結(jié)點數(shù)2k-1，即

2k-1-1<n≤2k-1

進一步可推導(dǎo)出

2k-1≤n<2k兩邊取對數(shù)后，有

k-1≤log2(n)<k進一步可推導(dǎo)出

log2(n)<k≤log2(n)+1因為k是整數(shù)，所以有k＝log2(n)+1

第六十八頁，共一百四十九頁，2022年，8月28日（a）如果i=1,此結(jié)點為根結(jié)點，無雙親；若i>1,則其雙親結(jié)點是i/2。（b）如果2i>n,則結(jié)點i無左孩子，i為葉子結(jié)點,否則其左孩子是結(jié)點2i。（c）如果2i+1>n，則結(jié)點i無右孩子，否則其右孩子是結(jié)點2i+1。5.如果將一棵有n個結(jié)點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點編號1,2,3,…,n,則對任一結(jié)點i（1in）有abcdefghij第六十九頁，共一百四十九頁，2022年，8月28日1.一棵樹高為K的完全二叉樹至少有（）個結(jié)點A.2k–1B.2k-1–1C.2k-1

D.2k習(xí)題答案：C第七十頁，共一百四十九頁，2022年，8月28日2.已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有______個葉子結(jié)點。習(xí)題結(jié)點總個數(shù)n=2+3+4+x前驅(qū)后繼n-1=2*1+3*2+4*3故x=12答案：12第七十一頁，共一百四十九頁，2022年，8月28日習(xí)題3.有關(guān)二叉樹下列說法正確的是（）A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結(jié)點的度為2D．二叉樹中任何一個結(jié)點的度都為2答案：B第七十二頁，共一百四十九頁，2022年，8月28日4.3二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)第七十三頁，共一百四十九頁，2022年，8月28日二叉樹的順序存儲結(jié)構(gòu)整個二叉樹可以按照從上到下，從左到右的順序編號；abcdefghij第七十四頁，共一百四十九頁，2022年，8月28日1．順序存貯結(jié)構(gòu)將一棵二叉樹按完全二叉樹順序存放到一維數(shù)組中abcdefghm123456789101112131415

0123456789101112131415abcdefghm第七十五頁，共一百四十九頁，2022年，8月28日順序存儲結(jié)構(gòu)舉例ABCABC????A?B???C第七十六頁，共一百四十九頁，2022年，8月28日對于一棵二叉樹,若采用順序存貯時,當(dāng)它為完全二叉樹時,比較方便;若為非完全二叉樹,將會浪費大量存貯單元。因此，對于非完全二叉樹，宜采用下面的鏈?zhǔn)酱鎯Y(jié)構(gòu)。第七十七頁，共一百四十九頁，2022年，8月28日2.鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉鏈表三叉鏈表第七十八頁，共一百四十九頁，2022年，8月28日二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉鏈表lchilddatarchilddatalchildrchild第七十九頁，共一百四十九頁，2022年，8月28日ABDCEFADEBCFroot第八十頁，共一百四十九頁，2022年，8月28日二叉鏈表的定義structbtnode{//結(jié)點結(jié)構(gòu)datatypedata;structbtnode*lchild,*rchild;}typedefstructbtnode*bitreptr；bitreptr*root;結(jié)點結(jié)構(gòu):lchilddatarchild第八十一頁，共一百四十九頁，2022年，8月28日ADEBCFroot問題：如何找到某結(jié)點的子樹？如何找到某結(jié)點的雙親？第八十二頁，共一百四十九頁，2022年，8月28日三叉鏈表lchilddatarchildparentADEBCFroot第八十三頁，共一百四十九頁，2022年，8月28日三叉鏈表的定義structbtnode{//結(jié)點結(jié)構(gòu)datatypedata;structbtnode*lchild,*rchild}typedefstructbtnode*bitreptr；bitreptr*root;結(jié)點結(jié)構(gòu):lchilddatarchildparent,*parent;;第八十四頁，共一百四十九頁，2022年，8月28日鏈?zhǔn)酱鎯Φ娜秉c；

若一棵二叉樹有n個結(jié)點,采用二叉鏈表作存貯結(jié)構(gòu)時,共有2n個指針域,其中只有n-1個指針指向左右孩子,其余n+1個指針為空,沒有發(fā)揮作用。第八十五頁，共一百四十九頁，2022年，8月28日4.4二叉樹的遍歷遍歷一棵二叉樹是按某種次序系統(tǒng)地“訪問”二叉樹上的所有結(jié)點，使每個結(jié)點恰好被“訪問”一次。先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法“訪問”的含義可以很廣，如：輸出結(jié)點的信息等第八十六頁，共一百四十九頁，2022年，8月28日若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：AECBGL第八十七頁，共一百四十九頁，2022年，8月28日若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。中（根）序的遍歷算法：AECBGL第八十八頁，共一百四十九頁，2022年，8月28日若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。后（根）序的遍歷算法：AECBGL第八十九頁，共一百四十九頁，2022年，8月28日先（根）序的遍歷算法：voidPreorder(bitreptrr){//先序遍歷二叉樹

if(r！=NULL){visit(r);Preorder(r->lchild);Preorder(r->rchild);

}}AECBGL第九十頁，共一百四十九頁，2022年，8月28日中（根）序的遍歷算法：voidInorder(bitreptrr){//中序遍歷二叉樹

if(r！=NULL){Inorder(r->lchild);visit(r);Inorder(r->rchild);

}}AECBGL第九十一頁，共一百四十九頁，2022年，8月28日后（根）序的遍歷算法：voidPostorder(bitreptrr){//后序遍歷二叉樹

if(r！=NULL){Postorder(r->lchild);Postorder(r->rchild);visit(r);

}}AECBGL第九十二頁，共一百四十九頁，2022年，8月28日二叉樹的遍歷算法：AECBGLDLRLDR、LRD、DLR第九十三頁，共一百四十九頁，2022年，8月28日遍歷舉例ABCDEF前序序列：abcdef中序序列：cbefda后序序列：cfedba第九十四頁，共一百四十九頁，2022年，8月28日習(xí)題

1.給定二叉樹如下圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。若遍歷后的結(jié)點序列為3,1,7,5,6,2,4，則其遍歷方式是LRNB.NRLC.RLND.RNL答案：D第九十五頁，共一百四十九頁，2022年，8月28日習(xí)題

2.假設(shè)前序序列為ABDGHCEFI，中序序列為GDHBAECIF，請確定一棵二叉樹ABDGHCEFIGDHBAECIF前序中序第九十六頁，共一百四十九頁，2022年，8月28日習(xí)題

8.試找出滿足下列條件的二叉樹1）先序序列與中序序列相同2）中序序列與后序序列相同3）先序序列與后序序列相同答案1）不含左子樹的二叉樹2）不含右子樹的二叉樹3）空二叉樹或只含根結(jié)點的二叉樹第九十七頁，共一百四十九頁，2022年，8月28日習(xí)題

4.某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是()的二叉樹

A．空或只有一個結(jié)點B.高度等于其結(jié)點數(shù)C．任一結(jié)點無左孩子D.任一結(jié)點無右孩子先序：根左右后序：左右根答案：B第九十八頁，共一百四十九頁，2022年，8月28日4.6樹和林考慮存儲結(jié)構(gòu)時，主要考慮邏輯結(jié)構(gòu)：數(shù)據(jù)元素數(shù)據(jù)元素之間的關(guān)系第九十九頁，共一百四十九頁，2022年，8月28日樹的存儲結(jié)構(gòu)ABECDF雙親表示法

孩子鏈表表示法

孩子兄弟鏈表表示法

第一百頁，共一百四十九頁，2022年，8月28日孩子鏈表表示法順序存儲結(jié)點+鏈?zhǔn)酱鎯⒆咏Y(jié)構(gòu)；找孩子容易，找雙親難；01234567第一百零一頁，共一百四十九頁，2022年，8月28日孩子兄弟鏈表表示法兩個指針：左孩子指針，右孩子指針第一百零二頁，共一百四十九頁，2022年，8月28日雙親表示法樹的雙親表示法主要描述的是結(jié)點的雙親關(guān)系順序表示，存放頂點和雙親信息第一百零三頁，共一百四十九頁，2022年，8月28日請畫出該樹的孩子鏈表結(jié)構(gòu)圖請畫出該樹的孩子兄弟鏈表結(jié)構(gòu)圖雙親表示法結(jié)構(gòu)圖第一百零四頁，共一百四十九頁，2022年，8月28日樹的遍歷前序遍歷樹若樹非空，則：（1）訪問樹的根結(jié)點；（2）依次前序遍歷樹的第一棵子樹、第二棵子樹，……第一百零五頁，共一百四十九頁，2022年，8月28日樹的遍歷后序遍歷樹若樹非空，則：（1）依次后序遍歷樹的第一棵子樹、第二棵子樹，……（2）訪問樹的根結(jié)點；第一百零六頁，共一百四十九頁，2022年，8月28日樹的遍歷層次遍歷樹1）訪問樹的根結(jié)點；2）依次前序遍歷樹的第一層結(jié)點、第二結(jié)點，……第一百零七頁，共一百四十九頁，2022年，8月28日ABCED前序遍歷序列：后序遍歷序列：層次遍歷序列：ABCDEBCEDAABCDE第一百零八頁，共一百四十九頁，2022年，8月28日森林是由若干棵樹組成，可以將森林中的每棵樹的根結(jié)點看作是兄弟樹、森林與二叉樹的關(guān)系樹與二叉樹的相互轉(zhuǎn)換森林與二叉樹的相互轉(zhuǎn)換第一百零九頁，共一百四十九頁，2022年，8月28日

1.樹與二叉樹的相互轉(zhuǎn)換樹轉(zhuǎn)換成的二叉樹其右子樹一定為空第一百一十頁，共一百四十九頁，2022年，8月28日2.森林與二叉樹的相互轉(zhuǎn)換第一百一十一頁，共一百四十九頁，2022年，8月28日森林轉(zhuǎn)換為二叉樹第一百一十二頁，共一百四十九頁，2022年，8月28日森林轉(zhuǎn)換為二叉樹第一百一十三頁，共一百四十九頁，2022年，8月28日習(xí)題將二叉樹轉(zhuǎn)換成樹ABCDEFGHIJKLABCDEFGHIJKLCDABCDEFGHIJKLC第一百一十四頁，共一百四十九頁，2022年，8月28日DEFGHIJLABCKFILCABEGHJKD習(xí)題二叉樹到森林的轉(zhuǎn)換第一百一十五頁，共一百四十九頁，2022年，8月28日習(xí)題設(shè)X是樹T中的一個非根結(jié)點，B是T所對應(yīng)的二叉樹。在B中，X是其雙親的右孩子，下列結(jié)論正確的是()。A.在樹T中，X是其雙親的第一個孩子B.在樹T中，X一定無右邊兄弟C.在樹T中，X一定是葉子結(jié)點D.在樹T中，X一定有左邊兄弟答案：D第一百一十六頁，共一百四十九頁，2022年，8月28日4.7判定樹和哈夫曼樹分類與判定樹哈夫曼樹與哈夫曼算法第一百一十七頁，共一百四十九頁，2022年，8月28日分類與判定樹問題：編寫程序?qū)崿F(xiàn)將百分制成績轉(zhuǎn)換為五級制成績假設(shè)成績已存入score變量中，轉(zhuǎn)換后等級存入grade變量if(score<60

)grade=“bad”;elseif(score<70)grade=“pass”;elseif(score<80

)grade=“general”;elseif(score<90)grade=“good”;elseif(score<=100)grade=“excellent”;elsegrade=“error”；第一百一十八頁，共一百四十九頁，2022年，8月28日程序已寫出，但是此種判定形式是否最好呢？從何角度考慮程序是否最優(yōu)？問題：編寫程序?qū)崿F(xiàn)將百分制成績轉(zhuǎn)換為五級制成績if(score<60

)grade=“bad”;elseif(score<70)grade=“pass”;elseif(score<80

)grade=“general”;elseif(score<90)grade=“good”;elseif(score<=100)grade=“excellent”;elsegrade=“error”；第一百一十九頁，共一百四十九頁，2022年，8月28日問題：編寫程序?qū)崿F(xiàn)將百分制成績轉(zhuǎn)換為五級制成績if(score<60

)grade=“bad”;elseif(score<70)grade=“pass”;elseif(score<80

)grade=“general”;elseif(score<90)grade=“good”;elseif(score<=100)grade=“excellent”;elsegrade=“error”；現(xiàn)實中成績在五個等級上的分布是不均勻的?。〖僭O(shè)分布規(guī)律如下：分數(shù)0-5960-6970-7980-8990-100比例0.050.150.400.300.10第一百二十頁，共一百四十九頁，2022年，8月28日假設(shè)成績在五個等級上的分布規(guī)律如下：if(score<60

)grade=“bad”;elseif(score<70)grade=“pass”;elseif(score<80

)grade=“general”;elseif(score<90)grade=“good”;elseif(score<=100)grade=“excellent”;elsegrade=“error”；分數(shù)0-5960-6970-7980-8990-100比例0.050.150.400.300.10哪個判斷執(zhí)行次數(shù)較多？判定語句什么順序最好？第一百二十一頁，共一百四十九頁，2022年，8月28日假設(shè)成績在五個等級上的分布規(guī)律如下：分數(shù)0-5960-6970-7980-8990-100比例0.050.150.400.300.100.300.050.400.100.150.300.6010.15先判斷是否70-79之間再判斷是否80-89后判斷是否60-69再判斷…第一百二十二頁，共一百四十九頁，2022年，8月28日假設(shè)成績在五個等級上的分布規(guī)律如下：分數(shù)0-5960-6970-7980-8990-100比例0.050.150.400.300.10良不及格中優(yōu)及格60-6980-8970-79>60YNNYNYYN如何構(gòu)造出最佳的判定樹？第一百二十三頁，共一百四十九頁，2022年，8月28日概念樹的路徑長度：樹的根結(jié)點到樹中每一個結(jié)點的路徑長度的和。結(jié)點的帶權(quán)的路徑長度：該結(jié)點到根結(jié)點之間的路程長度與該結(jié)點上權(quán)的乘積樹的帶權(quán)的路徑長度：樹中所有葉子結(jié)點的帶權(quán)的路徑長度的和。通常記為：WPL(WeightedPathLength)。由n個帶權(quán)值的葉子結(jié)點構(gòu)成的二叉樹中，WPL最小的二叉樹稱為最優(yōu)二叉樹，或哈夫曼（Huffman）樹。第一百二十四頁，共一百四十九頁，2022年，8月28日有4個結(jié)點，權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35dcab2475第一百二十五頁，共一百四十九頁，2022年，8月28日由n個帶權(quán)值的葉子結(jié)點構(gòu)成的二叉樹中，WPL最小的二叉樹稱為最優(yōu)二叉樹，或哈夫曼（Huffman）樹。abcd7524哈夫曼樹的形態(tài)是不唯一第一百二十六頁，共一百四十九頁，2022年，8月28日根據(jù)給定的n個權(quán)值{w1,w2,…,wn}，構(gòu)造n棵只有根結(jié)點的二叉樹，令其權(quán)值為wj;在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和;在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中;重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹。構(gòu)造Huffman樹步驟第一百二十七頁，共一百四十九頁，2022年，8月28日9例如:已知權(quán)值W={5,6,2,9,7}5627第一百二十八頁，共一百四十九頁，2022年，8月28日957267例如:已知權(quán)值W={5,6,2,9,7}第一百二十九頁，共一百四十九頁，2022年，8月28日95726713例如:已知權(quán)值W={5,6,2,9,7}第一百三十頁，共一百四十九頁，2022年，8月28日9572671316例如:已知權(quán)值W={5,6,2,9,7}第一百三十一頁，共一百四十九頁，2022年，8月28日957267131629例如:已知權(quán)值W={5,6,2,9,7}第一百三十二頁，共一百四十九頁，2022年，8月28日957262971316根據(jù)權(quán)值構(gòu)造得到哈夫曼樹構(gòu)造哈夫曼樹的目的是什么呢？例如:已知權(quán)值W={5,6,2,9,7}第一百三十三頁，共一百四十九頁，2022年，8月28日假設(shè)成績在五個等級上的分布規(guī)律如下：分數(shù)0-5960-6970-7980-8990-100比例0.050.150.400.300.100.300.050.400.100.150.300.6010.15先判斷是否70-79之間再判斷是否80-89后判斷是否60-69再判斷…第一百三十四頁，共一百