【文章內(nèi)容簡介】 620 二叉樹向樹的轉(zhuǎn)換過程 (C) 還原后的樹 F G R A B C D E (b) 去連線后 (a) 加虛線后 F G R A C D B E C F G R A D B E 2022/2/16 62 第 6章 樹和二叉樹 1森林轉(zhuǎn)換成二叉樹 G I H J A D B C (a) 森林 E F T1 T2 T3 B C D A (b)二叉樹 E F G H I J 2022/2/16 63 第 6章 樹和二叉樹 1二叉樹轉(zhuǎn)換成森林 圖 622 二叉樹還原成森林的過程 A C B D M G L H K (c) 還原成森林 (a) 二叉樹 A B C D G L K H M (b) 去連線后 A B C D M G L K H 2022/2/16 64 第 6章 樹和二叉樹 1樹的遍歷 樹的遍歷有二種方法。 ⑴ 先序遍歷 ：先訪問根結(jié)點，然后 依次先序遍歷 每棵子樹。 ⑵ 后序遍歷 ：先 依次后序遍歷 每棵子樹，然后訪問根結(jié)點。 2022/2/16 65 第 6章 樹和二叉樹 ◆ 樹的 先序遍歷 實質(zhì)上與將樹轉(zhuǎn)換成二叉樹后對二叉樹的 先序遍歷 相同。 ◆ 樹的 后序遍歷 實質(zhì)上與將樹轉(zhuǎn)換成二叉樹后對二叉樹的 中序遍歷 相同。 A B D C K G J I F H E 圖 623 樹 先序遍歷序列 : ABCDEFGIJHK 后序遍歷序列 : CDBFIJGHEKA 2022/2/16 66 第 6章 樹和二叉樹 1森林的遍歷 設(shè) F={T1, T2,?,Tm}是森林，對 F的遍歷有二種方法。 ⑴ 先序遍歷 ：按 先序遍歷 樹的方式 依次 遍歷 F中的每棵樹。森林的先序遍歷是其對應(yīng)的二叉樹的先序遍歷。 ⑵ 中序遍歷 ：按 后序遍歷 樹的方式 依次 遍歷 F中的每棵樹。森林的中序遍歷是其對應(yīng)的二叉樹的中序遍歷。 2022/2/16 67 第 6章 樹和二叉樹 A D B C E F G I H J 二叉樹遍歷先序序列： ABCDEFGHIJ 二叉樹遍歷中序序列： BCDAFEHJIG G I H J A D B C (a) 森林 E F T1 T2 T3 森林遍歷先序序列： ABCDEFGHIJ 森林遍歷中序序列： BCDAFEHJIG 2022/2/16 68 第 6章 樹和二叉樹 1 Huffman樹的構(gòu)造 圖 625是權(quán)值集合 W={8, 3, 4, 6, 5, 5}構(gòu)造 Huffman樹的過程。所構(gòu)造的 Huffman樹的 WPL是： WPL=6?2+3?3+4?3+8?2+5?3+5?3 =79 3 4 5 5 6 8 第一步 5 5 6 8 第二步 3 4 7 6 8 第三步 3 4 7 5 5 10 8 第四步 5 5 10 6 3 4 7 13 第六步 1 1 1 1 1 0 0 0 0 0 8 5 5 10 18 6 3 4 7 13 31 圖 625 Huffman樹的構(gòu)造過程 第五步 8 5 5 10 18 6 3 4 7 13 2022/2/16 69 第 6章 樹和二叉樹 1 Huffman編碼 若字符集 C={a, b, c, d, e, f}所對應(yīng)的權(quán)值集合為W={8, 3, 4, 6, 5, 5}，如圖 625所示，則字符 a,b, c,d, e,f所對應(yīng)的 Huffman編碼分別是： 10， 010，011， 00 ， 110， 111。 1 1 1 1 1 0 0 0 0 0 8 5 5 10 18 6 3 4 7 13 31 圖 625 Huffman樹的構(gòu)造過程 a e f d c b a： 10 b： 010 c： 011 d： 00 e： 110 f： 111 2022/2/16 70 第 6章 樹和二叉樹 二叉樹存儲結(jié)構(gòu)及遍歷練習(xí) 設(shè)有如圖 627所示的二叉樹。 ① 分別用順序存儲方法和二叉鏈表 存儲方法畫出該二叉樹的存儲結(jié)構(gòu)。 ② 寫出該二叉樹的先序、中序、后序遍歷序列。 圖 627 二叉樹 a d e b f g c h k m n 2022/2/16 71 第 6章 樹和二叉樹 2已知 遍歷序列 畫二叉樹 1）已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為 ABDGHCEFI和 GDHBAECIF，請畫出這棵二叉樹，然后給出該樹的后序遍歷序列。 2） 設(shè)一棵二叉樹的中序遍歷序列和后序遍歷序列分別為 BDCEAFHG和 DECBHGFA ，請畫出這棵二叉樹，然后給出該樹的先序序列。 2022/2/16 72 第 6章 樹和二叉樹 2二叉樹 遍歷 算法應(yīng)用 以二叉鏈表為存儲結(jié)構(gòu)，請分別寫出求二叉樹的結(jié)點總數(shù)及葉子結(jié)點總數(shù)的算法。 2森林與二叉樹的轉(zhuǎn)換 設(shè)圖 627所示的二叉樹是森林 F所對應(yīng)的二叉樹，請畫出森林 F。 圖 627 二叉樹 a d e b f g c h k m n 2022/2/16 73 第 6章 樹和二叉樹 2 樹 與二叉樹的轉(zhuǎn)換及遍歷和存儲 設(shè)有一棵樹，如圖 628所示。 ① 請分別用雙親表示法、孩子表示法、孩子兄弟表示法給出該樹的存儲結(jié)構(gòu)。 ② 請給出該樹的先序遍歷序列和后序遍歷序列。 ③ 請將這棵樹轉(zhuǎn)換成二叉樹。 a d e b f g m h k c n 圖 628 一般的樹 2022/2/16 74 第 6章 樹和二叉樹 2 huffman樹的構(gòu)造及編碼方法 1）設(shè)給定權(quán)值集合 w={3,5,7,8,11,12} ，請構(gòu)造關(guān)于w的一棵 huffman樹，并求其加權(quán)路徑長度 WPL 。 2）假設(shè)用于通信的電文是由字符集 {a, b, c, d, e, f, g, h}中的字符構(gòu)成， 這 8個字符在電文中出現(xiàn)的概率分別為 {, , , , , , , } 。 ① 請畫出對應(yīng)的 huffman樹 (按左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)的次序構(gòu)造 )。 ② 求出每個字符的 huffman編碼。 2022/2/16 75 第 7章 圖 頂點的度、入度、出度概念 頂點的度、入度、出度計算 圖的鄰接矩陣 (數(shù)組 )表示法 圖的鄰接表存儲結(jié)構(gòu) 最小生成樹 有向圖的拓?fù)渑判? 關(guān)鍵路徑計算 Dijkstra 單源點最短路徑算法 求每一對頂點間最短路徑的弗羅伊德 (Floyd)算法 圖存儲結(jié)構(gòu)練習(xí) 1最小生成樹計算練習(xí) 2022/2/16 76 第 7章 圖 1 Dijkstra算法練習(xí) 1 Floyd 算法練習(xí) 1拓?fù)渑判蛩惴ň毩?xí) 1關(guān)鍵路徑和關(guān)鍵活動算法練習(xí) 2022/2/16 77 第 7章 圖 頂點的度、入度、出度概念 對于 無向圖 G=(V， E)， vi?V，圖 G中 依附 于 vi的 邊的數(shù)目稱為頂點 vi的 度 (degree)，記為 TD(vi)。 對 有向圖 G=(V， E)，若 vi ?V ，圖 G中以 vi作為起點的 有向邊 (弧 )的數(shù)目稱為頂點 vi的出度 (Outdegree)，記為 OD(vi) ； 以 vi作為終點 的 有向邊 (弧 )的數(shù)目稱為頂點 vi的 入度 (Indegree)，記為 ID(vi) 。頂點 vi的出度 與 入度 之和稱為 vi的 度 ，記為 TD(vi) 。即 TD(vi)=OD(vi)+ID(vi) 顯然，所有 頂點度的和 是圖中 邊 或 弧 的 2倍。 即 ∑TD(vi)=2e i=1, 2, …, n ， e為圖的邊或弧數(shù) 。 2022/2/16 78 第 7章 圖 頂點的度、入度、出度 計算 計算如下兩圖頂點的度、入度和出度。 A B L M G3 C F I D E G H K J v1 v2 v3 v4 G1 2022/2/16 79 第 7章 圖 圖的鄰接矩陣 (數(shù)組 )表示法 圖的存儲結(jié)構(gòu)包括 頂點 信息、 弧 信息、 頂點數(shù) 和 弧數(shù) 以及 圖類型 （有向圖還是無向圖）。 根據(jù)下圖描述寫出圖的鄰接矩陣存儲結(jié)構(gòu)定義或者根據(jù)圖的鄰接矩陣存儲結(jié)構(gòu)定義畫出圖的存儲示意圖。 2022/2/16 80 第 7章 圖 v1 v2 v4 v5 G2 v3 圖的鄰接矩陣 V1 V2 V3 V4 V5 vexs 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 V1 V2 V3 V4 V1 V2 V3 V4 (info信息不確定 ) vexnum=5 arum=6 kind=UDG(無向圖 ) V5 V5 2022/2/16 81 第 7章 圖 圖的鄰接表存儲結(jié)構(gòu) 對圖的 每個頂點 建立一個 單鏈表 ，存儲該頂點所有鄰接頂點 及其相關(guān)信息。每一個單鏈表設(shè)一個 表頭結(jié)點 。 第 i個單鏈表 表示依附于 頂點 Vi的邊 (對 有向圖 是以頂點 Vi為頭或尾的弧 )。 2022/2/16 82 第 7章 圖 根據(jù)下圖描述寫出圖的鄰接表存儲結(jié)構(gòu)定義或者根據(jù)圖的鄰接表存儲結(jié)構(gòu)定義畫出圖的存儲示意圖。 圖 710 無向圖及其鄰接表 v1 v2 v3 v4 v5 0 1 2 3 4 MAX_VEX1 v1 v2 v3 v4 ┇ ┇ v5 2 1 3 ? 0 2 ? 0 3 1 4 ? 2 0 4 ? 2 3 ? 表頭向量 V2 V3 V4 2022/2/16 83 第 7章 圖 最小生成樹 1）普里姆 (Prim)算法 按 prime算法從 v2出發(fā)構(gòu)造最小生成樹的過程。 2022/2/16 84 第 7章 圖 v1 v3 v2 v4 v5 4 8 5 7 12 11 3 6 (a) v1 v3 v2 v4 v5 4 8 5 7 12 11 3 6 (b)與 V2鄰接的邊的權(quán)值為{8,5,11,12,7},其中權(quán)值最小的邊是 V2V4邊 ,將 V2 、 V4和邊 V2V4加入最小生成樹 v1 v3 v2 v4 v5 4 8 5 7 12 11 3 6 (c)將當(dāng)前的局部最小生成樹看成一個結(jié)點 ,如橢圓所圍。與該橢圓鄰接的邊的權(quán)值為 {8,4,3,11,12,7},其中權(quán)值最小的邊是 V4V5邊 ,將 V5 和邊 V4V5加入最小生成樹 2022/2/16 85 第 7章 圖 v1 v3 v2 v4 v5 4 8 5 7 12 11 3 6 (d)將當(dāng)前的局部最小生成樹看成一個結(jié)點 ,如不規(guī)則封閉曲線所圍。與該封閉曲線鄰接的邊的權(quán)值為{8,4,6,11,7},其中權(quán)值最小的邊是V1V4邊 ,將 V1 和邊 V1V4加入最小生成樹 v1 v3 v2 v4 v5 4 8 5 7 12 11 3 6 (d)將當(dāng)前的局部最小生成樹看成一個結(jié)點 ,如不規(guī)則封閉曲線所圍。與該封閉曲線鄰接的邊的權(quán)值為{6,11,7},其中權(quán)值最小的邊是 V5V3邊 ,將 V3 和邊 V5V3加入最小生成樹 2022/2/16 86 第 7章 圖 v1 v3 v2 v4 v5 4 8 5 7 12 11 3 6 (e)紫紅色頂點及紫紅色邊最小生成樹和大紅頂點為最小生成樹 v1 v3 v2 v4 v5 4 5 3 6 (f)刪除其它邊得到的最小生成樹 20