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