第6章樹與二叉樹(文件)
【正文】 （ 2）對(duì)任一節(jié)點(diǎn)，若其右分支下的子孫節(jié)點(diǎn)的最大層次為 k，則其左分支下的子孫的最大層次不小于 k。 ② 如果 2i n， 則節(jié)點(diǎn) i無左孩子 （ 節(jié)點(diǎn) i是葉子節(jié)點(diǎn) ） ；否則其左孩子 LCHILD(i)是節(jié)點(diǎn) 2i 。 53214( a ) 二叉樹T∧22∧1 14 ∧∧5 ∧345∧3 ∧ ∧214 ∧∧5 ∧∧3 ∧∧( b ) 二叉樹T 的單指針存儲(chǔ) ( c ) 二叉樹T 的雙指針存儲(chǔ) ( d ) 二叉樹T 的三指針存儲(chǔ)圖6 . 6 二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示例root root root? 鏈?zhǔn)酱鎯?chǔ) 單叉鏈表 三叉鏈表 二叉鏈表 常用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：二叉鏈表 二叉樹操作的實(shí)現(xiàn) ? 遍歷（周游）算法 深度優(yōu)先遍歷： 先序遍歷：若二叉樹為空 ， 則空操作；否則 (1)訪問根節(jié)點(diǎn)； (2)先序遍歷左子樹； (3)先序遍歷右子樹 。 第二種是孩子表示法 。 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)換而成的森林。 樹的典型應(yīng)用 ? 回溯法中的解空間樹與 01背包問題 01背包問題 : 給定 n種物品和一個(gè)背包 。這個(gè)開始節(jié)點(diǎn)成為活節(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展節(jié)點(diǎn)。 往回移動(dòng)（回溯）至最近的活節(jié)點(diǎn)處，并使這個(gè)活節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。 設(shè)計(jì)預(yù)估函數(shù)，其返回值說明右子樹中是否存在一個(gè)比當(dāng)前解更優(yōu)的解決方案。在最壞情況下，有 O(2N)個(gè)右子節(jié)點(diǎn)都需要進(jìn)行預(yù)估，故求解 01背包問題的回溯法時(shí)間復(fù)雜度為 O(N*2N)。 構(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é)構(gòu)特性 ， 了解相應(yīng)的 證明方法 。 熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn) ， 掌握樹和森林與二叉樹的轉(zhuǎn)換方法 。 學(xué)習(xí)并使用貪心算法與回溯法的思想 。 學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法 。 熟練掌握各種 遍歷策略 的遞歸算法 ，了解遍歷過程中 “ 棧 ” 的作用和狀態(tài) ， 而且能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其他操作 。它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。 考慮節(jié)點(diǎn)帶權(quán)的樹： 節(jié)點(diǎn)的帶權(quán)路徑長度為從該節(jié)點(diǎn)到樹根之間的路徑長度與節(jié)點(diǎn)上權(quán)的乘積。 預(yù)估函數(shù)的作用： 能夠估計(jì)出最優(yōu)解的上界。 注 ： 為了避免無效搜索，可使用剪枝函數(shù)把不需要的子樹剪去；使用限界函數(shù)剪去得不到最優(yōu)解的子樹 ,從而提高回溯法的搜索效率。該新節(jié)點(diǎn)成為新的活節(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。問：應(yīng)該如何選擇裝入背包的物品 ， 使得裝入背包中物
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1