第6章樹(shù)與二叉樹(shù)-資料下載頁(yè)
2024-10-24 15:07本頁(yè)面
【導(dǎo)讀】樹(shù)形結(jié)構(gòu)是線(xiàn)性結(jié)構(gòu)的拓廣。接后繼元素的個(gè)數(shù)也可以有多個(gè)。樹(shù)是包含N(N>0)個(gè)節(jié)點(diǎn)的有窮集合D，R來(lái)說(shuō)沒(méi)有前驅(qū)，節(jié)點(diǎn)e0稱(chēng)作樹(shù)的根。,em)，其中e0就是樹(shù)根，樣的節(jié)點(diǎn)序列稱(chēng)為從根到節(jié)點(diǎn)e的一條路徑。交的有限集T1，T2，…，Tm，其中每個(gè)集。合本身又是一棵樹(shù)，稱(chēng)T1，T2，…體現(xiàn)樹(shù)形結(jié)構(gòu)中分支和層次的特性。若D為空集,則稱(chēng)為空樹(shù);它在關(guān)系H下無(wú)前驅(qū);Ф,存在D-{r}的一個(gè)劃分。素xi∈Di有<r,xi>∈H;,<r,xm>}有惟一的一個(gè)劃分。parent的第order個(gè)子節(jié)點(diǎn)，樹(shù)和右子樹(shù)構(gòu)成，同時(shí)這兩棵子樹(shù)亦是二叉樹(shù)。二叉樹(shù)可以有5種基本形態(tài)，只含根結(jié)點(diǎn)二叉樹(shù)右子樹(shù)為空的二叉樹(shù)左、右子樹(shù)非空空的二叉樹(shù)左子樹(shù)為空的二叉樹(shù)。性質(zhì)：在二叉樹(shù)的第i層上至多有2i-1. 的子孫的最大層次不小于k。二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。二叉樹(shù)的深度為?
【正文】 ，可使用剪枝函數(shù)把不需要的子樹(shù)剪去；使用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù) ,從而提高回溯法的搜索效率。 具體到 01背包問(wèn)題： 預(yù)處理 ：按 各物品單位重量所包含的價(jià)值從大到小進(jìn)行排列物品。 設(shè)計(jì)預(yù)估函數(shù)，其返回值說(shuō)明右子樹(shù)中是否存在一個(gè)比當(dāng)前解更優(yōu)的解決方案。以此作為剪枝的依據(jù)。 預(yù)估函數(shù)的作用： 能夠估計(jì)出最優(yōu)解的上界。 01背包問(wèn)題的回溯法效率分析： 預(yù)估函數(shù)需要 O(N)時(shí)間，其中 N為物品種類(lèi)的數(shù)量。在最壞情況下，有 O(2N)個(gè)右子節(jié)點(diǎn)都需要進(jìn)行預(yù)估，故求解 01背包問(wèn)題的回溯法時(shí)間復(fù)雜度為 O(N*2N)。 哈夫曼樹(shù)與貪心算法 ? 相關(guān)概念： 從樹(shù)中一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)節(jié)點(diǎn)之間的路徑； 路徑上的分支數(shù)目稱(chēng)作路徑長(zhǎng)度。 考慮節(jié)點(diǎn)帶權(quán)的樹(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)度之和，記作： )0,1(N1NklwW P L kNkk ????? ??11 4 2311 4232 3114(a)WPL=(11+4+3+2)*2=40 (b)WPL=(11+4)*3+3*2+2*1=53 (c)WPL=(2+3)*3+4*2+11*1=34 3 具有不同帶權(quán)路徑長(zhǎng)度的二叉樹(shù) 試構(gòu)造一棵有 N個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，則其中帶權(quán)路徑長(zhǎng)度 WPL最小的二叉樹(shù)稱(chēng)作最優(yōu)二叉樹(shù)或哈夫曼（ Huffman）樹(shù)。 構(gòu)造哈夫曼樹(shù)思想： (1)根據(jù)給定的 N個(gè)權(quán)值 {w1,w2,…,wN}構(gòu)成 N棵二叉樹(shù)的集合 F ={T1,T2,…,TN}，其中每棵二叉樹(shù) Ti中只有一個(gè)帶權(quán)為 wi的根節(jié)點(diǎn)，其左右子樹(shù)均空； (2)在 F中選取兩棵根節(jié)點(diǎn)權(quán)值最小的子樹(shù) ， 分別做為左右子樹(shù)來(lái)構(gòu)造一棵新的二叉樹(shù) ， 且置新的二叉樹(shù)的根節(jié)點(diǎn)的權(quán)值為其左右子樹(shù)上根節(jié)點(diǎn)的權(quán)值之和； (3)在 F中刪除這兩棵樹(shù) ， 同時(shí)將新得到的二叉樹(shù)加入 F中； (4)重復(fù) (2)、 (3)，直到 F僅含一棵樹(shù)為止。 －－－－貪心算法 C DABA B DCC DA BC DBA11 4 3 23 211 41143 243 2115959520C DAB( a ) 初始集合含4 棵樹(shù) ( b ) 集合含3 棵樹(shù) ( c ) 集合含2 棵樹(shù) ( d ) 集合中只含1 棵樹(shù) ( e ) 哈夫曼樹(shù)的前綴編碼111 000A:0B:10C:110D:111圖6 . 1 4 哈夫曼樹(shù)的構(gòu)造過(guò)程及哈夫曼編碼 貪心算法并不從整體最優(yōu)的角度來(lái)考慮問(wèn)題。它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。 ?哈夫曼樹(shù)應(yīng)用： 哈夫曼編碼 －－電文的 二進(jìn)制前綴編碼 本章小結(jié) ? 基本內(nèi)容： 1. 樹(shù)的 基本概念 2. 二叉樹(shù) 的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的遍歷和線(xiàn)索化以及 遍歷算法 的各種描述形式； 3. 樹(shù)和森林 與二叉樹(shù)的轉(zhuǎn)換、樹(shù)和森林的遍歷； 典型應(yīng)用 ； 回溯法 與 貪心算法 。 ? 基本要求： 熟練掌握二叉樹(shù)的 結(jié)構(gòu)特性 ， 了解相應(yīng)的 證明方法 。 熟悉二叉樹(shù)的各種 存儲(chǔ)結(jié)構(gòu) 的特點(diǎn)及適用范圍 。 熟練掌握各種 遍歷策略 的遞歸算法 ，了解遍歷過(guò)程中 “ 棧 ” 的作用和狀態(tài) ， 而且能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其他操作 。 層次遍歷 是按另一種搜索策略進(jìn)行的遍歷 。 熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn) ， 掌握樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法 。 掌握各種建立二叉樹(shù)和樹(shù)的存儲(chǔ)結(jié)構(gòu)的方法 。 學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法 。 掌握建立哈夫曼編碼的方法 。 學(xué)習(xí)并使用貪心算法與回溯法的思想 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1