【正文】 100) As QelemType Dim front As Integer Dim rear As Integer End Structure 2. 隊的循環(huán)隊列實現(xiàn) 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 隊列 2. 隊的循環(huán)隊列實現(xiàn) 0 1 2 3 5 100 4 … 循環(huán)隊列的初始化： Sub InitQueue(ByRef Q As Queue) = 0 = 0 End Sub = 0 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 隊列 2. 隊的循環(huán)隊列實現(xiàn) 0 1 2 3 … 5 100 4 Q3 Q2 Q1 item Q4 將新元素 item插入到循環(huán)隊列 Q中 If (( + 1) Mod 101) = Then Call QUEUE_FULL() 39。隊列已滿 ,溢出 Else () = item = ( + 1) Mod 101 End If If (( + 1) Mod 101) = Then () = item = ( + 1) Mod 101 Else Q4 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 隊列 2. 隊的循環(huán)隊列實現(xiàn) 0 1 2 3 … 5 100 4 Q4 Q3 Q2 Q1 item Q5 Q5 將新元素 item插入到循環(huán)隊列 Q中 If (( + 1) Mod 101) = Then Call QUEUE_FULL() 39。隊列已滿 ,溢出 Else () = item = ( + 1) Mod 101 End If If (( + 1) Mod 101) = Then () = item = ( + 1) Mod 101 Else 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 隊列 2. 隊的循環(huán)隊列實現(xiàn) item 0 1 2 3 … 5 100 4 Q4 Q3 Q2 Q1 Q5 Q1 出隊操作 If = Then Call QUEUE_Empty() Else item = () = ( + 1) Mod 101 End If If = Then item = () = ( + 1) Mod 101 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 隊列 2. 隊的循環(huán)隊列實現(xiàn) item 0 1 2 3 … 5 100 4 Q4 Q3 Q2 Q5 出隊操作 If = Then Call QUEUE_Empty() Else item = () = ( + 1) Mod 101 End If Q2 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 樹和二叉樹 樹 1. 樹的定義： 樹是 n≥0結(jié)點的有窮集合 T。當(dāng) n＝ 0時稱之為空樹。在任何一棵非空樹 T中，必有一個特定的結(jié)點，稱之為 T的根結(jié)點；其余結(jié)點被分成m≥0個不相交的子集 T T … 、 Tm，其中每一個子集 Ti (1≤i≤m)本身又是一種樹，稱之為根的子樹。 A結(jié)點為樹的根 ， 它有三棵子樹 ， 三棵子樹的根 分 別 為 B 、 C 、 D A C B D N J H I K L G M F E 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 2．樹的存儲結(jié)構(gòu) 1）帶雙親的孩子鏈表表示法 這種存儲結(jié)構(gòu)是指，把每個結(jié)點的多個孩子視為一個線性表，且以單鏈表作為存儲結(jié)構(gòu)。 39。帶雙親的孩子鏈表存儲表示 Structure ChildNode Dim child As Integer Dim nextchild As Integer End Structure Structure Node Dim parant As Integer Dim data As TelemType Dim fristchild As Integer End Structure Structure Ctree Dim nodes() As Node Dim n As Integer Dim root As Integer End Structure 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 帶雙親的樹的孩子鏈表表示 1 2 3 ^ 4 5 ^ 6 ^ 12 13 ^ 7 8 9 ^ 10 11 ^ 1 A 0 B 0 C 0 D 1 E ^ 1 F 2 G ^ 3 H ^ 3 I ^ 3 J 5 K ^ 5 L ^ 9 M ^ 9 N ^ 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 2．樹的存儲結(jié)構(gòu) 2）孩子兄弟鏈表表示法 孩子兄弟表示法又稱為二叉樹表示方法。即鏈表中結(jié)點的兩個指針域分別指向該結(jié)點的第 1個孩子結(jié)點和下一個兄弟結(jié)點。 A ^ B D ^ J ^ C ^ G ^ F ^ ^ E ^ H ^ I ^ K ^ L ^ ^ M ^ N ^ T 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 2．樹的存儲結(jié)構(gòu) 39。樹的孩子兄弟存儲表示 Structure CSNode 39。孩子兄弟結(jié)點 Dim data As TelemType Dim firstchild As Integer Dim next_sibling As Integer End Structure Structure CSTree Dim root As Integer 39。樹的根結(jié)點 Dim n As Integer 39。樹的結(jié)點數(shù) End Structure 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 樹和二叉樹 二叉樹 1．二叉樹的定義 二叉樹是 n≥0個結(jié)點的有限集合。在任意一棵非空二叉樹中，每個結(jié)點至多只有兩棵子樹，并且二叉樹的子樹有左右之分，其次序不能任意顛倒。 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 樹和二叉樹 二叉樹 2．二叉樹的存儲結(jié)構(gòu) 一般情況下，利用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示二叉樹。 Lchild data rchild A B C E D F A ^ B ^ C ^ D ^ ^ E ^ F ^ T 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 樹和二叉樹 二叉樹 3．二叉樹的遍歷 二叉樹的遍歷是指，按一定的次序巡訪該樹中每個結(jié)點，使得每個結(jié)點被訪問且僅被訪問一次?？梢?，遍歷的過程就使得原來具有層次特性的各結(jié)點變成了一個結(jié)點的線性序列。 二叉鏈樹由根結(jié)點、左子樹、右子樹三個基本單元組成，假如以 L、 D、 R分別表示遍歷左子樹、訪問根結(jié)點和遍歷右子樹，且限定先左后右，則可有 DLR、 LDR、 LRD三種遍歷二叉樹的方法，并且分別稱之為先（根）序遍歷，中（根）序遍歷和后（根）序遍歷。 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 先序遍歷二叉樹的遞歸操作為： If Tree 0 Then Visit((Tree).data) Preorder((Tree).lchild,Space) Preorder((Tree).rchild,Space) Else Return End If A ^ B ^ C ^ ^ D ^ Tree 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 Preorder(參數(shù) 1,參數(shù) 2) A ^ B ^ C ^ ^ D ^ Tree 參數(shù) 1： (Tree).lchild 參數(shù) 2： Space 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 Preorder(參數(shù) 1,參數(shù) 2) 訪問 A 先序遍歷序列： A Preorder(參數(shù) 1,參數(shù) 2) A ^ B ^ C ^ ^ D ^ Tree 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 Preorder(參數(shù) 1,參數(shù) 2) 先序遍歷序列： A Preorder(參數(shù) 1,參數(shù) 2) 訪問 B Preorder(參數(shù) 1,參數(shù) 2) B A ^ B ^ C ^ ^ D ^ Tree 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 Preorder(參數(shù) 1,參數(shù) 2) 先序遍歷序列： A Preorder(參數(shù) 1,參數(shù) 2) Preorder(參數(shù) 1,參數(shù) 2) B 返回 Preorder(參數(shù) 1,參數(shù) 2) A ^ B ^ C ^ ^ D ^ Tree 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 Preorder(參數(shù) 1,參數(shù) 2) 先序遍歷序列： A Preorder(參數(shù) 1,參數(shù) 2) Preorder(參數(shù) 1,參數(shù) 2) B Preorder(參數(shù) 1,參數(shù) 2) 返回 返回 Preorder(參數(shù) 1,參數(shù) 2) A ^ B ^ C ^ ^ D ^ Tree 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 Preorder(參數(shù) 1,參數(shù) 2) 先序遍歷序列： A Preorder(參數(shù) 1,參數(shù) 2) Preorder(參數(shù) 1,參數(shù) 2) B Preorder(參數(shù) 1,參數(shù) 2) Preorder(參數(shù) 1,參數(shù) 2) 訪問 C C Preorder(參數(shù) 1,參數(shù) 2) A ^ B ^ C ^ ^ D ^ Tree 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 Preorder(參數(shù) 1,參數(shù) 2) 先序遍歷序列： A Preorder(參數(shù) 1,參數(shù) 2) Preorder(參數(shù) 1,參數(shù) 2) B Preorder(參數(shù) 1,參數(shù) 2) Preorder(參數(shù) 1,參數(shù) 2) C Preorder(參數(shù) 1,參數(shù) 2) 訪問 D D Preorder(參數(shù) 1,參數(shù) 2) A ^ B ^ C ^ ^ D ^ Tree 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 Preorder(參數(shù) 1,參數(shù) 2) 先序遍歷序列： A Preorder(參數(shù) 1,參數(shù) 2) Preorder(參數(shù) 1,參數(shù) 2) B Preorder(參數(shù) 1,參數(shù) 2) Preorder(參數(shù) 1,參數(shù) 2) C Preorder(參數(shù) 1,參數(shù) 2) D Preorder(參數(shù) 1,參數(shù) 2) 返回 Preorder(參數(shù) 1,參數(shù) 2) A ^ B ^ C ^ ^ D ^ Tree 鄭 州 航 院 計 算 機 科 學(xué) 與 應(yīng) 用 系 Preorder(參數(shù) 1,參數(shù) 2) 先序遍歷序列： A Preorder(參數(shù) 1,參數(shù) 2) Preorder(參數(shù) 1,參數(shù) 2) B Preorder(參數(shù) 1,參數(shù) 2) Preorder(參數(shù) 1,參數(shù) 2) C Preorder(參數(shù) 1,參數(shù) 2) D Preorder(參數(shù) 1,參數(shù) 2) Preord