第6章樹與二叉樹-文庫吧在線文庫
【正文】 ?有序樹 ?無序樹 ?森林 樹的 ADT ADT Tree { 數(shù)據(jù)對象為 D: D是具有相同特性的數(shù)據(jù)元素的集合 數(shù)據(jù)間的關(guān)系 R: (1) 若 D為空集 ,則稱為空樹 。tree) treeEmpty(tree) treeWidth(tree) 創(chuàng)建一棵樹 tree 銷毀一棵已有的樹tree 創(chuàng)建一棵樹 tree 判樹是否為空 求樹的度 treeDepth(tree) treeRoot(tree) treeInsert(amp。 ?性質(zhì) (2)：深度為 k的二叉樹至多有 2k1個(gè)節(jié)點(diǎn)（ k ≥ 1）。 性質(zhì) (5)：如果對一棵有 n個(gè)節(jié)點(diǎn)的完全二叉樹 （ 其深度為 ?log2n? +1） 的節(jié)點(diǎn)按層序編號 （ 從第 1層到第 ?log2n? +1層 ， 每層從左到右 ） ， 則對任一節(jié)點(diǎn) i（ 1≤ i≤ n） ， 有： ① 如果 i = 1， 則節(jié)點(diǎn) i是二叉樹的根 ， 無雙親；如果 i 1， 則其雙親 PARENT (i) 是節(jié)點(diǎn) ?i/2? 。 二叉樹遍歷的典型應(yīng)用－－表達(dá)式樹 cba*cba*cba*cba*(a)a*(bc)的 表達(dá)式樹T ( b ) 先序遍歷表達(dá)式樹T ( c ) 中序遍歷表達(dá)式樹T ( d ) 后序遍歷表達(dá)式樹T圖6 . 7 表達(dá)式樹與三種遍歷 先序遍歷此二叉樹 ， 得到的二叉樹的先序序列為： *abc； 中序遍歷此二叉樹 ， 得到該二叉樹的中序序列為： a*bc； 后序遍歷此二叉樹，得到該二叉樹的后序序列為： abc*； 前綴表示（波蘭式） 后綴表示（逆波蘭式） 中綴表示（中綴式） 非遞歸實(shí)現(xiàn)樹的深度優(yōu)先遍歷 利用棧 非遞歸實(shí)現(xiàn)樹的廣度優(yōu)先遍歷 利用隊(duì)列 ?遍歷算法 時(shí)間 復(fù)雜度： O(N) ?遍歷算法 空間 復(fù)雜度：至多為 O(N) 樹和森林 ? 樹的存儲結(jié)構(gòu) 三種典型的表示法： 第一種是 雙親表示法 。 (2)后序遍歷森林 若森林非空 ， 則可按下述規(guī)則遍歷之： ① 后序遍歷森林中第一棵樹的根節(jié)點(diǎn)的子樹森林； ② 訪問第一棵樹的根節(jié)點(diǎn)； ③ 按后根次序遍歷除去第一棵樹之后的其余樹構(gòu)成的森林。 3. 如果在當(dāng)前擴(kuò)展節(jié)點(diǎn)處不能再向縱深方向移動，則當(dāng)前擴(kuò)展節(jié)點(diǎn)就成為死節(jié)點(diǎn)。 01背包問題的回溯法效率分析： 預(yù)估函數(shù)需要 O(N)時(shí)間，其中 N為物品種類的數(shù)量。 ?哈夫曼樹應(yīng)用： 哈夫曼編碼 －－電文的 二進(jìn)制前綴編碼 本章小結(jié) ? 基本內(nèi)容： 1. 樹的 基本概念 2. 二叉樹 的定義、性質(zhì)和存儲結(jié)構(gòu)；二叉樹的遍歷和線索化以及 遍歷算法 的各種描述形式； 3. 樹和森林 與二叉樹的轉(zhuǎn)換、樹和森林的遍歷； 典型應(yīng)用 ； 回溯法 與 貪心算法 。 掌握建立哈夫曼編碼的方法 。 層次遍歷 是按另一種搜索策略進(jìn)行的遍歷 。 樹的帶權(quán)路徑長度為樹中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和，記作： )0,1(N1NklwW P L kNkk ????? ??11 4 2311 4232 3114(a)WPL=(11+4+3+2)*2=40 (b)WPL=(11+4)*3+3*2+2*1=53 (c)WPL=(2+3)*3+4*2+11*1=34 3 具有不同帶權(quán)路徑長度的二叉樹 試構(gòu)造一棵有 N個(gè)葉子結(jié)點(diǎn)的二叉樹，則其中帶權(quán)路徑長度 WPL最小的二叉樹稱作最優(yōu)二叉樹或哈夫曼（ Huffman）樹。 具體到 01背包問題： 預(yù)處理 ：按 各物品單位重量所包含的價(jià)值從大到小進(jìn)行排列物品。 ABD EIH KJCF GML ON111 1 1 1100
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1