【文章內容簡介】 ang(trchild)。 } }/*exchange*/ main() { bitree *root。 實習 1(5) printf(\n)。 root=creat()。 inorder(root)。 exchange(root)。 printf(\n)。 inorder(root)。 }/*main*/ 實習 2 利用非遞歸的方法 ， 層序遍歷二叉樹 。 ? 題目：編寫算法對以二叉鏈表存儲的二叉樹 ， 按層序遍歷輸出 。 define M 100 define Null 0 typedef struct node { int data。 struct node *lchild,*rchild。 }bitree。 bitree *que[M]。 int front=0,rear=0。 bitree *creat() /*建立二叉樹 */ 實習 2(2) { bitree *t。 int x。 scanf(%d,amp。x)。 if(x==0) t=Null。 else { t=(bitree*)malloc(sizeof(bitree))。 tdata=x。 tlchild=creat()。 trchild=creat()。 } return t。 }/*creat*/ 實習 2(3) void inorder(bitree *t) /*中序遍歷二叉樹 */ { if(t!=null) { inorder(tlchild)。 printf(%4d,tdata)。 inorder(trchild)。 } }/*inorder*/ void levorder(bitree *t) /*按層序遍歷輸出二叉樹中各結點 */ { 實習 2(4) bitree *que[max]。 int rear,front。 if(t!=null) { front=0。 rear=1。 que[1]=t。 while(rear!=front)。 { front=front%max+1。 t=que[front]。 printf(%4d,tdata)。 if(tlchild!=Null) { 實習 2(5) rear=rear%max+1。 que[rear]=tlchild。 } if(trchild!=Null) { rear=rear%max+1。 que[rear]=trchild。 } } } }/*levorder*/ 實習 2(6) main() { bitree *root。 printf(\n)。 root=creat()。 inorder(root)。 printf(\n)。 levorder(root)。 }/*main*/ 習 題 ? 1 填空題 ? 2 選擇題 ? 3 判斷題 ? 4 解答題 ? 5 算法題 習 題 __填空題 1. 填空題： (1) 假定一棵樹的嵌套括號表示法為 A(B(E)， C(F(H， I， J)， G)， D)， 則該樹的度為 _________， 樹的深度為 _________， 終端結點的個數(shù)為 _________，單分支結點的個數(shù)為 _________， 雙分支結點的個數(shù)為 _________， 三分支結點的個數(shù)為 _________， C結點的雙親結點為 _________， 其孩子結點為_________和為 _________結點 。 (2) 設 F是一個森林 ， B是由 F轉換得到的二叉樹 ， F中有 n個非終端結點 ， 則 B中右指針字段為空的結點有 _________。 (3) 對于一個具有 n個結點的二叉樹 ， 當它為一棵 _________二叉樹時 ， 具有最小高度 ， 即為 _________， 當它為一棵單支樹時具有為 _________高度 ， 即為 _________。 (4) 對于一個具有 n個結點的二叉樹 ， 當它存儲在二叉鏈表中時 ， 其指針字段的總數(shù)為 _________個 ， 其中 _________個用于鏈接孩子結點 ， _________個空閑 。 習 題 __填空題 (5) 一棵深度為 k的滿二叉樹的結點總數(shù)為 ___________， 一棵深度為 k的完全二叉樹的結點總數(shù)的最小值為 ___________， 最大值為 ___________。 (6) 如果 T2是由有序樹 T轉換而來的二叉樹 ， 那么 T中結點的前序就是 T2中結點的 _____序 。 (7) 如果 T2是由有序樹 T轉換而來的二叉樹 ， 那么 T中結點的后序就是 T2中結點的 _____序 。 (8) 具有 n個結點的完全二叉樹 ， 若按層次從上到下 、 從左到右對其編號(根結點為 1號 )， 則編號最大的分支結點序號為 ___________， 編號最小的分支結點序號為 ___________， 編號最大的葉子結點序號為___________， 編號最小的葉子結點序號為 ___________。 (9) 有 m個葉子結點的哈夫曼樹 ， 其結點總數(shù)為 ________________。 (10) 由三個結點構成的二叉樹 ， 共有 _________種不同的結構 。 習 題 __選擇題 2. 選擇題 (1) 數(shù)組的基本操作主要包括 _____。 A. 建立與刪除 B. 索引與修改 D. 訪問與索引 (2) 稀疏矩陣一般的壓縮存儲方法有兩種 ， 即 _____。 A. 二維數(shù)組和三維數(shù)組 B. 三元組和散列 C. 三元組和十字鏈表 D. 散列和十字鏈表 (3) 設二叉樹有 n個結點 ， 則其深度為 _____。 A. n1 B. n C. +1 (4) 設森林 T中有三棵樹 ， 第一 、 二 、 三棵數(shù)的結點個數(shù)分別為 n n n3，那么將森林轉換成二叉樹后 ， 其根結點的右子樹上有 _____個結點 。 +n3 +n2+n3 (5) 設森林 T中有三棵樹 ， 第一 、 二 、 三棵數(shù)的結點個數(shù)分別為 n n n3，那么將森林轉換成二叉樹后 ， 其根結點的左子樹上有 _____個結點 。 +n3 +n2+n3 (6) 設深度為 k的二叉樹上只有度為 0或度為 2的結點 ， 則這類二叉樹上所含結點總數(shù)至少 _____。 +1 B. 2k C. 2k1 +1 習 題 __選擇題 (7) 樹轉換成二叉樹后 ， 以下結論正確的是 _____。 (8) 某二叉樹的前序遍歷結點訪問順序為 ABDGCEFH， 中序遍歷結點訪問順序為 DGBAECHF， 則其后序遍歷結點訪問順序為 _____。 A. BDGCEFHA C. BDGAECHF D. GDBEHFCA (9) 在一棵非空二叉樹的中序遍歷序列中 ， 根結點的右邊 _____。 A. 只有右子樹上的所有結點 B. 只有右子樹上的部分結點 C. 只有左子樹上的所有結點 D. 只有左子樹上的部分結點 (10)任何一棵二叉樹的葉結點在先序 、 中序和后序遍歷序列中的相對次序 ___。 A. 不發(fā)生變化 B. 發(fā)生變化 C. 不能確定 D. 以上都不對 習 題 __判斷題 3. 判斷題 (1) 一棵度為 2的樹就是一棵二叉樹。 ( ) (2) 無序樹的子樹沒有順序之分，而二叉樹的子樹分為左子樹和右子樹。 ( ) (3) 給定二叉樹的先序遍歷序列和后序遍歷序列，就能惟一地確定一棵二叉樹。 ( ) (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) 試分別畫出具有 3個結點的樹和具有 3個結點的二叉樹的所有結構圖。 (4) 對圖 ，寫出此樹的先序遍歷、中序遍歷和后序遍歷的結點序列。 習 題 __解答題 (5)按照下列給定二叉樹的先序遍歷序列、中序遍歷序列和后序遍歷序列，分別構造出二叉樹。 ① 先序遍歷序列： EBADCFHGIKJ 中序遍歷序列： ABCDEFGHIJK ② 中序遍歷序列： ACBGEDF 后序遍歷序列： ABCDEFG (6) 分別畫出圖 。 (7) 對圖 ，分別畫出它的順序存儲結構和二叉鏈表。 (8)對給定的權值 {2,3,4,7,8,9}，構造出相應的赫夫曼樹和赫夫曼編碼，并求出帶權路徑的長度 WPL。 (9) 將圖 。 習 題 __算法題 5. 算法題 (1) 假設二叉樹中至多有一個結點的數(shù)據(jù)字段的值為 x， 編寫算法 ， 摘除以該結點為根的子樹 ， 使原二叉樹分為兩棵二叉樹 。 (2) 編寫算法 ， 計算一棵以二叉鏈表表示的樹的所有結點中度為 1的結點個數(shù) 。 (3) 對以二叉鏈表表示的樹編寫計算樹的深度的算法 。 (4) 設計算法 ， 將給定二叉樹的葉子結點連成一個帶頭結點的單鏈表 ， 并要求葉子結點按照從左到右的順序插入 ， 而排列順序為從右到左 (逆置 )的單鏈表 。 (5) 設計一個算法 ， 求給定值 x的結點在二叉樹中的所有祖先 ， 設樹中值為 x的結點不多于一個 。 Q amp。 A? Thanks! 第 6章 圖 （時間： 2次課， 4學時） 第 6章 圖 ? 教學提示： 結合前幾章的知識和圖結構的特點 ， 介紹圖的概念 、 有關術語 、 存儲和遍歷等內容 。 指出樹和圖的區(qū)別與聯(lián)系 。 ? 教學目標： 通過本章的學習 ， 使讀者能掌握圖的概念 、有關術語 、 存儲方式和遍歷算法等內容 ， 理解圖的應用 。 第 6章 圖 ? 圖的定義和術語 ? 圖的基本操作 ? 圖的存儲表示 ? 圖的遍歷 ? 生成樹和最小生成樹 ? 習題 圖的定義和術語 ? 圖的定義 ? 圖的相關術語 圖的定義 ? 1. 圖的定義 ? 圖是由非空的頂點 (Vertices)集合和描述頂點之間關系的邊 (Edges)的有限集合組成的一種數(shù)據(jù)結構 。 用二元組定義為： ? G=(V， E) ? 其中 ， G表示一個圖 ， V表示圖 G中全部頂點組成的非空集合 ， E是圖 G中全部邊組成的集合 。