【正文】 front=front%max+1。 printf(%4d,tdata)。x)。 define M 100 define Null 0 typedef struct node { int data。 實(shí)習(xí) 1(5) printf(\n)。 inorder(trchild)。 if(x==0) t=Null。 ? 題目：二叉樹按照二叉鏈表方式存儲(chǔ) ， 編寫算法 ， 將二叉樹左右子樹進(jìn)行交換 。 樹和森林的遍歷 森林的遍歷方法主要有兩種，即先序遍歷和后序遍歷。 ① 若 F為空，即 m=0，則 B為空二叉樹； ② 若 F非空，即 m≠0，則 B的根 root即為森林中第一棵樹的根ROOT(T1)； B的左子樹 LB是從 T1中根結(jié)點(diǎn)的子樹森林F1={T11， T12， … ， T1m}轉(zhuǎn)換而成的二叉樹； B的右子樹RB是從森林 F’={T2， T3， … ， Tm}轉(zhuǎn)換而成的二叉樹。 /* 結(jié)點(diǎn)數(shù)和根的位置 */ }CTree。 樹的存儲(chǔ)結(jié)構(gòu) 2. 孩子鏈表存儲(chǔ)結(jié)構(gòu)類型定義如下： typedef struct CTNode { /* 孩子結(jié)點(diǎn) */ int child。 利用孩子兄弟表示法存儲(chǔ)樹，能方便地實(shí)現(xiàn)樹的各種操作。 設(shè)表示字符的葉子結(jié)點(diǎn)權(quán)值為 w={5,29,7,8,14,3,23,11}， n=8， 則m=2n1=15， 按照算法 。 (3) 從 F中刪除被選中的那兩棵二叉樹 ， 同時(shí)把新構(gòu)成的二叉樹加入到森林 F中 。 } } 二叉樹的遍歷 __例 先序遍歷序列： A B D F G C E H 中序遍歷序列： B F D G A C E H 后序遍歷序列： F G D B H E C A 哈夫曼樹和哈夫曼編碼 ? 哈夫曼樹又稱最優(yōu)二叉樹 ， 是一種帶權(quán)路徑長(zhǎng)度最短的樹 ， 有著廣泛的應(yīng)用 。 PreOrder(plchild)。 ? 先遍歷左子樹 ， 再遍歷右子樹 ， 最后訪問(wèn)根 (記做 LRD)。 }BiTree。 ?1. 順序存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)是用一組連續(xù)的存儲(chǔ)單元來(lái)存放二叉樹的數(shù)據(jù)元素 。 完全二叉樹的特點(diǎn)是： 二叉樹的概念 圖 滿二叉樹 圖 完全二叉樹 二叉樹的性質(zhì) ? 二叉樹具有下列重要特性 : 1. 性質(zhì) 1: 在二叉樹的第 i層上至多有 2i－ 1個(gè)結(jié)點(diǎn) (i≥1)。 TraverseTree(Tree， Visit())： 樹 Tree存在 ， Visit()是對(duì)結(jié)點(diǎn)進(jìn)行訪問(wèn)的函數(shù) 。 FirstChild(Tree， x)： 樹 Tree存在 ， x是 Tree中的某個(gè)結(jié)點(diǎn) 。 ? 基本操作： InitTree(Tree)：將 Tree初始化為一棵空樹 。 樹的表示 ? 除了樹的邏輯定義以外 ， 樹的表示法還有以下四種 。 ? 兄弟結(jié)點(diǎn)： 同一個(gè)雙親的結(jié)點(diǎn)之間互為兄弟結(jié)點(diǎn) 。 ② 其余 n1個(gè)結(jié)點(diǎn)可以劃分成 m (m0) 個(gè)互不相交的有限集 T1， T2， … ， Tm， 其中每一個(gè)集合 Ti又是一棵樹 ， 稱其為根的子樹 。數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言）中 第 5章 樹 （時(shí)間： 3次課， 6學(xué)時(shí)） 第 5章 樹 ? 教學(xué)提示： 在前面 2～ 4章中介紹了線性表 、 棧 、 隊(duì)列 、 數(shù)組 、 串等 ， 它們的邏輯結(jié)構(gòu)都是線性的 ， 即數(shù)據(jù)之間存在著一對(duì)一的關(guān)系 ， 表示數(shù)據(jù)的結(jié)點(diǎn)間具有惟一前驅(qū)和惟一后繼 。 ? 2. 關(guān)于樹結(jié)構(gòu)的基本術(shù)語(yǔ) ? 結(jié)點(diǎn)： 包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支信息 。 ? 祖先結(jié)點(diǎn)： 從樹的根結(jié)點(diǎn)到達(dá)一個(gè)結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)都是該結(jié)點(diǎn)的祖先結(jié)點(diǎn) 。 對(duì)于以下邏輯結(jié)構(gòu)的樹： T = (K， L) K = {A， B， C， D， E， F， G， H} L = {A， B， A， C， A， D， C， E， C， F ， D， G，E， H} ? T是表示樹形結(jié)構(gòu)的二元組 ， 其中 ， K是樹中結(jié)點(diǎn)的有限集 ， L是樹中結(jié)點(diǎn)之間關(guān)系的有限集 。 DestoryTree(Tree)：銷毀樹 Tree。 若 x為非葉子結(jié)點(diǎn) ， 則返回它的第一個(gè)孩子結(jié)點(diǎn) ， 否則返回 “ 空 ” 。 按某種次序?qū)?Tree的每個(gè)結(jié)點(diǎn)調(diào)用 Visit()函數(shù)訪問(wèn)一次且最多訪問(wèn)一次 。 2. 性質(zhì) 2: 深度為 k的二叉樹至多有 2k –1個(gè)結(jié)點(diǎn) (k≥1)。 根據(jù)二叉樹的性質(zhì) 5， 可得根結(jié)點(diǎn)的編號(hào)為 1， 結(jié)點(diǎn) i的左孩子的位置為L(zhǎng)child(i)=2i；右孩子的位置為 Rchild(i)=2i+1。 二叉樹的存儲(chǔ)結(jié)構(gòu) 圖 鏈表存儲(chǔ)結(jié)構(gòu) 二叉樹的遍歷 ? 二叉樹的遍歷 是指按一定規(guī)律或路徑對(duì)二叉樹中的每個(gè)結(jié)點(diǎn)進(jìn)行訪問(wèn)且僅訪問(wèn)一次 。 ? 先遍歷右子樹 ， 再遍歷左子樹 ， 最后訪問(wèn)根 (記做 RLD)。 PreOrder(prchild)。 ? 1. 哈夫曼樹 ? 路徑和路徑長(zhǎng)度 路徑是指從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支序列；路徑長(zhǎng)度是指一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的路徑上所經(jīng)過(guò)的分支數(shù)目 。 (4) 重復(fù) (2)、 (3)的操作 ， 直到森林中只含有一棵二叉樹為止 ， 此時(shí)得到的這棵二叉樹就是哈夫曼樹 。 其存儲(chǔ)結(jié)構(gòu)HT的初始狀態(tài)如圖 (a)所示 ， 終結(jié)狀態(tài)如圖 (b)所示 ， 所得哈夫曼編碼如圖 (c)所示 。特別是易于實(shí)現(xiàn)查找某結(jié)點(diǎn)的孩子結(jié)點(diǎn)的運(yùn)算。 struct CTNode *next。 樹的存儲(chǔ)結(jié)構(gòu) 圖 孩子表示法 樹的存儲(chǔ)結(jié)構(gòu) 3. 孩子兄弟表示法的結(jié)構(gòu)定義如下 ： typedef struct CSNode { ElemType data。 樹、森林與二叉樹的轉(zhuǎn)換 二叉樹轉(zhuǎn)換成森林 如果 B={root， LB， RB}是一棵二叉樹 ， 則可以按照如下規(guī)則轉(zhuǎn)換成森林 F={T1， T2， … ， Tm}。 ? 先序遍歷 若森林非空，則先序遍歷方法為： ① 訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn)。 define Null 0 typedef struct node { int data。 else { t=(bitree*)malloc(sizeof(bitree))。 } }/*inorder*/ void exchange(bitree *t) /*對(duì)二叉樹 t中所有結(jié)點(diǎn)的左右子樹進(jìn)行交換 */ { bitree *p。 root=creat()。 struct node *lchild,*rchild。 if(x==0) t=Null。 inorder(trchild)。 t=que[front]。 root=creat()。 習(xí) 題 __填空題 (5) 一棵深度為 k的滿二叉樹的結(jié)點(diǎn)總數(shù)為 ___________， 一棵深度為 k的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值為 ___________， 最大值為 ___________。 A. 二維數(shù)組和三維數(shù)組 B. 三元組和散列 C. 三元組和十字鏈表 D. 散列和十字鏈表 (3) 設(shè)二叉樹有 n個(gè)結(jié)點(diǎn) ， 則其深度為 _____。 A. 不發(fā)生變化 B. 發(fā)生變化 C. 不能確定 D. 以上都不對(duì) 習(xí) 題 __判斷題 3. 判斷題 (1) 一棵度為 2的樹就是一棵二叉樹。 ① 先序遍歷序列： EBADCFHGIKJ 中序遍歷序列： ABCDEFGHIJK ② 中序遍歷序列： ACBGEDF 后序遍歷序列： ABCDEFG (6) 分別畫出圖 。 (5) 設(shè)計(jì)一個(gè)算法 ， 求給定值 x的結(jié)點(diǎn)在二叉樹中的所有祖先 ， 設(shè)樹中值為 x的結(jié)點(diǎn)不多于一個(gè) 。 ? 在有向圖中 ， 用尖括號(hào)表示兩個(gè)頂點(diǎn)間的首尾關(guān)系 ， 有向邊也稱為弧 。 ? 3. 無(wú)向完全圖 : 任意兩頂點(diǎn)間都有邊的圖稱為無(wú)向完全圖 。 圖的相關(guān)術(shù)語(yǔ) (2) ? 7. 邊的權(quán) : 在圖的邊或弧上標(biāo)示數(shù)字 ， 表示與該邊相關(guān)的數(shù)據(jù)信息 ，這個(gè)數(shù)據(jù)信息就稱該邊的權(quán) (Weight)。 ? 12. 連通圖和連通分量 : 在無(wú)向圖中 ， 如果從一個(gè)頂點(diǎn) Vi到另一個(gè)頂點(diǎn) Vj有路徑 ， 則稱頂點(diǎn) Vi和頂點(diǎn) Vj是連通的 。 去掉生成樹中任意一條邊 ，該子圖就不連通了 。 ? 2. 網(wǎng)的鄰接矩陣 有 n個(gè)頂點(diǎn)的網(wǎng) ， 其鄰接矩陣中是邊上的權(quán)值 ， 其鄰接矩陣叫加權(quán)矩陣 。(Gn),amp。 } for(i=0。 scanf(%c,%c,amp。j++}。 // 頂點(diǎn)字段 EdgeNode ﹡ firstedge。 printf(請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù) {輸入格式為：頂點(diǎn)數(shù) ， 邊數(shù) }： \n)。 //讀入頂點(diǎn)信息 鄰接表 (4) Gadjlist[i].firstedge=NULL。 //鄰接點(diǎn)序號(hào)為 j snext=Gadjlist[i].firstedge。 //該值為 1時(shí) ， 相應(yīng)結(jié)點(diǎn)已被訪問(wèn) ， 否則未被訪問(wèn) int i。 printf(\t\t深度優(yōu)先遍歷結(jié)點(diǎn)：結(jié)點(diǎn) %c\n， Gvexs[i])； visited[i]=TRUE。 ? 廣度優(yōu)先搜索的時(shí)間復(fù)雜度為 O(n+e)。i++) if(!visited[i]) BFSM(G,i)。Q,k)。!visited[j]) { printf(“ 廣度優(yōu)先遍歷結(jié)點(diǎn)： %c\n， Gvexs[j])。 (a) 圖 G4的深度優(yōu)先生成樹 (b) 圖 G4廣度優(yōu)先生成樹 圖 生成樹 最小生成樹 ? 對(duì)加權(quán)的連通圖 ， 去掉多余的邊 ， 使圖成為樹 ， 樹的枝上的權(quán)值的和最小 ， 該樹稱為 最小生成樹 。 (5) 有向圖中的強(qiáng)連通分量定義為有向圖的 ____________。 習(xí) 題 __選擇題 (6) — 個(gè)加權(quán)的無(wú)向連通圖的最小生成樹 ________。 (4) 按圖 V6點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索序列和深度優(yōu)先搜索序列 圖 某圖的鄰接表 習(xí) 題 __問(wèn)答題 (5) 按圖 V1點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索序列和深度優(yōu)先搜索序列 。 (9) 已知某無(wú)向圖 G的鄰接矩陣如圖 。 按關(guān)鍵字排序的表或文件便于查找 。 穩(wěn)定排序與非穩(wěn)定排序 ? 排序定義中的 關(guān)鍵字 Ki可以是記錄 Ri(i=1， 2， … ， n)的主關(guān)鍵字 ， 也可以是記錄 Ri的次關(guān)鍵字 ， 甚至是若干數(shù)據(jù)項(xiàng)的組合 。 若 Ki是次關(guān)鍵字 ， 則排序的結(jié)果不惟一 ， 因?yàn)榇判虻挠涗浶蛄兄锌赡艽嬖趦蓚€(gè)或兩個(gè)以上關(guān)鍵字相等的記錄 。 ② 排序方法有許多種 ， 可以分為穩(wěn)定的或不穩(wěn)定的 。 (10)已知無(wú)向圖 G的鄰接表如圖 ， 請(qǐng)畫出其所有的連通分量 。 (7) 根據(jù)如圖 ， 回答問(wèn)題 。 “ 先進(jìn)先出 ” 的特征 (8) 無(wú)向圖的鄰接矩陣是一個(gè) _______。 C. 樹 (2) 強(qiáng)連通分量是 _______的極大連通子圖 。 Prim方法： ① 從加權(quán)圖中選取權(quán)值最小的邊 ， 與該邊相關(guān)聯(lián)的頂點(diǎn)被選擇； ② 從與被選擇的頂點(diǎn)相關(guān)聯(lián)的未被選擇的邊中選取權(quán)值最小的邊 ， 若該邊使已經(jīng)選 擇的頂點(diǎn)和邊構(gòu)成圈 ， 則去掉該邊； ③ 重復(fù)步驟 ② ， 直到?jīng)]有未被選擇也未被去掉的邊 ， 剩下的邊和圖的全部頂點(diǎn)構(gòu)成最小生成樹 。 EnQueue(amp。Q)) { i=OutQueue(amp。 CirQueue Q。 int I。jGn。iGn。 } } 圖 的 遍 歷 ?圖的遍歷 是指從圖中的某一頂點(diǎn)出發(fā)，對(duì)圖中的所有頂點(diǎn)訪問(wèn)一次，且僅訪問(wèn)一次。 for(k=0； kGe。(Gn),amp。 typedef VertexNode