第6章樹與二叉樹(參考版)
2024-10-28 15:07本頁面
【正文】 學(xué)習(xí)并使用貪心算法與回溯法的思想 。 學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法 。 熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn) ， 掌握樹和森林與二叉樹的轉(zhuǎn)換方法 。 熟練掌握各種 遍歷策略 的遞歸算法 ，了解遍歷過程中 “ 棧 ” 的作用和狀態(tài) ， 而且能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其他操作 。 ? 基本要求： 熟練掌握二叉樹的 結(jié)構(gòu)特性 ， 了解相應(yīng)的 證明方法 。它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。 構(gòu)造哈夫曼樹思想： (1)根據(jù)給定的 N個(gè)權(quán)值 {w1,w2,…,wN}構(gòu)成 N棵二叉樹的集合 F ={T1,T2,…,TN}，其中每棵二叉樹 Ti中只有一個(gè)帶權(quán)為 wi的根節(jié)點(diǎn)，其左右子樹均空； (2)在 F中選取兩棵根節(jié)點(diǎn)權(quán)值最小的子樹 ， 分別做為左右子樹來構(gòu)造一棵新的二叉樹 ， 且置新的二叉樹的根節(jié)點(diǎn)的權(quán)值為其左右子樹上根節(jié)點(diǎn)的權(quán)值之和； (3)在 F中刪除這兩棵樹 ， 同時(shí)將新得到的二叉樹加入 F中； (4)重復(fù) (2)、 (3)，直到 F僅含一棵樹為止。 考慮節(jié)點(diǎn)帶權(quán)的樹： 節(jié)點(diǎn)的帶權(quán)路徑長度為從該節(jié)點(diǎn)到樹根之間的路徑長度與節(jié)點(diǎn)上權(quán)的乘積。在最壞情況下，有 O(2N)個(gè)右子節(jié)點(diǎn)都需要進(jìn)行預(yù)估，故求解 01背包問題的回溯法時(shí)間復(fù)雜度為 O(N*2N)。 預(yù)估函數(shù)的作用： 能夠估計(jì)出最優(yōu)解的上界。 設(shè)計(jì)預(yù)估函數(shù)，其返回值說明右子樹中是否存在一個(gè)比當(dāng)前解更優(yōu)的解決方案。 注 ： 為了避免無效搜索，可使用剪枝函數(shù)把不需要的子樹剪去；使用限界函數(shù)剪去得不到最優(yōu)解的子樹 ,從而提高回溯法的搜索效率。 往回移動(dòng)（回溯）至最近的活節(jié)點(diǎn)處，并使這個(gè)活節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。該新節(jié)點(diǎn)成為新的活節(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。這個(gè)開始節(jié)點(diǎn)成為活節(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展節(jié)點(diǎn)。問：應(yīng)該如何選擇裝入背包的物品 ， 使得裝入背包中物品的總價(jià)值最大 ？ 要求： 對(duì)物品 i只有兩種選擇：要么全部裝入背包，要么全都不裝入背包 借助樹形結(jié)構(gòu)組織問題的解空間，以便能用回溯法搜索整個(gè)解空間。 樹的典型應(yīng)用 ? 回溯法中的解空間樹與 01背包問題 01背包問題 : 給定 n種物品和一個(gè)背包 。 ?森林的兩種遍歷方法： (1)先序遍歷 森林 若森林非空 ， 則可按下述規(guī)則遍歷之： ① 訪問森林中第一棵樹的根節(jié)點(diǎn)； ② 先序遍歷第一棵樹中根節(jié)點(diǎn)的子樹森林； ③ 先序遍歷除去第一棵樹之后的樹構(gòu)成的森林。 A ∧B∧ C E ∧∧D ∧∧A ∧B∧CD ∧∧E ∧∧A ∧B∧CE ∧∧D ∧∧AB C EDD EBAC樹二叉樹對(duì)應(yīng)存儲(chǔ) 存儲(chǔ)解釋解釋 0 樹與二叉樹的對(duì)應(yīng)關(guān)系示例?二叉樹轉(zhuǎn)化成森林 如果 B=(root,lb,rb)是一棵二叉樹 ，則可按如下規(guī)則轉(zhuǎn)化成森林F={T1,T2, …,Tm} ① 若 B為空 ， 則 F為空； ② 若 B不空，則 F中第一棵樹 T1的根root(T1)即為二叉樹 B的根 root； T1中根節(jié)點(diǎn)的子樹森林 F1是由 B的左子樹 lb轉(zhuǎn)換而成的森林； F中除 T1之外其余樹組成的森林F’={T2,T3,…,Tm}是由 B的右子樹 rb轉(zhuǎn)換而成的森林。 RL M NP QWR 1L 0M 0N 0P 1Q 1W 30654321數(shù)組下標(biāo)數(shù)據(jù)域 父節(jié)點(diǎn)域( a ) 樹的邏輯結(jié)構(gòu) ( b ) 樹的雙親表示法示例data c 1 c Dc 2 ?degree c 1 c dc 2 ?dataRLM ∧NP ∧Q ∧W ∧∧∧∧∧∧∧∧∧∧∧∧32010 00RLMNP QW
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1