【正文】 接 以 Vi為弧頭的鄰接點(diǎn)鏈表，稱該表為逆鄰接表。 （ 3）還要在每個(gè)頂點(diǎn)的頭結(jié)點(diǎn)中存儲指向其鄰接表首元結(jié)點(diǎn)的指針。 （ 1）頭結(jié)點(diǎn)存儲一個(gè)頂點(diǎn)的詳細(xì)信息，為了便于管理，所有頭結(jié)點(diǎn)都存放在一個(gè)數(shù)組中。 ??????其它或當(dāng)]][[ E)v,(v Ev,vj)W ( i ,=ji A jiji對于含權(quán)的網(wǎng)絡(luò)而言，其鄰接矩陣可定義如下： ??? ???o t h e r w i s e0,) Ej)( i ,o r Eji,( if1,]j][iΑ[下一頁 上一頁 停止放映 [第 50頁 /91] 0 1 3 2 5 2 8 1 3 0 1 2 3 4 1 0 2 3 4 (a)無向圖 (b)有向圖 (c)網(wǎng)絡(luò) ???????????????0010100011100110110111110A0 1 3 2 4 ???????????????0010010010000000010101000A?????????????????????? 38 125A0 1 3 2 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 0 1 3 2 (a)無向圖鄰接矩陣 (b)有向圖鄰接矩陣 (c)網(wǎng)絡(luò)鄰接矩陣 鄰接矩陣舉例 下一頁 上一頁 停止放映 [第 51頁 /91] 2．鄰接表 鄰接表存儲形式是一種鏈表與數(shù)組結(jié)合的存儲形式。 MAX_NUM表示最多可存的頂點(diǎn)數(shù) 。 其中 :ArcType是頂點(diǎn)關(guān)系的數(shù)據(jù)類型 。 //圖實(shí)際頂點(diǎn)數(shù)和弧 (邊 )數(shù) int kind。 //頂點(diǎn)信息數(shù)組 ArcType Matrix[MAX_NUM][MAX_NUM]。無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣可能是不對稱的。此二維數(shù)組又稱 鄰接矩陣 。 V1 V2 V3 V4 G5 2 3 5 7 下一頁 上一頁 停止放映 [第 47頁 /91] 圖的存儲方式 1．鄰接矩陣 利用數(shù)組實(shí)現(xiàn)的。 網(wǎng) （ Network） 帶權(quán)的圖稱為網(wǎng) 。 （子圖包含所有頂點(diǎn)，但不一定包含所有邊） 下一頁 上一頁 停止放映 [第 46頁 /91] 網(wǎng)、權(quán) 權(quán) （ Weight） 若圖的邊或弧帶有與之相關(guān)的數(shù) ， 稱此數(shù)為該邊或弧的權(quán) 。 G的生成樹不是唯一的 。 G =（ V， E） ， G1=（ V1， E1） （圖的部分頂點(diǎn)和部分邊組成的圖） 生成子圖 、 生成樹 設(shè) G是一個(gè)連通圖 ， G中任一包含 G的所有頂點(diǎn)的子圖稱為生成子圖 。 如圖 G4所示 。 連通分量（ Connected Component） 無向圖中的極大連通子圖稱為連通 分量 。 1 3 2 4 G2 o o o o v1 v2 v3 v4 G1 下一頁 上一頁 停止放映 [第 44頁 /91] 連通圖、強(qiáng)連通圖、連通分量 連通圖（ Connected Graph） 在無向圖中，若每一對頂點(diǎn)間都有路徑，稱此圖是連通圖。 長度 （ Length） 路徑的長度是該路徑上邊或弧的數(shù)目 。 路徑可能是不唯一的 。 例如 ， G2中頂點(diǎn) 1的度 =2+1=3。 例如 G2中頂點(diǎn) 1的出度為 2。 例如 G2中頂點(diǎn) 1的入度為1。 例如 ， G1中 V2的度為 3， V4的度為 1。有向圖中 ， 若弧 〈 Ｖ x,Ｖ y〉? E， 則Ｖ y是Ｖ x的鄰接點(diǎn) ， 反之 ， 不是 。如圖 G G2中的Ｖ Ｖ 2， 1， 2。 弧尾 （ Tail） 弧的起始點(diǎn) （ Initial Node） 稱為弧尾（ 方向后方 ） 。 弧是有序的 ，〈 Vx， Vy〉 表示從 Vx到 Vy。 弧 （ Arc） 若頂點(diǎn)間的邊是有方向性 （ 有序 ） 的 ， 則稱該偶對為弧 。 記為： （ Vx， Vy） 。 例 G2=（ V， E） V={ 1， 2， 3， 4} E={〈 1， 2〉 ,〈 1， 3〉 ， 〈 3， 4〉 ,〈 4， 1〉 } 無向圖 （ Undigraph） 圖 G中頂點(diǎn)的偶對若是無向的 ， 稱為無向圖 ， 其偶對用 （ vx， vy） 表示 ， 如圖 G1所示 。 如圖G2所示 。 一般記作 : Graph＝ ( V, E ) 其中 :V是頂點(diǎn)的有限非空集合； E是頂點(diǎn)之間關(guān)系的有限集合 。 在該結(jié)構(gòu)中 ， 數(shù)據(jù)元素一般稱為頂點(diǎn) 。 － ＋ ／ － e f ＊b － c d a 下一頁 上一頁 停止放映 [第 36頁 /91] 表達(dá)式樹應(yīng)用舉例 （ 1） a b c d 入棧 d c b a （ 1） （ 2） c d b a （ 3） b*（ cd） a a+b*（ cd） （ 4） （ 5） a+b*（ cd） f e （ 6） e/f a+b*（ cd） （ 7） a+b*（ cd） e/f （ 2） 遇 ‘ ’， c d 出棧 ， 運(yùn)算后再壓棧； （ 3） 遇 ‘ *’ ， （ c d） 和 b 出棧 ， 運(yùn)算后再壓棧； （ 4） 遇 ‘ +’， b*（ cd） 和 a出棧 ， 運(yùn)算后再壓棧； （ 5） e f 入棧 （ 6） 遇 ‘ /’， f e 出棧 ， 運(yùn)算后再壓棧； （ 7） 遇 ‘ ’， a+b*（ cd） 和 e/f出棧 ， 運(yùn)算后再壓棧 。 表達(dá)式處理一般采用后序法 ， 也稱 ? 逆波蘭 ? 法 。 // 訪問根節(jié)點(diǎn) 下一頁 上一頁 停止放映 [第 35頁 /91] 表達(dá)式樹及應(yīng)用 在計(jì)算機(jī)中對表達(dá)式進(jìn)行分析和計(jì)算是一項(xiàng)重要的任務(wù) 。 // 遍歷左子樹 PostOrder( trightChild )。 // 遍歷右子樹 下一頁 上一頁 停止放映 [第 34頁 /91] （ 3） 后序遍歷 對一顆非空二叉樹進(jìn)行中序遍歷時(shí) ， 首先按 后序遍歷 方式訪問左子樹 ， 然后 按后序遍歷 方式訪問右子樹 ， 最后訪問根結(jié)點(diǎn) 。 // 遍歷左子樹 Visit( t )。 //遍歷右子樹 } } A B C D E F 前序遍歷二叉樹的序列為： A B C D E F 下一頁 上一頁 停止放映 [第 32頁 /91] 二叉樹遍歷算法（遞歸、前序法驗(yàn)證） 打印 A – 取 A?.左子 (B) – 打印 B 取 B?.左子 (C) 打印 C – 取 C?.左子 (空 ) – 取 C?.右子 (空 ) 取 B?.右子 (D) 打印 D – 取 D?.左子 (E) – 打印 E 取 E?.左子 (空 ) 取 E?.右子 (空 ) – 取 D?.右子 (F) – 打印 F 取 F?.左子 (空 ) 取 F?.右子 (空 ) – 取 A?.右子 (空 ) 結(jié)束 A B C D E F A TOP A TOP B A TOP B A TOP B C A TOP D A TOP D E A TOP D A TOP F A TOP 下一頁 上一頁 停止放映 [第 33頁 /91] （ 2） 中序遍歷 對一顆非空二叉樹進(jìn)行中序遍歷時(shí) ， 首先按中序遍歷方式訪問左子樹 ， 然后訪問根結(jié)點(diǎn) ，最后按中序遍歷方式訪問右子樹 。 //訪問根結(jié)點(diǎn) PreOrder( tleftChild )。 即： 根 左子 右子 a b c 遍歷 序列 b a c 下一頁 上一頁 停止放映 [第 29頁 /91] 后序法（ PostOrder） ? 方法描述： – 從左子結(jié)點(diǎn) b開始訪問 ， – 接著訪問右子結(jié)點(diǎn) c， – 最后訪問根結(jié)點(diǎn) a。 ? 遍歷的方法很多 ， 常用的有： – 前序法 （ PreOrder） – 中序法 （ InOrder） – 后序法 （ PostOrder） 下一頁 上一頁 停止放映 [第 27頁 /91] 前序法（ PreOrder） 方法描述： – 從根結(jié)點(diǎn) a開始訪問 ， – 接著訪問左子結(jié)點(diǎn) b， – 最后訪問右子結(jié)點(diǎn) c。這和單鏈表必須保留頭指針的道理一樣。從根結(jié)點(diǎn)出發(fā)，可以訪問二叉樹的任何結(jié)點(diǎn)。 對于葉結(jié)點(diǎn)或一個(gè)新生成的結(jié)點(diǎn)而言 ， 其左孩子和右孩子指針都為空值 。 struct BinTreeNode *root。 struct BinTreeNode *leftChild, *rightChild。右子存放在第 2*i+1的位置（ 若 2i+1＜ n ）。 二叉樹的性質(zhì)六 下一頁 上一頁 停止放映 [第 23頁 /91] 驗(yàn)證性質(zhì)六 1 4 3 2 5 6 1 2 3 4 5 6 1 2 3 4 5 6 第 i個(gè)結(jié)點(diǎn)就存放在第 i個(gè)位置上； 第 i個(gè)結(jié)點(diǎn)（ i1)的父結(jié)點(diǎn)就存放在第 i/2個(gè)位置 。 否則 ， 編號為 2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn) 。否則 ， 編號為 [i/2]的結(jié)點(diǎn)為其父結(jié)點(diǎn)； ② 若 2in， 則該結(jié)點(diǎn)無左孩子 。 二叉樹的性質(zhì)五 證明： 假設(shè)二叉樹的深度為 h， 則必有 2h11n≤2h1， 于是有 2h1n+1≤2h， 也就是 2h1≤n2h， 從而得到 h1≤log2(n)h， 于是 h=[log2(n)]+1。因此二叉樹的分支數(shù)加 1就是結(jié)點(diǎn)總數(shù)。 二叉樹的性質(zhì)四 證明：設(shè)二叉樹含有 n1個(gè)度為 1的結(jié)點(diǎn)，則二叉樹結(jié)點(diǎn)總數(shù)顯然為： n0 + n1 + n2 （ 22） 再看樹的分支數(shù)， n2個(gè)度為 2的結(jié)點(diǎn)必然有 2n2個(gè)分支，n1個(gè)度為 1的結(jié)點(diǎn)必然有 n1個(gè)分支。 在所有子結(jié)