【正文】 plchild = c。 p = RightChild(Trchild, e)。 if (p != NULL) return p。 T1 = LeftSibling(Tlchild, e)。 //遞歸調(diào)用對(duì)左子樹進(jìn)行操作 if (T1 != NULL) return T1。 T1 = Parent(Trchild, e)。}BiTNode* Parent(BiTree T, char e) { //若e是T的非根結(jié)點(diǎn)，返回它的雙親結(jié)點(diǎn)指針 //否則返回NULL BiTree T1。 int top = 0。 //置空棧 st[top++] = T。 } else { T = Trchild。 }//循環(huán)結(jié)束時(shí)表示以棧頂元素為指向的 //根節(jié)點(diǎn)的二叉樹的左子樹遍歷完畢 pre = NULL。 //對(duì)根結(jié)點(diǎn)進(jìn)行操作 T = Trchild。 //將左子樹的根結(jié)點(diǎn)存入棧中 } return OK。 } else return OK。 }}//以下三個(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 OK。Tindex)。 getchar()。 } return OK。}status InitBiTree(BiTree amp。typedef struct{ QElemType *base。 }//end of while } printf(歡迎下次再使用本系統(tǒng)！\n)。 break。 break。 if (ListDelete(L[t], i, e) == ERROR) printf(刪除失??！\n)。 else printf(插入成功,表的長(zhǎng)度為%d\n, L[t].length)。 getchar()。 getchar()。 break。 scanf(%d, amp。i)。 break。 getchar()。 ? ? if (DestroyList(L[t]) == OK) printf(線性表刪除成功！\n)。 scanf(%d, amp。 printf( 3. ClearList 10. ListInsert\n)。 int cur。 scanf(%d, amp。 } while (fread(amp。}status DataLoading(SqList amp。 if ((fp = fopen(filename, wb)) == NULL)//打開或創(chuàng)建文本文件時(shí)只寫，對(duì)已經(jīng)存在的文件清除原有內(nèi)容 { printf(File open error!\n )。 printf(\nall elements \n)。([i 1])。 ++。 +=LISTINCREMENT。 return TRUE。 return TRUE。 j++) if ([j] == e) return j + 1。 else return FALSE。}status ClearList(SqList amp。 return OK。 int length。 掌握了二叉樹的基本操作。圖221 插入子樹的測(cè)試結(jié)果插入子樹后，先序遍歷得到的序列為：ABDEHICFGJMNK,層序遍歷得到的序列應(yīng)該為：ABCDEFGHIJMNK，中序遍歷得到的序列為：DBHEIAFCGNKMJ。圖213 求二叉樹根結(jié)點(diǎn)的測(cè)試結(jié)果，求關(guān)鍵字為D的結(jié)點(diǎn)的值，測(cè)試結(jié)果如圖214所示。執(zhí)行功能17，先序遍歷二叉樹，并執(zhí)行PRINT操作，測(cè)試結(jié)果如圖27所示。typedef char TElemType。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)。經(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。 獲得結(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ù)分別遞歸遍歷其左子樹和右子樹。 清空二叉樹算法思想：將二叉樹的清空過(guò)程寫成函數(shù)，函數(shù)的參數(shù)同上，將根結(jié)點(diǎn)的左右孩子指針置為空，此時(shí)其左右子樹的存儲(chǔ)空間并未釋放掉。進(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)。附錄A中給出了簡(jiǎn)單菜單的框架。⒃刪除子樹：函數(shù)名稱是DeleteChild()；初始條件是二叉樹T存在，p指向T中的某個(gè)結(jié)點(diǎn)，LR為0或1。若e無(wú)左孩子，則返回NULL。⑸判定空二叉樹：函數(shù)名稱是BiTreeEmpty(T)；初始條件是二叉樹T存在；操作結(jié)果是若T為空二叉樹則返回TRUE，否則返回FALSE。 二叉樹的基本概念二叉樹是一種樹型結(jié)構(gòu)，即n個(gè)結(jié)點(diǎn)的有限集，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。還發(fā)現(xiàn)了自己的薄弱之處，就是在文件的處理時(shí)存在許多紕漏，導(dǎo)致文件讀取不成功。圖112 求線性表長(zhǎng)度的測(cè)試結(jié)果，查找第三個(gè)數(shù)據(jù)元素的數(shù)值，測(cè)試結(jié)果如圖113所示。圖15 系統(tǒng)演示2，此時(shí)會(huì)退出當(dāng)前演示界面，即退出對(duì)當(dāng)前線性表的操作，并顯示要求用戶選擇對(duì)哪一個(gè)線性表進(jìn)行操作。11. 遍歷線性表算法思想：將遍歷線性表寫成一個(gè)函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)類型變量，直接用一個(gè)循環(huán)來(lái)對(duì)線性表中的每一個(gè)元素進(jìn)行操作。首先判斷是否為最后一個(gè)元素，如果不是則直接返回其后一個(gè)元素，否則的話返回FALSE，同樣該算法需要調(diào)用獲得元素的函數(shù)來(lái)確定該特定元素在線性表中的次序。5. 獲得元素的算法思想：將獲得線性表元素寫成函數(shù)，其中函數(shù)的參數(shù)是結(jié)構(gòu)型變量L以及數(shù)據(jù)元素的序號(hào)i，由于采取的是線性存儲(chǔ)結(jié)構(gòu)，[i1]來(lái)獲取元素，當(dāng)然，在這之前需要判斷合法性。經(jīng)分析，算法的時(shí)間復(fù)雜度為O(1)。 //定義整型指針，為存儲(chǔ)空間基址 int length。 演示系統(tǒng)與數(shù)據(jù)文件要求構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)。⑸求表長(zhǎng)：函數(shù)名稱是ListLength(L)；初始條件是線性表已存在；操作結(jié)果是返回L中數(shù)據(jù)元素的個(gè)數(shù)。 線性表的基本概念線性表是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)，即n個(gè)數(shù)據(jù)元素的有限序列。線性表中元素的個(gè)數(shù)n定義為線性表的長(zhǎng)度，n=0時(shí)成為空表。⑹獲得元素：函數(shù)名稱是GetElem(L,i,e)；初始條件是線性表已存在，1≤i≤ListLength(L)；操作結(jié)果是用e返回L中第i個(gè)數(shù)據(jù)元素的值。其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示，并給出適當(dāng)?shù)牟僮魈崾撅@示。 //線性表的長(zhǎng)度 int listsize。2. 銷毀線性表思想：將銷毀線性表的過(guò)程寫成函數(shù)，其中傳入函數(shù)是主函數(shù)中定義的結(jié)構(gòu)性變量L。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（1）。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。如圖16所示。圖113 查找數(shù)據(jù)元素的測(cè)試結(jié)果，確定值為4的數(shù)據(jù)元素前驅(qū)數(shù)據(jù)元素，測(cè)試結(jié)果如圖114所示。并且我還加深了對(duì)線性表的存在與空的區(qū)別。 邏輯結(jié)構(gòu)與基本運(yùn)算 抽象數(shù)據(jù)類型二叉樹的定義如下：ADT BinaryTree { 數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。⑹求二叉樹深度：函數(shù)名稱是BiTreeDepth(T)；初始條件是二叉樹T存在；操作結(jié)果是返回T的深度。⑿獲得右孩子結(jié)點(diǎn)：函數(shù)名稱是RightChild(T,e)；初始條件是二叉樹T已存在，e是T中某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的右孩子結(jié)點(diǎn)指針。 操作結(jié)果是根據(jù)LR為0或者1，刪除c為T中p所指結(jié)點(diǎn)的左或右子樹。演示系統(tǒng)可選擇實(shí)現(xiàn)線性表的文件形式保存，演示系統(tǒng)可選擇實(shí)現(xiàn)多個(gè)線性表的管理。圖21 系統(tǒng)設(shè)計(jì)結(jié)構(gòu)圖 運(yùn)算算法思想與設(shè)計(jì) 二叉樹運(yùn)算算法思想與設(shè)計(jì)如下： 初始化二叉樹算法思想：將初始化二叉樹過(guò)程寫成函數(shù)，函數(shù)的參數(shù)是主函數(shù)中所定義的結(jié)構(gòu)類型指針T（參數(shù)傳遞為引用方式，即取別名），T所指向的是二叉樹的根結(jié)點(diǎn)，將T賦值為NULL即完成了二叉樹的初始化。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(1)。或者采取非遞歸的方式，即使用堆棧來(lái)存儲(chǔ)根結(jié)點(diǎn)的信息，先將根結(jié)點(diǎn)入棧，在循環(huán)中彈出棧頂元素，比較關(guān)鍵字，在分別將其右子樹和左子樹的根結(jié)點(diǎn)入棧。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。1 插入子樹的算法思想是：將插入子樹寫成函數(shù)，函數(shù)的形參是二叉樹的頭指針T，指向特定二叉樹結(jié)點(diǎn)的指針p（在主函數(shù)中要求輸入關(guān)鍵字，通過(guò)FIND函數(shù)找到插入點(diǎn)位置并將其值記錄），再調(diào)用CreateBiTNode函數(shù)創(chuàng)建根結(jié)點(diǎn)c的右子樹為空的二叉樹，插入的過(guò)程即將P所指向結(jié)點(diǎn)的左子樹或者右子樹根結(jié)點(diǎn)指針賦值給c的右孩子指針域，而c賦值給p所指結(jié)點(diǎn)的左指針域或者右指針域。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。typedef BiTree QElemType。圖27 先序遍歷二叉樹的測(cè)試結(jié)果，中序遍歷二叉樹，并執(zhí)行PRINT操作，測(cè)試結(jié)果如圖28所示。圖214 求二叉樹指定結(jié)點(diǎn)的值測(cè)試結(jié)果，將關(guān)鍵字為E的結(jié)點(diǎn)值改為9，測(cè)試結(jié)果如圖215所示。通過(guò)遍歷新生成的二叉樹驗(yàn)證其結(jié)構(gòu)正確性。 通過(guò)遞歸算法的編寫加深了對(duì)遞歸的認(rèn)識(shí)和理解。 int listsize。}//InitList_Sqstatus DestroyList(SqList amp。L) { if ( == NULL) return ERROR。}status GetElem(SqList L, int i, ElemType amp。 return FALSE。 } else return FALSE。 } return FALSE。 } q = amp。 return OK。 for (q = amp。 for (i = 0。 return FALSE。L) { FILE *stream。[], sizeof(int), 1, stream)) { ++。t)。 int op = 1。 printf( 4. ListEmpty 11. ListDelete\n)。op)。 else printf(線性表刪除失??！\n)。 getchar()。 case 5: //printf(\nListLength功能待實(shí)現(xiàn)！\n)。 getchar()。e)。 case 8: printf(請(qǐng)輸入數(shù)據(jù)元素！\n)。 break。 getchar()。 getchar()。 else printf(刪除的元素為%d,表的長(zhǎng)度是%d!\n, e, L[t].length)。 case 13: char filename[30]。 case 14: if (DataLoading(L[t]) == FALSE) printf(文件加載到當(dāng)前線性表失?。n)。}//end of main()附錄B 基于二叉鏈表二叉樹實(shí)現(xiàn)的源程序黑體小2加粗居中，另起頁(yè)include include include define TRUE 1define FALSE 0define OK 1define ERROR 0define OVERFLOW 2define MAXLENG 10define MAXSIZE 2define QMAXSIZE 5typedef int status。 int front。T) { //將二叉樹T置空 T = NULL。}//采用遞歸的方式銷毀二叉樹，思想和前序遍歷二叉樹是一致的//若采取非遞歸的方式銷毀二叉樹和層序遍歷二叉樹的思想一致status CreateBiTNode(BiTree amp。 if (ch == 39。 getchar()。}status BiTreeEmpty(B