第6章樹與二叉樹-免費(fèi)閱讀
【正文】 掌握各種建立二叉樹和樹的存儲(chǔ)結(jié)構(gòu)的方法 。 －－－－貪心算法 C DABA B DCC DA BC DBA11 4 3 23 211 41143 243 2115959520C DAB( a ) 初始集合含4 棵樹 ( b ) 集合含3 棵樹 ( c ) 集合含2 棵樹 ( d ) 集合中只含1 棵樹 ( e ) 哈夫曼樹的前綴編碼111 000A:0B:10C:110D:111圖6 . 1 4 哈夫曼樹的構(gòu)造過(guò)程及哈夫曼編碼 貪心算法并不從整體最優(yōu)的角度來(lái)考慮問(wèn)題。以此作為剪枝的依據(jù)。 2. 在當(dāng)前擴(kuò)展節(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新節(jié)點(diǎn)。 AB EEAB C DFGDBACEGFDCGF樹與二叉樹對(duì)應(yīng)森林與二叉樹對(duì)應(yīng)樹根相連圖6 . 1 1 森林與二叉樹的對(duì)應(yīng)關(guān)系示例 樹的遍歷 ? 樹的遍歷 先根（次序）遍歷： 先訪問(wèn)樹的根節(jié)點(diǎn)，然后按照從左至右的次序 先根遍歷 根的每棵子樹 后根（次序） 遍歷：先按照從左至右的次序 后根遍歷 每棵子樹，然后訪問(wèn)根節(jié)點(diǎn)。 中序遍歷：若二叉樹為空 ， 則空操作；否則 (1)中序遍歷左子樹； (2)訪問(wèn)根節(jié)點(diǎn)； (3)中序遍歷右子樹 。 滿二叉樹是完全二叉樹，但完全二叉樹不一定是滿二叉樹。 (2) 如果 T是有限集 ， 則 T由一個(gè)特定的 、 稱之為根 的節(jié)點(diǎn) ， 以及稱為該根的兩個(gè)互不相交的 左子樹 和 右子樹 構(gòu)成 ， 同時(shí)這兩棵子樹亦是 二叉樹 。tree) treeDestroy (amp。 (2)其余的節(jié)點(diǎn)分成 m(m≥ 0)個(gè) 互不相交的有限集 T1， T2， …， Tm， 其中每個(gè)集合本身又是一棵 樹 ， 稱 T1， T2， …， Tm為根的子樹 。第 6章 樹與二叉樹 樹的概念和運(yùn)算 二叉樹 樹和森林 樹的典型應(yīng)用 本章小結(jié) 樹的概念和運(yùn)算 樹形結(jié)構(gòu)是 線性結(jié)構(gòu)的拓廣 。 遞歸是樹的固有屬性 樹的表示： 體現(xiàn)樹形結(jié)構(gòu)中 分支 和 層次 的特性 。tree) treeClear(amp。 遞歸定義 二叉樹可以有 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）。 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)后序遍歷左子樹； (2)后序遍歷右子樹； (3)訪問(wèn)根節(jié)點(diǎn)。 ?森林的兩種遍歷方法： (1)先序遍歷 森林 若森林非空 ， 則可按下述規(guī)則遍歷之： ① 訪問(wèn)森林中第一棵樹的根節(jié)點(diǎn)； ② 先序遍歷第一棵樹中根節(jié)點(diǎn)的子樹森林； ③ 先序遍歷除去第一棵樹之后的樹構(gòu)成的森林。該新節(jié)點(diǎn)成為新的活節(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。 預(yù)估函數(shù)的作用：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1