【文章內(nèi)容簡(jiǎn)介】 列時(shí)將其左右子樹(shù)根結(jié)點(diǎn)放進(jìn)隊(duì)列，循環(huán)即可一層一層的訪(fǎng)問(wèn)二叉樹(shù)。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。 系統(tǒng)實(shí)現(xiàn)黑體4號(hào)加粗， 編程環(huán)境、運(yùn)行環(huán)境、項(xiàng)目工程描述 本次實(shí)驗(yàn)采用Microsoft Visual Studio 2015編程軟件編寫(xiě)，并用VS2015進(jìn)行編譯運(yùn)行，項(xiàng)目名稱(chēng)是BinaryTree。 頭文件及預(yù)定義常量說(shuō)明頭文件 include include include 預(yù)定義常量（1）函數(shù)結(jié)果狀態(tài)宏定義 define TRUE 1define FALSE 0define OK 1define ERROR 0define OVERFLOW 2（2）類(lèi)型表達(dá)式 typedef int status。typedef char TElemType。typedef BiTree QElemType。（3）系統(tǒng)常量定義define MAXLENG 10define MAXSIZE 2define QMAXSIZE 5 演示系統(tǒng)操作。圖22 演示系統(tǒng)操作圖1~20，會(huì)執(zhí)行序號(hào)所對(duì)應(yīng)的操作。圖23 演示系統(tǒng)操作圖2，演示系統(tǒng)結(jié)束并退出。圖23 演示系統(tǒng)操作圖3 測(cè)試計(jì)劃測(cè)試功能及序號(hào)輸入函數(shù)的參數(shù)預(yù)計(jì)輸出此時(shí)二叉樹(shù)的狀態(tài)無(wú)二叉樹(shù)創(chuàng)建成功二叉樹(shù)根結(jié)點(diǎn)指針置為空，未分配具體的存儲(chǔ)空間無(wú)二叉樹(shù)銷(xiāo)毀失敗二叉樹(shù)頭指針置為空，對(duì)應(yīng)的存儲(chǔ)空間被釋放依次輸入關(guān)鍵字及其對(duì)應(yīng)值：A1 B9 D7 E0H1I2C9F6G2J0二叉樹(shù)創(chuàng)建成功按照輸入關(guān)鍵字的先序序列創(chuàng)建二叉樹(shù)，每個(gè)結(jié)點(diǎn)賦值無(wú)二叉樹(shù)清空成功二叉樹(shù)根結(jié)點(diǎn)保留，但其左右指針域置為空無(wú)二叉樹(shù)不為空同上3無(wú)二叉樹(shù)的深度為4同上3無(wú)二叉樹(shù)的根結(jié)點(diǎn)關(guān)鍵字為A同上3輸入關(guān)鍵字為D輸出關(guān)鍵字為D的結(jié)點(diǎn)值為7同上3輸入關(guān)鍵字E輸入關(guān)鍵字為E的結(jié)點(diǎn)的值改為9輸出關(guān)鍵字為E的結(jié)點(diǎn)的值已改為9同上3輸入查找關(guān)鍵字為I的結(jié)點(diǎn)輸出關(guān)鍵字為I的結(jié)點(diǎn)的雙親結(jié)點(diǎn)為E同上3(測(cè)試1)輸入查找關(guān)鍵字為E的結(jié)點(diǎn)輸出關(guān)鍵字為E的結(jié)點(diǎn)的左孩子為H同上3（測(cè)試2）輸入查找關(guān)鍵字為F的結(jié)點(diǎn)輸出關(guān)鍵字為F的左孩子不存在，查找失敗同上3（測(cè)試1）輸入查找關(guān)鍵字為B的結(jié)點(diǎn)輸出關(guān)鍵字為B的結(jié)點(diǎn)右孩子為E同上3（測(cè)試2）輸入查找關(guān)鍵字為F的結(jié)點(diǎn)輸出關(guān)鍵字為F的右孩子不存在，操作失敗同上3（測(cè)試1）輸入查找關(guān)鍵字為G的結(jié)點(diǎn)輸出關(guān)鍵字為G的結(jié)點(diǎn)左孩子為F同上3（測(cè)試2）輸入查找關(guān)鍵字為B的結(jié)點(diǎn)輸出關(guān)鍵字為B的結(jié)點(diǎn)左孩子不存在，操作失敗同上3輸入LR值為0，輸入查找關(guān)鍵字為J，新生成右子樹(shù)為空的二叉樹(shù)輸入：M1N2K3（字母后為該關(guān)鍵字結(jié)點(diǎn)的值）輸出二叉樹(shù)插入成功在原二叉樹(shù)的基礎(chǔ)上，將新生成二叉樹(shù)作為關(guān)鍵字為J的結(jié)點(diǎn)的左子樹(shù)，J的左子樹(shù)作為新生成二叉樹(shù)的右子樹(shù)輸入查找關(guān)鍵字為E的結(jié)點(diǎn)，輸入LR值為1輸出二叉樹(shù)刪除成功在上一基礎(chǔ)上，將原二叉樹(shù)的E結(jié)點(diǎn)的右子樹(shù)刪除無(wú)輸出先序遍歷序列：ABDEHICFGJ同上3無(wú)輸出中序遍歷序列：DBHEIAFCGJ同上3無(wú)輸出后續(xù)遍歷序列：DHIEBFJGCA同上3無(wú)輸出層序遍歷序列：ABCDEFGHIJ同上3表21 測(cè)試計(jì)劃圖24 按以上測(cè)試用例生成的原始二叉樹(shù) 測(cè)試，測(cè)試結(jié)果如圖25所示。圖25 初始化二叉樹(shù)測(cè)試，創(chuàng)建二叉樹(shù)，測(cè)試結(jié)果如圖26所示。圖26 二叉樹(shù)創(chuàng)建，根據(jù)其前序遍歷、中序遍歷、后續(xù)遍歷的結(jié)果是否與預(yù)期一致判斷結(jié)構(gòu)是否正確。執(zhí)行功能17，先序遍歷二叉樹(shù)，并執(zhí)行PRINT操作，測(cè)試結(jié)果如圖27所示。圖27 先序遍歷二叉樹(shù)的測(cè)試結(jié)果，中序遍歷二叉樹(shù)，并執(zhí)行PRINT操作，測(cè)試結(jié)果如圖28所示。圖28 中序遍歷二叉樹(shù)的測(cè)試結(jié)果，后序遍歷二叉樹(shù)，測(cè)試結(jié)果如圖29所示。圖29 后序遍歷二叉樹(shù)的測(cè)試結(jié)果，層序遍歷二叉樹(shù)，測(cè)試結(jié)果如圖210所示。圖210 層序遍歷二叉樹(shù)的測(cè)試結(jié)果上述測(cè)試與預(yù)期的遍歷結(jié)果是一致的，說(shuō)明生成二叉樹(shù)的結(jié)構(gòu)正確性，即生成了如圖24所示的二叉樹(shù)。，判斷二叉樹(shù)是否為空樹(shù)，測(cè)試結(jié)果如圖211所示。圖211 判斷二叉樹(shù)是否為空測(cè)試結(jié)果，求二叉樹(shù)的深度，測(cè)試結(jié)果如圖212所示。圖212 求二叉樹(shù)深度測(cè)試結(jié)果，求二叉樹(shù)的根結(jié)點(diǎn)，測(cè)試結(jié)果如圖213所示。圖213 求二叉樹(shù)根結(jié)點(diǎn)的測(cè)試結(jié)果，求關(guān)鍵字為D的結(jié)點(diǎn)的值，測(cè)試結(jié)果如圖214所示。圖214 求二叉樹(shù)指定結(jié)點(diǎn)的值測(cè)試結(jié)果，將關(guān)鍵字為E的結(jié)點(diǎn)值改為9，測(cè)試結(jié)果如圖215所示。圖215 對(duì)指定結(jié)點(diǎn)重新賦值測(cè)試結(jié)果，輸入查找關(guān)鍵字為E的結(jié)點(diǎn)的左孩子，測(cè)試結(jié)果如圖216所示。圖216 查找左孩子的測(cè)試結(jié)果1，測(cè)試關(guān)鍵字為F的結(jié)點(diǎn)的左孩子，測(cè)試結(jié)果如圖217所示。圖217 查找左孩子的測(cè)試結(jié)果2，查找關(guān)鍵字為I的結(jié)點(diǎn)的雙親結(jié)點(diǎn)，測(cè)試結(jié)果如圖218所示。圖218 查找結(jié)點(diǎn)的雙親結(jié)點(diǎn)，查找關(guān)鍵字為E的結(jié)點(diǎn)的左兄弟，查找結(jié)果如圖219所示。圖219 查找結(jié)點(diǎn)的左兄弟測(cè)試結(jié)果1，查找關(guān)鍵字為B的結(jié)點(diǎn)的左兄弟，查找結(jié)果如圖220所示。圖220 查找結(jié)點(diǎn)的左兄弟測(cè)試結(jié)果2，在原二叉樹(shù)的基礎(chǔ)上插入子樹(shù)，測(cè)試結(jié)果如圖221所示。圖221 插入子樹(shù)的測(cè)試結(jié)果插入子樹(shù)后，先序遍歷得到的序列為：ABDEHICFGJMNK,層序遍歷得到的序列應(yīng)該為：ABCDEFGHIJMNK，中序遍歷得到的序列為：DBHEIAFCGNKMJ。通過(guò)遍歷新生成的二叉樹(shù)驗(yàn)證其結(jié)構(gòu)正確性。圖222 先序遍歷的測(cè)試結(jié)果圖223 層序遍歷的測(cè)試結(jié)果圖224 后序遍歷的測(cè)試結(jié)果以上遍歷結(jié)果與預(yù)期相吻合，說(shuō)明插入后得到的新二叉樹(shù)滿(mǎn)足結(jié)構(gòu)正確性。，刪除關(guān)鍵字為E的結(jié)點(diǎn)的右子樹(shù)，即I結(jié)點(diǎn)，測(cè)試結(jié)果如圖225所示。圖225 刪除子樹(shù)的測(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ō)明刪除子樹(shù)后結(jié)構(gòu)的正確性，函數(shù)功能執(zhí)行正確。，刪除二叉樹(shù)，此時(shí)銷(xiāo)毀二叉樹(shù)的存儲(chǔ)空間，頭指針置為空，測(cè)試結(jié)果如圖229所示。圖229 銷(xiāo)毀二叉樹(shù)的測(cè)試結(jié)果二叉樹(shù)銷(xiāo)毀后，進(jìn)行判斷是否為空，應(yīng)該返回空樹(shù)，測(cè)試結(jié)果如圖230所示。圖230 驗(yàn)證二叉樹(shù)為空 實(shí)驗(yàn)小結(jié)黑體4號(hào)加粗，通過(guò)本次實(shí)驗(yàn)，熟悉了二叉樹(shù)的基本操作，學(xué)會(huì)了用二叉樹(shù)去解決一些問(wèn)題，學(xué)習(xí)中的主要收獲為以下幾點(diǎn)： 加深了對(duì)二叉樹(shù)的概念和邏輯結(jié)構(gòu)的理解。 掌握了二叉樹(shù)的基本操作。 通過(guò)遞歸算法的編寫(xiě)加深了對(duì)遞歸的認(rèn)識(shí)和理解。 通過(guò)非遞歸算法的編寫(xiě)加深了對(duì)遞歸內(nèi)在機(jī)制的分析以及學(xué)會(huì)了如何用堆棧去代替遞歸達(dá)到相同的目的。 規(guī)范了報(bào)告撰寫(xiě)能力。參考文獻(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++. Second Edition, Calvin College, 2005 [3] 殷立峰. Qt C++跨平臺(tái)圖形界面程序設(shè)計(jì)基礎(chǔ). 清華大學(xué)出版社,2014:192～197[4] (C語(yǔ)言版). 清華大學(xué)出版社宋體小4號(hào)，指導(dǎo)教師評(píng)定意見(jiàn)黑體小2加粗居中，另起頁(yè)一、對(duì)實(shí)驗(yàn)報(bào)告的評(píng)語(yǔ)二、對(duì)實(shí)驗(yàn)報(bào)告評(píng)分評(píng)分項(xiàng)目(分值)程序內(nèi)容()程序規(guī)范()報(bào)告內(nèi)容()報(bào)告規(guī)范()考勤（8分）逾期扣分合 計(jì)(100分)得分附錄A 基于順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性表實(shí)現(xiàn)的源程序黑體小2加粗居中，另起頁(yè)include include include define TRUE 1define FALSE 0define OK 1define ERROR 0define INFEASTABLE 1define OVERFLOW 2define LIST_INIT_SIZE 100define LISTINCREMENT 10typedef int status。typedef int ElemType。typedef struct { ElemType * elem。 int length。 int listsize。}SqList。status Initlist(SqList amp。L) { = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))。 if (!) exit(OVERFLOW)。 = 0。 = LIST_INIT_SIZE。 return OK。}//InitList_Sqstatus DestroyList(SqList amp。L) { if ( != NULL) { free()。 = NULL。 = 0。 = 0。 return OK。 } return ERROR。}status ClearList(SqList amp。L) { if ( == NULL) return ERROR。 else { = 0。 return OK。 }}int ListLength(SqList amp。L) { return 。}status ListEmpty(SqList amp。L) { if ( == 0) return TRUE。 else return FALSE。}status GetElem(SqList L, int i, ElemType amp。e) { if (i1 || iListLength(L)) return OVERFLOW。 else e = [i 1]。 return OK。}//用e返回L中第i個(gè)數(shù)據(jù)元素的值status LocateElem(SqList L, ElemType e) { int j。 for (j = 0。 j = 1。 j++) if ([j] == e) return j + 1。 return FALSE。}status PriorElem(SqList L, ElemType cur, ElemType amp。pre_e) { int j。 j = LocateElem(L, cur)。 if (j != 0 amp。amp。 j != 1) { pre_e = [j 2]。 return TRUE。 } else return FALSE。}status NextElem(SqList L, ElemType cur, ElemType amp。next_e) { int j。 j = LocateElem(L, cur)。 if (j != 0 amp。amp。 j != ) { next_e = [j]。 return TRUE。 } return FALSE。}status ListInsert(SqList amp。L, int i, ElemType e) { ElemType *newbase, *p, *q。 if (i1 || i + 1) return ERROR。 if ( = ){//當(dāng)前存儲(chǔ)空間已滿(mǎn)，增加分配 newbase = (ElemType*)realloc(, ( + LISTINCREMENT)*sizeof(ElemType))。 if(!newbase) exit(OVERFLOW)。 = newbase。 +=LISTINCREMENT。 } q = amp。([i 1])。 for (p = amp。([ 1])。 p = q。 p) *(p + 1) = *p。 *q = e。 ++。 return OK。}status ListDelete(SqList amp。L, int i, ElemType amp。e) { if (i1 || i) return ERROR。 e = [i 1]。 ElemType *p, *q。 p = amp。([i