第6章樹與二叉樹-文庫(kù)吧資料
2024-11-01 15:07本頁(yè)面
【正文】 rootroot節(jié)點(diǎn)的結(jié)構(gòu)節(jié)點(diǎn)的結(jié)構(gòu)( c ) 樹的一種孩子表示法示例( d ) 樹的另一種孩子表示法示例RLM ∧NP ∧Q ∧W ∧0654321數(shù)據(jù)域 子節(jié)點(diǎn)域L M N ∧P Q ∧W ∧RLM ∧NP ∧Q ∧W ∧0654321數(shù)據(jù)域 子節(jié)點(diǎn)域L M N ∧P Q ∧W ∧1000113父節(jié)點(diǎn)域( e ) 樹的孩子鏈表 ( e ) 樹的帶雙親的孩子鏈表 樹的雙 親表示法與孩子表示法R ∧LP∧ M∧N ∧Q ∧∧W ∧∧data nextSiblingfirstChild節(jié)點(diǎn)的數(shù)據(jù)域節(jié)點(diǎn)的下一個(gè)兄弟域節(jié)點(diǎn)的第一個(gè)孩子域( a ) 樹節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu) ( b ) 圖6 . 8 ( a ) 中的樹對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)圖6 . 9 樹的左孩子右兄弟存儲(chǔ)結(jié)構(gòu) 樹、森林與二叉樹的轉(zhuǎn)換 ?森林轉(zhuǎn)換成二叉樹 如果 F={T1,T2,…,Tm}是森林 ， 則按如下規(guī)則轉(zhuǎn)化成一棵二叉樹 B=(root,lb,rb)。 第二種是孩子表示法 。 后序遍歷：若二叉樹為空 ， 則空操作；否則 (1)后序遍歷左子樹； (2)后序遍歷右子樹； (3)訪問(wèn)根節(jié)點(diǎn)。 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)訪問(wèn)根節(jié)點(diǎn)； (2)先序遍歷左子樹； (3)先序遍歷右子樹 。 二叉樹的存儲(chǔ)結(jié)構(gòu) ? 順序存儲(chǔ) 以節(jié)點(diǎn)在向量中的相對(duì)位置來(lái)表示節(jié)點(diǎn)間的關(guān)系。 ② 如果 2i n， 則節(jié)點(diǎn) i無(wú)左孩子 （ 節(jié)點(diǎn) i是葉子節(jié)點(diǎn) ） ；否則其左孩子 LCHILD(i)是節(jié)點(diǎn) 2i 。 124 536 7124 536124 5312431241243( b ) 完全二叉樹( a ) 滿二叉樹 ( c ) 完全二叉樹 ( d ) 完全二叉樹 ( e ) 非完全二叉樹 ( f ) 非完全二叉樹圖6 . 4 特殊形狀的二叉樹35完全二叉樹的兩個(gè)重要特性： 性質(zhì) (4)：具有 n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為 ?log2n?+1。 完全二叉樹： （ 1）葉子節(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)； （ 2）對(duì)任一節(jié)點(diǎn)，若其右分支下的子孫節(jié)點(diǎn)的最大層次為 k，則其左分支下的子孫的最大層次不小于 k。 滿二叉樹： 一棵深度為 k且有 2k1個(gè)節(jié)點(diǎn)的二叉樹。 ?性質(zhì) (3)：對(duì)任何一棵二叉樹 T，如果其葉節(jié)點(diǎn)數(shù)為 n0，度為 2的節(jié)點(diǎn)數(shù)為 n2，則n0=n2+1。 遞歸定義 二叉樹可以有 5種基本形態(tài)， ( a ) 空二叉樹( b ) 只含根結(jié)點(diǎn)二叉樹 ( c ) 右子樹為空的二叉樹 ( d ) 左、右子樹非空空的二叉樹 ( e ) 左子樹為空的二叉樹圖6 . 3 二叉樹的五種基本形態(tài)rootroot root root?二叉樹的基本運(yùn)算 與樹的基本運(yùn)算相類似 詳見二叉樹的 ADT說(shuō)明 二叉樹的性質(zhì) ? 性質(zhì) (1)：在二叉樹的第 i層上至多有 2i1個(gè)節(jié)點(diǎn)（ i≥ 1）。 同時(shí) ， 集合 T具有下列的性質(zhì)： (1) 如果 T是空集 ， 則稱 T是空的二叉樹 。parent)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1