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