第6章樹(shù)與二叉樹(shù)(存儲(chǔ)版)
【正文】 能夠估計(jì)出最優(yōu)解的上界。它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。 學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法 。 熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn) ， 掌握樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法 。 構(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ù)為止。 設(shè)計(jì)預(yù)估函數(shù)，其返回值說(shuō)明右子樹(shù)中是否存在一個(gè)比當(dāng)前解更優(yōu)的解決方案。這個(gè)開(kāi)始節(jié)點(diǎn)成為活節(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展節(jié)點(diǎn)。 A ∧B∧ C E ∧∧D ∧∧A ∧B∧CD ∧∧E ∧∧A ∧B∧CE ∧∧D ∧∧AB C EDD EBAC樹(shù)二叉樹(shù)對(duì)應(yīng)存儲(chǔ) 存儲(chǔ)解釋解釋 0 樹(shù)與二叉樹(shù)的對(duì)應(yīng)關(guān)系示例?二叉樹(shù)轉(zhuǎn)化成森林 如果 B=(root,lb,rb)是一棵二叉樹(shù) ，則可按如下規(guī)則轉(zhuǎn)化成森林F={T1,T2, …,Tm} ① 若 B為空 ， 則 F為空； ② 若 B不空，則 F中第一棵樹(shù) T1的根root(T1)即為二叉樹(shù) B的根 root； T1中根節(jié)點(diǎn)的子樹(shù)森林 F1是由 B的左子樹(shù) lb轉(zhuǎn)換而成的森林； F中除 T1之外其余樹(shù)組成的森林F’={T2,T3,…,Tm}是由 B的右子樹(shù) rb轉(zhuǎn)換而成的森林。 53214( a ) 二叉樹(shù)T∧22∧1 14 ∧∧5 ∧345∧3 ∧ ∧214 ∧∧5 ∧∧3 ∧∧( b ) 二叉樹(shù)T 的單指針存儲(chǔ) ( c ) 二叉樹(shù)T 的雙指針存儲(chǔ) ( d ) 二叉樹(shù)T 的三指針存儲(chǔ)圖6 . 6 二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示例root root root? 鏈?zhǔn)酱鎯?chǔ) 單叉鏈表 三叉鏈表 二叉鏈表 常用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：二叉鏈表 二叉樹(shù)操作的實(shí)現(xiàn) ? 遍歷（周游）算法 深度優(yōu)先遍歷： 先序遍歷：若二叉樹(shù)為空 ， 則空操作；否則 (1)訪問(wèn)根節(jié)點(diǎn)； (2)先序遍歷左子樹(shù)； (3)先序遍歷右子樹(shù) 。 完全二叉樹(shù)： （ 1）葉子節(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)； （ 2）對(duì)任一節(jié)點(diǎn)，若其右分支下的子孫節(jié)點(diǎn)的最大層次為 k，則其左分支下的子孫的最大層次不小于 k。 同時(shí) ， 集合 T具有下列的性質(zhì)： (1) 如果 T是空集 ， 則稱(chēng) T是空的二叉樹(shù) 。 幾種基本操作 : treeCreate(amp。 樹(shù)的遞歸定義： 樹(shù)是由一個(gè)或多個(gè)節(jié)點(diǎn)組成的有限集 T，它滿足下面兩個(gè)條件： (1)有一個(gè)特定的節(jié)點(diǎn)稱(chēng)之為 根 。 除了 首元 （ 唯一存在 ，在樹(shù)形結(jié)構(gòu)中稱(chēng)為 “根” 節(jié)點(diǎn)）沒(méi)有前驅(qū)元素以外，樹(shù)中其他所有元素（ 節(jié)點(diǎn) ）都有且只有一個(gè)直接前驅(qū)元素（ 父 節(jié)點(diǎn)）；直接后繼元素則沒(méi)有限制：沒(méi)有直接后繼元素的節(jié)點(diǎn)（ 葉 節(jié)點(diǎn)）可以有多個(gè)；存在直接后繼元素的節(jié)點(diǎn)，其直接后繼元素的個(gè)數(shù)也可以有多個(gè)。 AB C DE F GHBGFHDECAABCDEFHG( b ) 文式圖表示方法( a ) 倒置的樹(shù)形圖表示方法 ( c ) 凹入表的表示方法圖6 . 2 樹(shù)形結(jié)構(gòu)中分支與層次特性的表示本書(shū)中描述 樹(shù)形結(jié)構(gòu) 的方式 樹(shù)的基本術(shù)語(yǔ) ?節(jié)點(diǎn) ?節(jié)點(diǎn)的度 ?葉子或終端節(jié)點(diǎn) ?非終端節(jié)點(diǎn)或分支節(jié)點(diǎn) ?內(nèi)部節(jié)點(diǎn) ?樹(shù)的度 ?孩子 ?雙親 ?兄弟 ?祖先 ?子孫 ?節(jié)點(diǎn)的層次 ?樹(shù)的深度或高度
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1