【正文】 圖15 系統(tǒng)演示2，此時會退出當前演示界面，即退出對當前線性表的操作，并顯示要求用戶選擇對哪一個線性表進行操作。圖18 初始化線性表的測試結(jié)果，銷毀線性表，測試結(jié)果如圖19所示。圖112 求線性表長度的測試結(jié)果，查找第三個數(shù)據(jù)元素的數(shù)值，測試結(jié)果如圖113所示。圖116 刪除線性表中的數(shù)據(jù)元素測試結(jié)果，測試結(jié)果如圖117所示。還發(fā)現(xiàn)了自己的薄弱之處，就是在文件的處理時存在許多紕漏，導致文件讀取不成功。e”使得在函數(shù)中調(diào)用主函數(shù)中的值“e”時可以同時更改其值，如在GetElem函數(shù) 中調(diào)用了“e”的值然后在主函數(shù)中輸出，如果要更改其值的話就必須要用“amp。 二叉樹的基本概念二叉樹是一種樹型結(jié)構(gòu)，即n個結(jié)點的有限集，它的特點是每個結(jié)點至多只有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。}依據(jù)最小最小完備性和常用性相結(jié)合的原則，以函數(shù)形式定義了二叉樹的初始化、銷毀二叉樹、創(chuàng)建二叉樹、清空二叉樹、判定空二叉樹和求二叉樹深度等20種基本運算，具體運算功能定義如下：⑴初始化二叉樹：函數(shù)名稱是InitBiTree(T)；初始條件是二叉樹T不存在；操作結(jié)果是構(gòu)造空二叉樹T。⑸判定空二叉樹：函數(shù)名稱是BiTreeEmpty(T)；初始條件是二叉樹T存在；操作結(jié)果是若T為空二叉樹則返回TRUE，否則返回FALSE。⑼結(jié)點賦值：函數(shù)名稱是Assign(T,amp。若e無左孩子，則返回NULL。若e是T的左孩子或者無左兄弟，則返回NULL。⒃刪除子樹：函數(shù)名稱是DeleteChild()；初始條件是二叉樹T存在，p指向T中的某個結(jié)點，LR為0或1。⒆后序遍歷：函數(shù)名稱是PostOrderTraverse(T,Visit))；初始條件是二叉樹T存在，Visit是對結(jié)點操作的應(yīng)用函數(shù)；操作結(jié)果是后序遍歷t，對每個結(jié)點調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。附錄A中給出了簡單菜單的框架。//左右孩子指針 int index。進入while循環(huán)后，系統(tǒng)首先顯示功能菜單，然后提示用戶輸入選擇（020），其中120對應(yīng)二叉樹的一個基本操作，分別對應(yīng)一個函數(shù)，通過switch語句將用戶輸入的序號對應(yīng)到相應(yīng)的函數(shù)功能，執(zhí)行完該語句后break跳出switch語句，執(zhí)行while循環(huán)，直到用戶輸入0選擇退出，退出系統(tǒng)。經(jīng)分析，該算法的時間復(fù)雜度為O(n)。 清空二叉樹算法思想：將二叉樹的清空過程寫成函數(shù)，函數(shù)的參數(shù)同上，將根結(jié)點的左右孩子指針置為空，此時其左右子樹的存儲空間并未釋放掉。 求二叉樹的深度算法思想：將求二叉樹的深度寫成函數(shù)，采取遞歸的方式求二叉樹的深度，如果根結(jié)點的左右孩子都不存在，則返回樹的深度為1，否則的話返回根結(jié)點左右子樹的深度的最大加上一。 獲得結(jié)點的算法思想是：將獲得關(guān)鍵字結(jié)點寫成函數(shù)，函數(shù)的參數(shù)是二叉樹的頭指針以及主函數(shù)中輸入的關(guān)鍵字，通過遞歸先序遍歷二叉樹，即先比較根結(jié)點的關(guān)鍵字與給定是否一致，若一致，返回該結(jié)點的INDEX值，否則繼續(xù)分別遞歸遍歷其左子樹和右子樹。經(jīng)分析，該算法的時間復(fù)雜度為O(n)。如果不一致，繼續(xù)遞歸調(diào)用原函數(shù)，傳入的參數(shù)為二叉樹根結(jié)點的左子樹的根結(jié)點指針，如果函數(shù)的返回值非空，則返回該值，否則繼續(xù)調(diào)用原函數(shù)，傳入的參數(shù)是二叉樹根結(jié)點的右子樹的根結(jié)點指針，如果函數(shù)的返回值為非空，則返回該值，否則返回NULL。1 獲得左孩子結(jié)點的算法思想是：將獲得左孩子結(jié)點寫成函數(shù)，函數(shù)的參數(shù)是二叉樹的頭指針。經(jīng)分析，該算法的時間復(fù)雜度為O(n)。經(jīng)分析，該算法的時間復(fù)雜度為O(n)。1 非遞歸前序遍歷的算法思想是：將非遞歸前序遍歷寫成函數(shù)，函數(shù)的形參是二叉樹的頭指針，仿照遞歸過程堆棧的使用，首先將根結(jié)點的值壓入堆棧，執(zhí)行循環(huán)體，堆棧非空，彈出根結(jié)點并執(zhí)行訪問操作，將其右子樹根結(jié)點指針壓入堆棧，再將其左子樹根結(jié)點指針壓入堆棧，執(zhí)行循環(huán)。 層序遍歷的算法思想是：將層序遍歷寫成函數(shù)，函數(shù)的形參是二叉樹的頭指針，借助隊列，使根結(jié)點進入隊列，根結(jié)點出隊列，執(zhí)行訪問操作，此時將根結(jié)點的左右子樹根結(jié)點依次進入隊列，即隊列中的某個元素出隊列時將其左右子樹根結(jié)點放進隊列，循環(huán)即可一層一層的訪問二叉樹。typedef char TElemType。圖23 演示系統(tǒng)操作圖2，演示系統(tǒng)結(jié)束并退出。執(zhí)行功能17，先序遍歷二叉樹，并執(zhí)行PRINT操作，測試結(jié)果如圖27所示。圖210 層序遍歷二叉樹的測試結(jié)果上述測試與預(yù)期的遍歷結(jié)果是一致的，說明生成二叉樹的結(jié)構(gòu)正確性，即生成了如圖24所示的二叉樹。圖213 求二叉樹根結(jié)點的測試結(jié)果，求關(guān)鍵字為D的結(jié)點的值，測試結(jié)果如圖214所示。圖217 查找左孩子的測試結(jié)果2，查找關(guān)鍵字為I的結(jié)點的雙親結(jié)點，測試結(jié)果如圖218所示。圖221 插入子樹的測試結(jié)果插入子樹后，先序遍歷得到的序列為：ABDEHICFGJMNK,層序遍歷得到的序列應(yīng)該為：ABCDEFGHIJMNK，中序遍歷得到的序列為：DBHEIAFCGNKMJ。圖225 刪除子樹的測試結(jié)果未驗證結(jié)果的正確性，若對其先序遍歷得到的序列應(yīng)該為：ABDEHCFGJMNK，層序遍歷得到的序列應(yīng)該為：ABCDEFGHJMNK，中序遍歷得到的結(jié)果應(yīng)該為：DBHEAFCGNKMJ圖226 先序遍歷的測試結(jié)果圖227 中序遍歷的測試結(jié)果圖228 層序遍歷的測試結(jié)果上面的測試結(jié)果與預(yù)期相一致，說明刪除子樹后結(jié)構(gòu)的正確性，函數(shù)功能執(zhí)行正確。 掌握了二叉樹的基本操作。參考文獻黑體小2號加粗居中，[1] 嚴蔚敏等. 數(shù)據(jù)結(jié)構(gòu)(C語言版). 清華大學出版社[2] Larry Nyhoff. ADTs, Data Structures, and Problem Solving with C++. int length。L) { = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))。 return OK。 = 0。}status ClearList(SqList amp。 }}int ListLength(SqList amp。 else return FALSE。 return OK。 j++) if ([j] == e) return j + 1。 j = LocateElem(L, cur)。 return TRUE。 j = LocateElem(L, cur)。 return TRUE。 if (i1 || i + 1) return ERROR。 +=LISTINCREMENT。([ 1])。 ++。e) { if (i1 || i) return ERROR。([i 1])。 p++) *p = *(p + 1)。 printf(\nall elements \n)。 printf(\n end \n)。 if ((fp = fopen(filename, wb)) == NULL)//打開或創(chuàng)建文本文件時只寫，對已經(jīng)存在的文件清除原有內(nèi)容 { printf(File open error!\n )。 i++) { if((fwrite(amp。}status DataLoading(SqList amp。 printf(請輸入需加載的文件名：\n)。 } while (fread(amp。 return OK。 scanf(%d, amp。 int e。 int cur。 printf( Menu for Linear Table On Sequence Structure \n)。 printf( 3. ClearList 10. ListInsert\n)。 printf( 7. LocateElem 14. DataLoading\n)。 scanf(%d, amp。 getchar()。 ? ? if (DestroyList(L[t]) == OK) printf(線性表刪除成功！\n)。 break。 getchar()。 ? ? if (ListEmpty(L[t]) == TRUE) printf(線性表為空表！\n)。 break。 getchar()。i)。 getchar()。 scanf(%d, amp。 if (i == FALSE) printf(查找失敗！\n)。 break。 getchar()。 getchar()。cur)。 getchar()。 scanf(%d %d, amp。 else printf(插入成功,表的長度為%d\n, L[t].length)。 case 11: printf(請輸入需刪除的數(shù)據(jù)元素在線性表中的位序！\n)。 if (ListDelete(L[t], i, e) == ERROR) printf(刪除失??！\n)。 break。 break。 if (SaveData(L[t], filename) == OK) printf(文件保存成功!\n)。 break。 getchar()。 }//end of while } printf(歡迎下次再使用本系統(tǒng)！\n)。 struct BiTNode *lchild, *rchild。typedef struct{ QElemType *base。//輔助函數(shù)，返回a、b中大的數(shù)值int MAX(int a, int b) { if (a = b) return a。}status InitBiTree(BiTree amp。T) { if (T) { if (Tlchild) DestroyBiTree(Tlchild)。 } return OK。字符表示空樹， //采用遞歸調(diào)用的方式構(gòu)造二叉樹鏈表表示的二叉樹為T char ch。 getchar()。 else { if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW)。Tindex)。 } return OK。 } return OK。//若T為NULL，即空二叉樹深度返回為0 else { if ((Tlchild == NULL) amp。 }}//以下三個函數(shù)Pre_order,Mid_order,Post_order為遞歸方式遍歷二叉樹status Pre_order(BiTree T, status (*visit)(TElemType e)) { if (T) { if (visit(Tdata)) if (Pre_order(Tlchild, visit)) if (Pre_order(Trchild, visit)) return OK。 return ERROR。 } else return OK。 while (top) { p = st[top]。 //將左子樹的根結(jié)點存入棧中 } return OK。 st[top++] = T。 //對根結(jié)點進行操作 T = Trchild。 int flag, top = 0。 }//循環(huán)結(jié)束時表示以棧頂元素為指向的 //根節(jié)點的二叉樹的左子樹遍歷完畢 pre = NULL。flag) { T = st[top 1]。 } else { T = Trchild。 else return Tdata。 //置空棧 st[top++] = T。 if(plchild!=NULL) st[top++] = plchild。 int top = 0。 return OK。}BiTNode* Parent(BiTree T, char e) { //若e是T的非根結(jié)點，返回它的雙親結(jié)點指針 //否則返回NULL BiTree T1。amp。 T1 = Parent(Trchild, e)。 if (T) { if (Trchild!=NULLamp。 //遞歸調(diào)用對左子樹進行操作 if (T1 != NULL) return T1。}BiTNode* RightSibling(BiTree T, char e) { //若e無右孩子，返回NULL BiTree T1 = NULL。 T1 = LeftSibling(Tlchild, e)。 } return NULL。 if (p != NULL) return p。}BiTNode* RightChild(BiTree T, char e) { BiTree p。 p = RightChild(Trchild, e)。 return ERROR。 plchild =