【正文】 V2 ， Vl， V3 ， V3， V4 ， V4， V2} (a ) 無向圖 G1 (b) 有向圖 G2 圖 6 . 1 圖的類型 圖的相關術語 圖有以下術語： ? 1. 無向圖 : 每條邊都沒有方向 (如圖 (a))的圖稱為無向圖 。 在有向圖中，用尖括號表示兩個頂點間的首尾關系，有向邊也稱為弧。 圖的定義 Gl=(V ， E) V= {V1， V2， V3， V4， V5} 。 ? 在有向圖中 ， 用尖括號表示兩個頂點間的首尾關系 ， 有向邊也稱為弧 。 用二元組定義為： ? G=(V， E) ? 其中 ， G表示一個圖 ， V表示圖 G中全部頂點組成的非空集合 ， E是圖 G中全部邊組成的集合 。 ? 教學目標： 通過本章的學習 ， 使讀者能掌握圖的概念 、有關術語 、 存儲方式和遍歷算法等內容 ， 理解圖的應用 。 A? Thanks! 第 6章 圖 （時間： 2次課， 4學時） 第 6章 圖 ? 教學提示： 結合前幾章的知識和圖結構的特點 ， 介紹圖的概念 、 有關術語 、 存儲和遍歷等內容 。 (5) 設計一個算法 ， 求給定值 x的結點在二叉樹中的所有祖先 ， 設樹中值為 x的結點不多于一個 。 (3) 對以二叉鏈表表示的樹編寫計算樹的深度的算法 。 習 題 __算法題 5. 算法題 (1) 假設二叉樹中至多有一個結點的數(shù)據(jù)字段的值為 x， 編寫算法 ， 摘除以該結點為根的子樹 ， 使原二叉樹分為兩棵二叉樹 。 (8)對給定的權值 {2,3,4,7,8,9}，構造出相應的赫夫曼樹和赫夫曼編碼，并求出帶權路徑的長度 WPL。 ① 先序遍歷序列： EBADCFHGIKJ 中序遍歷序列： ABCDEFGHIJK ② 中序遍歷序列： ACBGEDF 后序遍歷序列： ABCDEFG (6) 分別畫出圖 。 (4) 對圖 ，寫出此樹的先序遍歷、中序遍歷和后序遍歷的結點序列。 ( ) 習 題 __解答題 4. 解答題 (參見教材題目及圖例 ) (1) 已知一棵樹邊的集合為 {(I， M)， (I， N)， (E， I)， (B， E)， (B， D)， (A，B)， (G， J)， (G， K)， (C， G)， (C， F)， (H， L)， (C， H)， (A， C)}，畫出這棵樹，并回答下列問題： ① 哪個結點是根結點？ ② 哪些結點是葉子結點 ? ③ 哪個結點是結點 G的雙親結點 ? ④ 哪些結點是結點 G的祖先結點？ ⑤ 哪些結點是結點 G的孩子結點 ? ⑥ 哪些結點是結點 E的子孫結點 ? ⑦ 哪些結點是結點 E的兄弟結點？哪些是結點 F的兄弟結點？ ⑧ 結點 B和 N的層次分別是多少 ? ⑨ 樹的深度是多少 ? ⑩ 以結點 C為根的子樹的深度是多少 ? (2) 說明一棵度為 2的樹與一棵二叉樹之間的區(qū)別。 ( ) (3) 給定二叉樹的先序遍歷序列和后序遍歷序列，就能惟一地確定一棵二叉樹。 A. 不發(fā)生變化 B. 發(fā)生變化 C. 不能確定 D. 以上都不對 習 題 __判斷題 3. 判斷題 (1) 一棵度為 2的樹就是一棵二叉樹。 A. BDGCEFHA C. BDGAECHF D. GDBEHFCA (9) 在一棵非空二叉樹的中序遍歷序列中 ， 根結點的右邊 _____。 +1 B. 2k C. 2k1 +1 習 題 __選擇題 (7) 樹轉換成二叉樹后 ， 以下結論正確的是 _____。 +n3 +n2+n3 (5) 設森林 T中有三棵樹 ， 第一 、 二 、 三棵數(shù)的結點個數(shù)分別為 n n n3，那么將森林轉換成二叉樹后 ， 其根結點的左子樹上有 _____個結點 。 A. 二維數(shù)組和三維數(shù)組 B. 三元組和散列 C. 三元組和十字鏈表 D. 散列和十字鏈表 (3) 設二叉樹有 n個結點 ， 則其深度為 _____。 習 題 __選擇題 2. 選擇題 (1) 數(shù)組的基本操作主要包括 _____。 (9) 有 m個葉子結點的哈夫曼樹 ， 其結點總數(shù)為 ________________。 (7) 如果 T2是由有序樹 T轉換而來的二叉樹 ， 那么 T中結點的后序就是 T2中結點的 _____序 。 習 題 __填空題 (5) 一棵深度為 k的滿二叉樹的結點總數(shù)為 ___________， 一棵深度為 k的完全二叉樹的結點總數(shù)的最小值為 ___________， 最大值為 ___________。 (3) 對于一個具有 n個結點的二叉樹 ， 當它為一棵 _________二叉樹時 ， 具有最小高度 ， 即為 _________， 當它為一棵單支樹時具有為 _________高度 ， 即為 _________。 }/*main*/ 習 題 ? 1 填空題 ? 2 選擇題 ? 3 判斷題 ? 4 解答題 ? 5 算法題 習 題 __填空題 1. 填空題： (1) 假定一棵樹的嵌套括號表示法為 A(B(E)， C(F(H， I， J)， G)， D)， 則該樹的度為 _________， 樹的深度為 _________， 終端結點的個數(shù)為 _________，單分支結點的個數(shù)為 _________， 雙分支結點的個數(shù)為 _________， 三分支結點的個數(shù)為 _________， C結點的雙親結點為 _________， 其孩子結點為_________和為 _________結點 。 printf(\n)。 root=creat()。 } } } }/*levorder*/ 實習 2(6) main() { bitree *root。 } if(trchild!=Null) { rear=rear%max+1。 if(tlchild!=Null) { 實習 2(5) rear=rear%max+1。 t=que[front]。 while(rear!=front)。 rear=1。 int rear,front。 inorder(trchild)。 }/*creat*/ 實習 2(3) void inorder(bitree *t) /*中序遍歷二叉樹 */ { if(t!=null) { inorder(tlchild)。 trchild=creat()。 tdata=x。 if(x==0) t=Null。 scanf(%d,amp。 bitree *creat() /*建立二叉樹 */ 實習 2(2) { bitree *t。 bitree *que[M]。 struct node *lchild,*rchild。 ? 題目：編寫算法對以二叉鏈表存儲的二叉樹 ， 按層序遍歷輸出 。 inorder(root)。 exchange(root)。 root=creat()。 } }/*exchange*/ main() { bitree *root。 exchang(tlchild)。 tlchild=trchild。 } }/*inorder*/ void exchange(bitree *t) /*對二叉樹 t中所有結點的左右子樹進行交換 */ { bitree *p。 printf(%4d,tdata)。 } return t。 tlchild=creat()。 else { t=(bitree*)malloc(sizeof(bitree))。x)。 實習 1(2) int x。 }bitree。 define Null 0 typedef struct node { int data。 上 機 實 習 ? 實習 1 ? 實習 2 實習 1 掌握二叉樹的建立算法 ， 并利用遞歸實現(xiàn)中序遍歷二叉樹 。 ② 訪問第一棵樹的根結點。 ③ 先序遍歷除去第一棵樹之后剩余的樹構成的森林。 ? 先序遍歷 若森林非空，則先序遍歷方法為： ① 訪問森林中第一棵樹的根結點。 例如：圖 后根遍歷序列為 BDCEA。 例如：圖 根遍歷序列為 ABCDE。 樹和森林的遍歷 ? 由樹的結構定義可以得出樹的遍歷方法主要有兩種：先根(次序 )遍歷和后根 (次序 )遍歷 。 樹、森林與二叉樹的轉換 二叉樹轉換成森林 如果 B={root， LB， RB}是一棵二叉樹 ， 則可以按照如下規(guī)則轉換成森林 F={T1， T2， … ， Tm}。 樹、森林與二叉樹的轉換 ? 森林轉換成二叉樹 如果 F={T1， T2， …Tm} 是森林，則可以按照如下規(guī)則轉換成一棵二叉樹， B={root， LB， RB}。 樹、森林與二叉樹的轉換 ? 具體步驟如下： (1) 將樹的根結點作為二叉樹的根結點； (2) 對于樹中的每個結點 ， 都將其第一個孩子結點作為該二叉樹結點的左子樹 ， 將其第一個兄弟結點作為該二叉樹結點的右子樹 。 *nextsibling。 樹的存儲結構 圖 孩子表示法 樹的存儲結構 3. 孩子兄弟表示法的結構定義如下 ： typedef struct CSNode { ElemType data。 int n, *r。 /* 孩子鏈表頭指針 */ }CTBox。 typedef struct { TelemType data。 struct CTNode *next。 /* 結點數(shù) */ }PTree。 typedef struct { PTNode nodes[MAX]。 int parent。特別是易于實現(xiàn)查找某結點的孩子結點的運算。即以二叉鏈表作為樹的存儲結構，鏈表中結點的兩個字段分別指向該結點的第一個孩子結點和下一個兄弟結點，分別命名為 firstchild字段和 nextsibling字段。 ? 2. 孩子表示法 孩子表示法是樹的一種鏈式存儲結構，其設計思想有兩種，其一是建立一個多重鏈表，存放樹中每個結點及其多棵子樹，即每個結點由一個數(shù)據(jù)字段和多個指針字段組成，數(shù)據(jù)字段中存放該結點的數(shù)據(jù)元素，每個指針字段中的指針指向一棵子樹的根結點。雙親表示法是通過結點與雙親之間的關系將樹中結點組織在一起。 其存儲結構HT的初始狀態(tài)如圖 (a)所示 ， 終結狀態(tài)如圖 (b)所示 ， 所得哈夫曼編碼如圖 (c)所示 。 構造算法 ， 參見教材 p85. 哈夫曼樹和哈夫曼編碼 __例 例 54 已知某系統(tǒng)在通訊聯(lián)絡中只可能出現(xiàn) 8種字符 ， 其出現(xiàn)的頻率分別為5％ , 29％ ， 7％ ， 8％ ， 14％ ， 3％ ， 23％ 和 11％ ， 根據(jù)算法 曼編碼 。 利用二叉樹可以設計出二進制編碼的前綴編碼 ， 將需要編碼的字符做為葉子結點構造一棵二叉樹 ， 并且約定二叉樹的左分支表示的字符為 0， 右分支表示的字符為 1， 則可以從根結點到葉子結點的路徑分支上的 0、 1組成的序列作為該葉子結點字符的編碼 。 哈夫曼樹和哈夫曼編碼 ? 2. 哈夫曼編碼