華中科技大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程報(bào)告

1、課 程 實(shí) 驗(yàn) 報(bào) 告課程名稱： 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 專業(yè)班級： 信息安全201502 學(xué) 號： 姓 名： 指導(dǎo)教師： 報(bào)告日期： 2016年 10月 28 日 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院目 錄黑體小2號加粗居中.間距前后0.5行1基于順序存儲結(jié)構(gòu)的線性表實(shí)現(xiàn)11.1問題描述11.2系統(tǒng)設(shè)計(jì)11.3系統(tǒng)實(shí)現(xiàn)11.4實(shí)驗(yàn)小結(jié)12 基于二叉鏈表的二叉樹實(shí)現(xiàn)22.1問題描述22.2系統(tǒng)設(shè)計(jì)22.3系統(tǒng)實(shí)現(xiàn)22.4實(shí)驗(yàn)小結(jié)2指導(dǎo)教師評定意見3附錄A 基于順序存儲結(jié)構(gòu)線性表實(shí)現(xiàn)的源程序4附錄B 基于二叉鏈表二叉樹實(shí)現(xiàn)的源程序5章為宋體小4號加粗，其余宋體小4號，行間距1.5倍,段落前后0行1 基于順序存儲結(jié)構(gòu)的線性

2、表實(shí)現(xiàn)黑體小2加粗，居中，間距前后0.5行1.1 問題描述黑體4號加粗，間距前后0.5行采用順序表的物理結(jié)構(gòu)，構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)。其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示。定義了線性表的初始化表、銷毀表、清空表、判定空表、求表長和獲得元素等基本運(yùn)算對應(yīng)的函數(shù)，并給出適當(dāng)?shù)牟僮魈崾撅@示，可選擇以文件的形式進(jìn)行存儲和加載，即將生成的線性表存入到相應(yīng)的文件中，也可以從文件中獲取線性表進(jìn)行操作。1.1.1 線性表的基本概念線性表是最常用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)，即n個(gè)數(shù)據(jù)元素的有限序列。線性表中元素的個(gè)數(shù)n定義為線性表的長度，n=0時(shí)成為空表。在非空表中的每個(gè)數(shù)據(jù)元素

3、都有一個(gè)確定的位置，如a1是第一個(gè)數(shù)據(jù)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素。線性表的存儲結(jié)構(gòu)分為線性存儲和鏈?zhǔn)酱鎯Α?.1.2 邏輯結(jié)構(gòu)與基本運(yùn)算線性表的數(shù)據(jù)邏輯結(jié)構(gòu)定義如下: ADT List 數(shù)據(jù)對象：D=ai|aiElemSet，i=1，2，n，n0 數(shù)據(jù)關(guān)系：R1= <ai-1，ai> | ai-1，aiD，i=2，n 依據(jù)最小完備性和常用性相結(jié)合的原則，以函數(shù)形式定義了包括線性表的初始化表、加載表、保存表、銷毀表、清空表、判定空表、求表長、獲得元素、查找元素、獲得前驅(qū)、獲得后繼、插入元素、刪除元素、遍歷表 14 個(gè)基本運(yùn)算，要求分別定義函數(shù)來實(shí)現(xiàn)上述功能，具

4、體功能運(yùn)算如下：初始化表：函數(shù)名稱是InitaList(L)；初始條件是線性表L不存在已存在；操作結(jié)果是構(gòu)造一個(gè)空的線性表。銷毀表：函數(shù)名稱是DestroyList(L)；初始條件是線性表L已存在；操作結(jié)果是銷毀線性表L。清空表：函數(shù)名稱是ClearList(L)；初始條件是線性表L已存在；操作結(jié)果是將L重置為空表。判定空表：函數(shù)名稱是ListEmpty(L)；初始條件是線性表L已存在；操作結(jié)果是若L為空表則返回TRUE,否則返回FALSE。求表長：函數(shù)名稱是ListLength(L)；初始條件是線性表已存在；操作結(jié)果是返回L中數(shù)據(jù)元素的個(gè)數(shù)。獲得元素：函數(shù)名稱是GetElem(L,i,e)；

5、初始條件是線性表已存在，1iListLength(L)；操作結(jié)果是用e返回L中第i個(gè)數(shù)據(jù)元素的值。查找元素：函數(shù)名稱是LocateElem(L,e,compare()；初始條件是線性表已存在；操作結(jié)果是返回L中第1個(gè)與e滿足關(guān)系compare（）關(guān)系的數(shù)據(jù)元素的位序，若這樣的數(shù)據(jù)元素不存在，則返回值為0。獲得前驅(qū)：函數(shù)名稱是PriorElem(L,cur_e,pre_e)；初始條件是線性表L已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。獲得后繼：函數(shù)名稱是NextElem(L,cur_e,next_e)；初始條件是線性表

6、L已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無定義。插入元素：函數(shù)名稱是ListInsert(L,i,e)；初始條件是線性表L已存在且非空，1iListLength(L)+1；操作結(jié)果是在L的第i個(gè)位置之前插入新的數(shù)據(jù)元素e。刪除元素：函數(shù)名稱是ListDelete(L,i,e)；初始條件是線性表L已存在且非空，1iListLength(L)；操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，用e返回其值。遍歷表：函數(shù)名稱是ListTraverse(L,visit()，初始條件是線性表L已存在；操作結(jié)果是依次對L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)

7、visit()。1.1.3 演示系統(tǒng)與數(shù)據(jù)文件要求構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)。其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示，并給出適當(dāng)?shù)牟僮魈崾撅@示。附錄 A 提供了簡易菜單的框架。 演示系統(tǒng)可選擇實(shí)現(xiàn)線性表的文件形式保存。其中，需要設(shè)計(jì)文件數(shù)據(jù)記錄格式，以高效保存線性表數(shù)據(jù)邏輯結(jié)構(gòu)(D,R)的完整信息；需要設(shè)計(jì)線性表文件保存和加載操作合理模式。附錄 B 提供了文件存取的方法。 演示系統(tǒng)可選擇實(shí)現(xiàn)多個(gè)線性表管理。1.2 系統(tǒng)設(shè)計(jì)黑體4號加粗，間距前后0.5行1.2.1 數(shù)據(jù)物理結(jié)構(gòu)線性表的數(shù)據(jù)物理結(jié)構(gòu)如下：typedef struct /順序表（順序結(jié)構(gòu)）的定義 Ele

8、mType *elem; /定義整型指針，為存儲空間基址 int length; /線性表的長度 int listsize; /當(dāng)前分配的存儲容量(以 sizeof(ElemType)為單位) SqList;要實(shí)現(xiàn)同時(shí)對多個(gè)線性表管理，只需要定義一個(gè)結(jié)構(gòu)數(shù)組即可。1.2.2 演示系統(tǒng)將菜單演示和用戶選擇寫入到while循環(huán)中，用OP獲取用戶的選擇，OP初始化為1，以便第一次能進(jìn)入循環(huán)。進(jìn)入循環(huán)后系統(tǒng)首先顯示功能菜單，然后用戶輸入選擇0-14，其中1-14分別代表線性表的一個(gè)基本運(yùn)算，在主函數(shù)中通過SWITCH語句對應(yīng)到相應(yīng)的函數(shù)功能，執(zhí)行完該功能后BREAK跳出SWITCH語句，繼續(xù)執(zhí)行whi

9、le循環(huán)，直至用戶輸入0退出當(dāng)前演示系統(tǒng)。在第一次進(jìn)入循環(huán)while時(shí)首先會(huì)詢問用戶對哪個(gè)線性表進(jìn)行操作，直至退出演示系統(tǒng)之前一直對指定線性表進(jìn)行操作。演示系統(tǒng)結(jié)構(gòu)如圖1- 運(yùn)算算法思想與設(shè)計(jì)線性表運(yùn)算算法思想與設(shè)計(jì)如下：1. 初始化線性表思想：將線性表初始化過程寫成函數(shù)，其中傳入函數(shù)的參數(shù)是主函數(shù)中定義的結(jié)構(gòu)型變量L的引用，在函數(shù)中，首先使用malloc函數(shù)分配LISTSIZE大小的連續(xù)內(nèi)存空間，并將首地址返回賦值給L.elem，由于線性表的長度為0，將L.length初始化為0，即完成了線性表的初始化。經(jīng)分析，算法的時(shí)間復(fù)雜度為O(1)。2. 銷毀線性表思想：將銷毀線性表的過

10、程寫成函數(shù)，其中傳入函數(shù)是主函數(shù)中定義的結(jié)構(gòu)性變量L。在函數(shù)中，首先使用free函數(shù)釋放掉以L.elem為首地址的連續(xù)內(nèi)存空間，再將L.length,L.listsize重新賦值為0。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(1)。3. 清空線性表的思想：將清空表的過程寫成函數(shù)，其中將主函數(shù)中定義的結(jié)構(gòu)性變量L的引用作為函數(shù)參數(shù)，在函數(shù)中，由于清空操作并不釋放內(nèi)存空間，故只需將線性表的長度置為0即可。經(jīng)分許，該算法的時(shí)間復(fù)雜度為O(1)。4. 求線性表表長的思想：將求表長過程寫成函數(shù)，其中主函數(shù)中定義的結(jié)構(gòu)性變量L的引用作為函數(shù)的參數(shù)，在函數(shù)中，直接返回L.length即為所求線性表的表長。經(jīng)分析，該算

11、法的時(shí)間復(fù)雜度為O（1）。5. 獲得元素的算法思想：將獲得線性表元素寫成函數(shù)，其中函數(shù)的參數(shù)是結(jié)構(gòu)型變量L以及數(shù)據(jù)元素的序號i，由于采取的是線性存儲結(jié)構(gòu)，故直接通過訪問數(shù)組的方式即L.elemi-1來獲取元素，當(dāng)然，在這之前需要判斷合法性。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（1）。6. 查找元素的算法思想：將查找線性表特定值的數(shù)據(jù)元素寫成函數(shù)，其中函數(shù)的參數(shù)是主函數(shù)中定義的結(jié)構(gòu)類型變量L以及查找的數(shù)據(jù)元素的值，通過循環(huán)對線性表中的每一個(gè)元素與給定值比較看是否相等，如果相等就返回該元素的次序。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。查找算法的流程圖如圖1-2所示。圖1-2 線性表查找算法流程圖7. 獲

12、得前驅(qū)算法思想：將獲得前驅(qū)過程寫成函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)體類型變量以及特定數(shù)據(jù)元素的值，接受前驅(qū)的變量作為另一個(gè)參數(shù)，首先調(diào)用獲得元素的函數(shù)判斷該線性表中特定數(shù)據(jù)元素的位序，首先判斷不為1，否則的話返回FALSE，然后直接返回其前一個(gè)元素即L.elemj-2。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。8. 獲得后繼算法思想：將獲得后繼寫成函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)體類型變量以及特定數(shù)據(jù)元素的值。首先判斷是否為最后一個(gè)元素，如果不是則直接返回其后一個(gè)元素，否則的話返回FALSE，同樣該算法需要調(diào)用獲得元素的函數(shù)來確定該特定元素在線性表中的次序。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。9. 插入元素算法思想

13、：將插入函數(shù)寫成函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)型變量以及插入元素的值大小以及插入位置。在函數(shù)中，首先判斷插入位置的合法性，即是否在線性表中合適的位置，其次還要判斷當(dāng)前存儲空間是否已滿，如果滿了的話要malloc函數(shù)重新分配空間，插入元素時(shí)從該位置起到最后一個(gè)元素從后開始以此往后移一個(gè)單元。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。該算法的程序流程圖如圖1-3所示。圖1-3 線性表中插入元素算法流程圖10. 刪除元素算法思想：將刪除線性表中元素寫成函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)類型變量，首先判斷位序的合法性，在之后直接將刪除元素位置后一個(gè)元素直到最后一個(gè)元素以此從前往后向前移動(dòng)一個(gè)單元。經(jīng)分析，該算法的時(shí)間復(fù)雜度為

14、O（n）。11. 遍歷線性表算法思想：將遍歷線性表寫成一個(gè)函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)類型變量，直接用一個(gè)循環(huán)來對線性表中的每一個(gè)元素進(jìn)行操作。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。圖內(nèi)容：字體大小參考宋體5號，居中1.3 系統(tǒng)實(shí)現(xiàn)黑體4號加粗，間距前后0.5行1.3.1 編程環(huán)境、運(yùn)行環(huán)境、項(xiàng)目工程描述本次實(shí)驗(yàn)采用Microsoft Visual Studio 2015編程軟件編寫，并用VS2015進(jìn)行編譯運(yùn)行，項(xiàng)目名稱是linear datastructer。1.3.2 頭文件及預(yù)定義常量說明1.頭文件#include <stdio.h>#include <malloc.h&g

15、t;#include <stdlib.h>2.預(yù)定義常量#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASTABLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 103.類型表達(dá)式typedef int status;typedef int ElemType;1.3.3 系統(tǒng)演示操作1.系統(tǒng)一開始會(huì)顯示菜單提示用戶輸入選擇對1-99號線性表哪一個(gè)進(jìn)行操作。如圖1-4所示。圖1-4 系統(tǒng)演示12.選擇對

16、線性表1進(jìn)行操作，進(jìn)入菜單演示界面，如圖1-5所示。圖1-5 系統(tǒng)演示23.選擇退出0，此時(shí)會(huì)退出當(dāng)前演示界面，即退出對當(dāng)前線性表的操作，并顯示要求用戶選擇對哪一個(gè)線性表進(jìn)行操作。如圖1-6所示。圖1-6 演示系統(tǒng)34.輸入0，退出演示系統(tǒng)，結(jié)束操作，如圖1-7所示。圖1-7 系統(tǒng)演示41.3.4 測試計(jì)劃測試功能及序號輸入要管理的線性表序號輸入函數(shù)的參數(shù)（具體元素）預(yù)計(jì)輸出此時(shí)線性表的狀態(tài)1.IntiaList1無線性表初始化成功分配了連續(xù)的物理存儲空間，表長度為0，表尺寸為空間大小2.DestroyList1無線性表刪除成功線性表連續(xù)物理空間被釋放， 3.ClearList1無線性表清空成

17、功線性表的物理空間保留，但表長置為0.10.ListInsert(多次調(diào)用)1輸入1：1，2：2，3：3，4：4，5：5線性表創(chuàng)建成功創(chuàng)建了一個(gè)線性表，序列為：1，2，3，4，54.ListEmpty1無輸出線性表非空同上5.ListLength1無輸出線性表的長度為5同上6.GetElem1輸入數(shù)據(jù)元素的位序?yàn)?輸出線性表的第三個(gè)元素為3同上8.PriorElem1輸入數(shù)據(jù)元素的值為4輸出4的前面一個(gè)元素是3同上9.NextElem1輸入數(shù)據(jù)元素的值為2輸出2的后面一個(gè)元素是3同上11.ListDelete1輸入數(shù)據(jù)元素的置為3輸出元素刪除成功重新生成了一新的線性表，序列為12457.Loc

18、ateElem1輸入數(shù)據(jù)元素的值為4輸出4是線性表中的第三個(gè)數(shù)據(jù)元素同上13.SaveData1輸入保存到的文件名為LY.txt輸出文件保存成功同上14.DataLoading1輸入要加載的文件名為LY.txt輸出文件加載成功同上1.3.5 測試1.輸入對線性表1進(jìn)行操作，進(jìn)入菜單演示界面，執(zhí)行功能1，初始化線性表，測試結(jié)果如圖1-8所示。圖1-8 初始化線性表的測試結(jié)果2.執(zhí)行功能2，銷毀線性表，測試結(jié)果如圖1-9所示。圖1-9 刪除線性表的操作結(jié)果3.執(zhí)行功能10，往線性表中添加數(shù)據(jù)元素1,2,3,4,5，測試結(jié)果如圖1-10所示。圖1-10 插入元素的測試結(jié)果4.執(zhí)行功能4，判斷線性表是

19、否為空，測試結(jié)果如圖1-11所示。圖1-11 判斷線性表非空的測試結(jié)果5.執(zhí)行功能5，求線性表的長度，測試結(jié)果如圖1-12所示。圖1-12 求線性表長度的測試結(jié)果6.執(zhí)行功能6，查找第三個(gè)數(shù)據(jù)元素的數(shù)值，測試結(jié)果如圖1-13所示。圖1-13 查找數(shù)據(jù)元素的測試結(jié)果7.執(zhí)行功能8，確定值為4的數(shù)據(jù)元素前驅(qū)數(shù)據(jù)元素，測試結(jié)果如圖1-14所示。圖1-14 查找元素的前驅(qū)數(shù)據(jù)元素8.執(zhí)行功能9，確定值為2的數(shù)據(jù)元素的后繼數(shù)據(jù)元素，測試結(jié)果如圖1-15所示。1-15 查找元素的后繼數(shù)據(jù)元素9.執(zhí)行功能11，刪除第三個(gè)數(shù)據(jù)元素，測試結(jié)果如圖1-16所示。圖1-16 刪除線性表中的數(shù)據(jù)元素測試結(jié)果10.執(zhí)行

20、功能13，保存線性表中的數(shù)據(jù)元素值到文件名為LY.txt的文件中，測試結(jié)果如圖1-17所示。圖1-17 保存線性表測試結(jié)果11.清空此時(shí)的線性表，在執(zhí)行功能14，加載線性表，測試結(jié)果如圖1-18所示。圖1-18 線性表加載的測試結(jié)果11.執(zhí)行功能12，遍歷并輸出線性表中的元素，應(yīng)該輸出1245，測試結(jié)果如圖1-19所示。圖1-19 遍歷輸出線性表中元素的測試結(jié)果1.4 實(shí)驗(yàn)小結(jié)黑體4號加粗，間距前后0.5行經(jīng)過本次試驗(yàn)，我充分了解到了線性表的物理結(jié)構(gòu)，并且通過切身的體會(huì)熟練掌握了線性表的基本操作，提高了自己寫有關(guān)線性表的代碼的能力，尤其是在寫的過程中遇到了許多困難，在多次尋求同學(xué)的幫助下終于解

21、決了。還發(fā)現(xiàn)了自己的薄弱之處，就是在文件的處理時(shí)存在許多紕漏，導(dǎo)致文件讀取不成功。并且我還加深了對線性表的存在與空的區(qū)別。還有對“&”引用符號的理解，加強(qiáng)了其與“*”的區(qū)別，“&e”使得在函數(shù)中調(diào)用主函數(shù)中的值“e”時(shí)可以同時(shí)更改其值，如在GetElem函數(shù) 中調(diào)用了“e”的值然后在主函數(shù)中輸出，如果要更改其值的話就必須要用“&”符號。2 基于二叉鏈表的二叉樹實(shí)現(xiàn)黑體小2加粗，居中，間距前后0.5行，每章另起頁2.1 問題描述黑體4號加粗，間距前后0.5行采用二叉鏈表作為二叉樹的物理結(jié)構(gòu)，實(shí)現(xiàn)二叉樹的基本運(yùn)算，數(shù)據(jù)元素的類型名可自行定義。要求構(gòu)造一個(gè)具有菜單的功能演示系

22、統(tǒng)，其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示，并給出適當(dāng)?shù)牟僮魈崾尽?.1.1 二叉樹的基本概念二叉樹是一種樹型結(jié)構(gòu)，即n個(gè)結(jié)點(diǎn)的有限集，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。2.1.2 邏輯結(jié)構(gòu)與基本運(yùn)算抽象數(shù)據(jù)類型二叉樹的定義如下：ADT BinaryTree 數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系R:若D=，則R=，稱BinaryTree為空二叉樹；若D，則R=H,H是如下二元關(guān)系：（1） 在D中存在唯一的成為根的數(shù)據(jù)元素root，它在關(guān)系H中無前驅(qū)；（2） 若D-

23、root,則存在D-root=D1,Dr,且D1Dr=;（3） 若D1，則D1中存在唯一的元素X1，<root,X1>H，且存在D1上的關(guān)系H1包含于H；若Dr,則Dr中存在唯一的元素Xr，<root,Xr>H,且存在Dr上的關(guān)系屬于H；（4） （D，H1）是一棵符合本定義的二叉樹，稱為根的左子樹，（Dr，Hr）是一棵符合本定義的二叉樹，稱為根的右子樹。依據(jù)最小最小完備性和常用性相結(jié)合的原則，以函數(shù)形式定義了二叉樹的初始化、銷毀二叉樹、創(chuàng)建二叉樹、清空二叉樹、判定空二叉樹和求二叉樹深度等20種基本運(yùn)算，具體運(yùn)算功能定義如下：初始化二叉樹：函數(shù)名稱是InitBiTree(

24、T)；初始條件是二叉樹T不存在；操作結(jié)果是構(gòu)造空二叉樹T。銷毀二叉：樹函數(shù)名稱是DestroyBiTree(T)；初始條件是二叉樹T已存在；操作結(jié)果是銷毀二叉樹T。創(chuàng)建二叉樹：函數(shù)名稱是CreateBiTree(T,definition)；初始條件是definition 給出二叉樹T的定義；操作結(jié)果是按definition構(gòu)造二叉樹T。清空二叉樹：函數(shù)名稱是ClearBiTree (T)；初始條件是二叉樹T存在；操作結(jié)果是將二叉樹T清空。判定空二叉樹：函數(shù)名稱是BiTreeEmpty(T)；初始條件是二叉樹T存在；操作結(jié)果是若T為空二叉樹則返回TRUE，否則返回FALSE。求二叉樹深度：函數(shù)名

25、稱是BiTreeDepth(T)；初始條件是二叉樹T存在；操作結(jié)果是返回T的深度。獲得根結(jié)點(diǎn)：函數(shù)名稱是Root(T)；初始條件是二叉樹T已存在；操作結(jié)果是返回T的根。獲得結(jié)點(diǎn)：函數(shù)名稱是Value(T,e)；初始條件是二叉樹T已存在，e是T中的某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的值。結(jié)點(diǎn)賦值：函數(shù)名稱是Assign(T,&e,value)；初始條件是二叉樹T已存在，e是T中的某個(gè)結(jié)點(diǎn)；操作結(jié)果是結(jié)點(diǎn)e賦值為value。獲得雙親結(jié)點(diǎn)：函數(shù)名稱是Parent(T,e) ；初始條件是二叉樹T已存在，e是T中的某個(gè)結(jié)點(diǎn)；操作結(jié)果是若e是T的非根結(jié)點(diǎn)，則返回它的雙親結(jié)點(diǎn)指針，否則返回NULL。獲得左孩

26、子結(jié)點(diǎn)：函數(shù)名稱是LeftChild(T,e)；初始條件是二叉樹T存在，e是T中某個(gè)節(jié)點(diǎn)；操作結(jié)果是返回e的左孩子結(jié)點(diǎn)指針。若e無左孩子，則返回NULL。獲得右孩子結(jié)點(diǎn)：函數(shù)名稱是RightChild(T,e)；初始條件是二叉樹T已存在，e是T中某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的右孩子結(jié)點(diǎn)指針。若e無右孩子，則返回NULL。獲得左兄弟結(jié)點(diǎn)：函數(shù)名稱是LeftSibling(T,e)；初始條件是二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的左兄弟結(jié)點(diǎn)指針。若e是T的左孩子或者無左兄弟，則返回NULL。獲得右兄弟結(jié)點(diǎn)：函數(shù)名稱是RightSibling(T,e)；初始條件是二叉樹T已存在，e是T中某

27、個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的右兄弟結(jié)點(diǎn)指針。若e是T的右孩子或者無有兄弟，則返回NULL。插入子樹：函數(shù)名稱是InsertChild(T,p,LR,c)；初始條件是二叉樹T存在，p指向T中的某個(gè)結(jié)點(diǎn)，LR為0或1，,非空二叉樹c與T不相交且右子樹為空；操作結(jié)果是根據(jù)LR為0或者1，插入c為T中p所指結(jié)點(diǎn)的左或右子樹，p所指結(jié)點(diǎn)的原有左子樹或右子樹則為c的右子樹。刪除子樹：函數(shù)名稱是DeleteChild(T.p.LR)；初始條件是二叉樹T存在，p指向T中的某個(gè)結(jié)點(diǎn)，LR為0或1。操作結(jié)果是根據(jù)LR為0或者1，刪除c為T中p所指結(jié)點(diǎn)的左或右子樹。前序遍歷：函數(shù)名稱是PreOrderTraverse

28、(T,Visit()；初始條件是二叉樹T存在，Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)；操作結(jié)果：先序遍歷t，對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。中序遍歷：函數(shù)名稱是InOrderTraverse(T,Visit)；初始條件是二叉樹T存在，Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)；操作結(jié)果是中序遍歷t，對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。后序遍歷：函數(shù)名稱是PostOrderTraverse(T,Visit)；初始條件是二叉樹T存在，Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)；操作結(jié)果是后序遍歷t，對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失

29、敗。按層遍歷：函數(shù)名稱是LevelOrderTraverse(T,Visit)；初始條件是二叉樹T存在，Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)；操作結(jié)果是層序遍歷t，對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。2.1.3 演示系統(tǒng)與數(shù)據(jù)文件要求構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)。其中，在主函數(shù)中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示，并給出適當(dāng)?shù)牟僮魈崾尽８戒汚中給出了簡單菜單的框架。演示系統(tǒng)可選擇實(shí)現(xiàn)線性表的文件形式保存，演示系統(tǒng)可選擇實(shí)現(xiàn)多個(gè)線性表的管理。2.2 系統(tǒng)設(shè)計(jì)黑體4號加粗，間距前后0.5行2.2.1 數(shù)據(jù)物理結(jié)構(gòu)二叉樹的數(shù)據(jù)物理結(jié)構(gòu)如下：typedef s

30、truct BiTNode TElemType data;struct BiTNode *lchild, *rchild;/左右孩子指針int index;BiTNode,*BiTree;/typedef是將結(jié)構(gòu)類型定義struct BiTNode取別名為BiTNode2.2.2 演示系統(tǒng)將菜單演示和用戶選擇輸入寫入到while循環(huán)中，用op獲取用戶的選擇。Op初始化為1，以便第一次能進(jìn)入循環(huán)。進(jìn)入while循環(huán)后，系統(tǒng)首先顯示功能菜單，然后提示用戶輸入選擇（0-20），其中1-20對應(yīng)二叉樹的一個(gè)基本操作，分別對應(yīng)一個(gè)函數(shù)，通過switch語句將用戶輸入的序號對應(yīng)到相應(yīng)的函數(shù)功能，執(zhí)行完該語

31、句后break跳出switch語句，執(zhí)行while循環(huán)，直到用戶輸入0選擇退出，退出系統(tǒng)。圖2-1 系統(tǒng)設(shè)計(jì)結(jié)構(gòu)圖2.2.3 運(yùn)算算法思想與設(shè)計(jì)二叉樹運(yùn)算算法思想與設(shè)計(jì)如下：1、 初始化二叉樹算法思想：將初始化二叉樹過程寫成函數(shù)，函數(shù)的參數(shù)是主函數(shù)中所定義的結(jié)構(gòu)類型指針T（參數(shù)傳遞為引用方式，即取別名），T所指向的是二叉樹的根結(jié)點(diǎn)，將T賦值為NULL即完成了二叉樹的初始化。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(1)。2、 銷毀二叉樹算法思想：將二叉樹的銷毀過程寫成函數(shù)，函數(shù)的參數(shù)是指向二叉樹根結(jié)點(diǎn)的結(jié)構(gòu)類型指針T，采取遞歸的方式先銷毀二叉樹的左子樹，在銷毀二叉樹的右子樹，最后用free函數(shù)釋放掉根結(jié)

32、點(diǎn)對應(yīng)的內(nèi)存空間。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。3、 創(chuàng)建二叉樹算法思想：將二叉樹的創(chuàng)建過程寫成函數(shù)，函數(shù)的參數(shù)是指向二叉樹根結(jié)點(diǎn)的結(jié)構(gòu)類型指針T，按照先序次序輸入二叉樹中結(jié)點(diǎn)的值，如果第一個(gè)字符為#，則T為空二叉樹。否則，malloc函數(shù)分配一個(gè)單元的空間作為樹的根結(jié)點(diǎn)，并為其賦值，采取遞歸的方式繼續(xù)創(chuàng)建根結(jié)點(diǎn)的左子樹和右子樹。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。4、 清空二叉樹算法思想：將二叉樹的清空過程寫成函數(shù)，函數(shù)的參數(shù)同上，將根結(jié)點(diǎn)的左右孩子指針置為空，此時(shí)其左右子樹的存儲空間并未釋放掉。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(1)。5、 判定空二叉樹的算法思想：將判定空二叉樹寫成

33、函數(shù)，對于一個(gè)二叉樹，若根結(jié)點(diǎn)不存在則為空二叉樹，否則不是空二叉樹，那么只需要判斷指向根結(jié)點(diǎn)的結(jié)構(gòu)類型指針T是否為空即可。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(1)。6、 求二叉樹的深度算法思想：將求二叉樹的深度寫成函數(shù)，采取遞歸的方式求二叉樹的深度，如果根結(jié)點(diǎn)的左右孩子都不存在，則返回樹的深度為1，否則的話返回根結(jié)點(diǎn)左右子樹的深度的最大加上一。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。7、 獲得二叉樹根結(jié)點(diǎn)的算法思想：將求二叉樹根結(jié)點(diǎn)寫成函數(shù)，傳入頭結(jié)點(diǎn)，若其頭指針不為空，則返回該結(jié)點(diǎn)的關(guān)鍵字信息。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(1)。8、 獲得結(jié)點(diǎn)的算法思想是：將獲得關(guān)鍵字結(jié)點(diǎn)寫成函數(shù)，函數(shù)的參數(shù)是

34、二叉樹的頭指針以及主函數(shù)中輸入的關(guān)鍵字，通過遞歸先序遍歷二叉樹，即先比較根結(jié)點(diǎn)的關(guān)鍵字與給定是否一致，若一致，返回該結(jié)點(diǎn)的INDEX值，否則繼續(xù)分別遞歸遍歷其左子樹和右子樹。或者采取非遞歸的方式，即使用堆棧來存儲根結(jié)點(diǎn)的信息，先將根結(jié)點(diǎn)入棧，在循環(huán)中彈出棧頂元素，比較關(guān)鍵字，在分別將其右子樹和左子樹的根結(jié)點(diǎn)入棧。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。9、 結(jié)點(diǎn)賦值的算法思想是：將結(jié)點(diǎn)賦值寫成函數(shù)，函數(shù)的參數(shù)是二叉樹的頭指針，主函數(shù)中輸入的關(guān)鍵字，根據(jù)關(guān)鍵字獲取到根結(jié)點(diǎn)，并對根結(jié)點(diǎn)賦值，思想同8，不在贅述。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。10、 獲得雙親結(jié)點(diǎn)的算法思想是：將獲得雙親結(jié)點(diǎn)寫成

35、函數(shù)，函數(shù)的參數(shù)是二叉樹的頭指針，若頭指針為空，則返回空；否則，如果頭指針左孩子或右孩子不為空且關(guān)鍵字與給定關(guān)鍵字相同，返回根結(jié)點(diǎn)，如果不同，采取遞歸的方式調(diào)用原函數(shù)，傳入的參數(shù)分別為根結(jié)點(diǎn)的左右子樹的根結(jié)點(diǎn)。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。11、 獲得左兄弟結(jié)點(diǎn)的算法思想是：將獲得左孩子結(jié)點(diǎn)寫成函數(shù)，函數(shù)的參數(shù)是二叉樹的頭指針，如果頭指針為空，返回NULL；否則，如果二叉樹的根結(jié)點(diǎn)的右孩子關(guān)鍵字與給定關(guān)鍵字一致，返回根結(jié)點(diǎn)的左孩子。如果不一致，繼續(xù)遞歸調(diào)用原函數(shù)，傳入的參數(shù)為二叉樹根結(jié)點(diǎn)的左子樹的根結(jié)點(diǎn)指針，如果函數(shù)的返回值非空，則返回該值，否則繼續(xù)調(diào)用原函數(shù)，傳入的參數(shù)是二叉樹根結(jié)點(diǎn)

36、的右子樹的根結(jié)點(diǎn)指針，如果函數(shù)的返回值為非空，則返回該值，否則返回NULL。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。12、 獲得右兄弟結(jié)點(diǎn)的算法思想是:算法思想同上。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。13、 獲得左孩子結(jié)點(diǎn)的算法思想是：將獲得左孩子結(jié)點(diǎn)寫成函數(shù)，函數(shù)的參數(shù)是二叉樹的頭指針。如果根結(jié)點(diǎn)的關(guān)鍵字與給定關(guān)鍵字一致，且其左孩子存在，則返回其左孩子關(guān)鍵字，否則遞歸調(diào)用原函數(shù)分別將根結(jié)點(diǎn)的左右子樹根結(jié)點(diǎn)指針作為形參，若返回值非空則返回該值。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。14、 獲得右孩子結(jié)點(diǎn)的算法思想是：算法思想同上。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。15、 插入子樹的算法思

37、想是：將插入子樹寫成函數(shù)，函數(shù)的形參是二叉樹的頭指針T，指向特定二叉樹結(jié)點(diǎn)的指針p（在主函數(shù)中要求輸入關(guān)鍵字，通過FIND函數(shù)找到插入點(diǎn)位置并將其值記錄），再調(diào)用CreateBiTNode函數(shù)創(chuàng)建根結(jié)點(diǎn)c的右子樹為空的二叉樹，插入的過程即將P所指向結(jié)點(diǎn)的左子樹或者右子樹根結(jié)點(diǎn)指針賦值給c的右孩子指針域，而c賦值給p所指結(jié)點(diǎn)的左指針域或者右指針域。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。16、 刪除子樹的算法思想是：將刪除子樹寫成函數(shù)，函數(shù)的形參是二叉樹的頭指針，特定結(jié)點(diǎn)的指針，根據(jù)指向特定結(jié)點(diǎn)的指針找到給結(jié)點(diǎn)并將其左右孩子指針域置為空，對應(yīng)的還應(yīng)該在這之前調(diào)用DESTROY函數(shù)將其左子樹或右子樹

38、銷毀。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。17、 前序遍歷的算法思想是：將前序遍歷寫成函數(shù)，函數(shù)的形參是二叉樹的頭指針，首先訪問根結(jié)點(diǎn)，并對其執(zhí)行遍歷操作，操作成功后采取遞歸的方式遍歷根結(jié)點(diǎn)的左子樹，返回值為OK時(shí)繼續(xù)遍歷其右子樹，最終遍歷完成。遞歸方法前序遍歷、中序遍歷以及后序遍歷的根本區(qū)別在與訪問根結(jié)點(diǎn)的操作是在兩次遞歸操作之間之前還是之后。經(jīng)分許，該算法的時(shí)間復(fù)雜度為O(n)。18、 非遞歸前序遍歷的算法思想是：將非遞歸前序遍歷寫成函數(shù)，函數(shù)的形參是二叉樹的頭指針，仿照遞歸過程堆棧的使用，首先將根結(jié)點(diǎn)的值壓入堆棧，執(zhí)行循環(huán)體，堆棧非空，彈出根結(jié)點(diǎn)并執(zhí)行訪問操作，將其右子樹根結(jié)點(diǎn)指針壓入

39、堆棧，再將其左子樹根結(jié)點(diǎn)指針壓入堆棧，執(zhí)行循環(huán)。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。19、 非遞歸中序遍歷的算法思想是：將非遞歸中序遍歷寫成函數(shù)，函數(shù)的形參是二叉樹的頭指針，首先將根結(jié)點(diǎn)的值壓入堆棧，然后一直向左，將根結(jié)點(diǎn)依次壓入堆棧，判斷堆棧非空，將棧頂元素彈出，訪問該結(jié)點(diǎn)，如果其右子樹非空，對其右子樹執(zhí)行循環(huán)操作。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。20、 層序遍歷的算法思想是：將層序遍歷寫成函數(shù)，函數(shù)的形參是二叉樹的頭指針，借助隊(duì)列，使根結(jié)點(diǎn)進(jìn)入隊(duì)列，根結(jié)點(diǎn)出隊(duì)列，執(zhí)行訪問操作，此時(shí)將根結(jié)點(diǎn)的左右子樹根結(jié)點(diǎn)依次進(jìn)入隊(duì)列，即隊(duì)列中的某個(gè)元素出隊(duì)列時(shí)將其左右子樹根結(jié)點(diǎn)放進(jìn)隊(duì)列，循環(huán)即可一

40、層一層的訪問二叉樹。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。2.3 系統(tǒng)實(shí)現(xiàn)黑體4號加粗，間距前后0.5行2.3.1 編程環(huán)境、運(yùn)行環(huán)境、項(xiàng)目工程描述本次實(shí)驗(yàn)采用Microsoft Visual Studio 2015編程軟件編寫，并用VS2015進(jìn)行編譯運(yùn)行，項(xiàng)目名稱是BinaryTree。2.3.2 頭文件及預(yù)定義常量說明1、頭文件#include <stdio.h>#include <malloc.h>#include <stdlib.h>2、預(yù)定義常量（1）函數(shù)結(jié)果狀態(tài)宏定義#define TRUE 1#define FALSE 0#define OK

41、 1#define ERROR 0#define OVERFLOW -2（2）類型表達(dá)式typedef int status;typedef char TElemType;typedef BiTree QElemType;（3）系統(tǒng)常量定義#define MAXLENG 10#define MAXSIZE 2#define QMAXSIZE 52.3.3 演示系統(tǒng)操作1.系統(tǒng)一開始會(huì)顯示功能菜單并提示用戶輸入選擇。圖2-2 演示系統(tǒng)操作圖12.輸入序號020，會(huì)執(zhí)行序號所對應(yīng)的操作。圖2-3 演示系統(tǒng)操作圖23.輸入序號0，演示系統(tǒng)結(jié)束并退出。圖2-3 演示系統(tǒng)操作圖32.3.4 測試計(jì)劃測試

42、功能及序號輸入函數(shù)的參數(shù)預(yù)計(jì)輸出此時(shí)二叉樹的狀態(tài)1.InitBiTree無二叉樹創(chuàng)建成功二叉樹根結(jié)點(diǎn)指針置為空，未分配具體的存儲空間2.DestroyBiTree無二叉樹銷毀失敗二叉樹頭指針置為空，對應(yīng)的存儲空間被釋放3.CreateBiTree依次輸入關(guān)鍵字及其對應(yīng)值：A1 B9 D7 #E0H1#I2#C9F6#G2#J0#二叉樹創(chuàng)建成功按照輸入關(guān)鍵字的先序序列創(chuàng)建二叉樹，每個(gè)結(jié)點(diǎn)賦值4.ClearBiTree無二叉樹清空成功二叉樹根結(jié)點(diǎn)保留，但其左右指針域置為空5.BiTreeEmpty無二叉樹不為空同上36.BiTreeDepth無二叉樹的深度為4同上37.Root無二叉樹的根結(jié)點(diǎn)關(guān)鍵

43、字為A同上38.Value輸入關(guān)鍵字為D輸出關(guān)鍵字為D的結(jié)點(diǎn)值為7同上39.Assign輸入關(guān)鍵字E輸入關(guān)鍵字為E的結(jié)點(diǎn)的值改為9輸出關(guān)鍵字為E的結(jié)點(diǎn)的值已改為9同上310.Parent輸入查找關(guān)鍵字為I的結(jié)點(diǎn)輸出關(guān)鍵字為I的結(jié)點(diǎn)的雙親結(jié)點(diǎn)為E同上311.LeftChild(測試1)輸入查找關(guān)鍵字為E的結(jié)點(diǎn)輸出關(guān)鍵字為E的結(jié)點(diǎn)的左孩子為H同上312.LeftChild（測試2）輸入查找關(guān)鍵字為F的結(jié)點(diǎn)輸出關(guān)鍵字為F的左孩子不存在，查找失敗同上313.RightChild（測試1）輸入查找關(guān)鍵字為B的結(jié)點(diǎn)輸出關(guān)鍵字為B的結(jié)點(diǎn)右孩子為E同上314.RightChild（測試2）輸入查找關(guān)鍵字為F的

44、結(jié)點(diǎn)輸出關(guān)鍵字為F的右孩子不存在，操作失敗同上315.LeftSibling（測試1）輸入查找關(guān)鍵字為G的結(jié)點(diǎn)輸出關(guān)鍵字為G的結(jié)點(diǎn)左孩子為F同上315.LeftSibling（測試2）輸入查找關(guān)鍵字為B的結(jié)點(diǎn)輸出關(guān)鍵字為B的結(jié)點(diǎn)左孩子不存在，操作失敗同上316.InsertChild輸入LR值為0，輸入查找關(guān)鍵字為J，新生成右子樹為空的二叉樹輸入：M1N2#K3#（字母后為該關(guān)鍵字結(jié)點(diǎn)的值）輸出二叉樹插入成功在原二叉樹的基礎(chǔ)上，將新生成二叉樹作為關(guān)鍵字為J的結(jié)點(diǎn)的左子樹，J的左子樹作為新生成二叉樹的右子樹17.DeleteChild輸入查找關(guān)鍵字為E的結(jié)點(diǎn)，輸入LR值為1輸出二叉樹刪除成功在上

45、一基礎(chǔ)上，將原二叉樹的E結(jié)點(diǎn)的右子樹刪除18.PreOrderTraverse無輸出先序遍歷序列：ABDEHICFGJ同上319.InOrderTraverse無輸出中序遍歷序列：DBHEIAFCGJ同上320.PostOrderTraverse無輸出后續(xù)遍歷序列：DHIEBFJGCA同上321.LevelTraverse無輸出層序遍歷序列：ABCDEFGHIJ同上3表2-1 測試計(jì)劃圖2-4 按以上測試用例生成的原始二叉樹2.3.5 測試1.執(zhí)行功能1.InitBiTree，測試結(jié)果如圖2-5所示。圖2-5 初始化二叉樹測試2.執(zhí)行功能3，創(chuàng)建二叉樹，測試結(jié)果如圖2-6所示。圖2-6 二叉樹

46、創(chuàng)建3.在上一步的基礎(chǔ)上對二叉樹的結(jié)構(gòu)進(jìn)行驗(yàn)證，根據(jù)其前序遍歷、中序遍歷、后續(xù)遍歷的結(jié)果是否與預(yù)期一致判斷結(jié)構(gòu)是否正確。執(zhí)行功能17，先序遍歷二叉樹，并執(zhí)行PRINT操作，測試結(jié)果如圖2-7所示。圖2-7 先序遍歷二叉樹的測試結(jié)果4.執(zhí)行功能18，中序遍歷二叉樹，并執(zhí)行PRINT操作，測試結(jié)果如圖2-8所示。圖2-8 中序遍歷二叉樹的測試結(jié)果5.執(zhí)行功能19，后序遍歷二叉樹，測試結(jié)果如圖2-9所示。圖2-9 后序遍歷二叉樹的測試結(jié)果6.執(zhí)行功能20，層序遍歷二叉樹，測試結(jié)果如圖2-10所示。圖2-10 層序遍歷二叉樹的測試結(jié)果上述測試與預(yù)期的遍歷結(jié)果是一致的，說明生成二叉樹的結(jié)構(gòu)正確性，即生成

47、了如圖2-4所示的二叉樹。7.執(zhí)行功能5，判斷二叉樹是否為空樹，測試結(jié)果如圖2-11所示。圖2-11 判斷二叉樹是否為空測試結(jié)果8.執(zhí)行功能6，求二叉樹的深度，測試結(jié)果如圖2-12所示。圖2-12 求二叉樹深度測試結(jié)果9.執(zhí)行功能7，求二叉樹的根結(jié)點(diǎn)，測試結(jié)果如圖2-13所示。圖2-13 求二叉樹根結(jié)點(diǎn)的測試結(jié)果10.執(zhí)行功能8，求關(guān)鍵字為D的結(jié)點(diǎn)的值，測試結(jié)果如圖2-14所示。圖2-14 求二叉樹指定結(jié)點(diǎn)的值測試結(jié)果11.執(zhí)行功能9，將關(guān)鍵字為E的結(jié)點(diǎn)值改為9，測試結(jié)果如圖2-15所示。圖2-15 對指定結(jié)點(diǎn)重新賦值測試結(jié)果12.執(zhí)行功能11，輸入查找關(guān)鍵字為E的結(jié)點(diǎn)的左孩子，測試結(jié)果如圖2

48、-16所示。圖2-16 查找左孩子的測試結(jié)果113.執(zhí)行功能11，測試關(guān)鍵字為F的結(jié)點(diǎn)的左孩子，測試結(jié)果如圖2-17所示。圖2-17 查找左孩子的測試結(jié)果214.執(zhí)行功能10，查找關(guān)鍵字為I的結(jié)點(diǎn)的雙親結(jié)點(diǎn)，測試結(jié)果如圖2-18所示。圖2-18 查找結(jié)點(diǎn)的雙親結(jié)點(diǎn)15.執(zhí)行功能13，查找關(guān)鍵字為E的結(jié)點(diǎn)的左兄弟，查找結(jié)果如圖2-19所示。圖2-19 查找結(jié)點(diǎn)的左兄弟測試結(jié)果116.執(zhí)行功能13，查找關(guān)鍵字為B的結(jié)點(diǎn)的左兄弟，查找結(jié)果如圖2-20所示。圖2-20 查找結(jié)點(diǎn)的左兄弟測試結(jié)果217.執(zhí)行功能15，在原二叉樹的基礎(chǔ)上插入子樹，測試結(jié)果如圖2-21所示。圖2-21 插入子樹的測試結(jié)果插入

49、子樹后，先序遍歷得到的序列為：ABDEHICFGJMNK,層序遍歷得到的序列應(yīng)該為：ABCDEFGHIJMNK，中序遍歷得到的序列為：DBHEIAFCGNKMJ。通過遍歷新生成的二叉樹驗(yàn)證其結(jié)構(gòu)正確性。圖2-22 先序遍歷的測試結(jié)果圖2-23 層序遍歷的測試結(jié)果圖2-24 后序遍歷的測試結(jié)果以上遍歷結(jié)果與預(yù)期相吻合，說明插入后得到的新二叉樹滿足結(jié)構(gòu)正確性。18.執(zhí)行功能16，刪除關(guān)鍵字為E的結(jié)點(diǎn)的右子樹，即I結(jié)點(diǎn)，測試結(jié)果如圖2-25所示。圖2-25 刪除子樹的測試結(jié)果未驗(yàn)證結(jié)果的正確性，若對其先序遍歷得到的序列應(yīng)該為：ABDEHCFGJMNK，層序遍歷得到的序列應(yīng)該為：ABCDEFGHJMN

50、K，中序遍歷得到的結(jié)果應(yīng)該為：DBHEAFCGNKMJ圖2-26 先序遍歷的測試結(jié)果圖2-27 中序遍歷的測試結(jié)果圖2-28 層序遍歷的測試結(jié)果上面的測試結(jié)果與預(yù)期相一致，說明刪除子樹后結(jié)構(gòu)的正確性，函數(shù)功能執(zhí)行正確。19.執(zhí)行功能2，刪除二叉樹，此時(shí)銷毀二叉樹的存儲空間，頭指針置為空，測試結(jié)果如圖2-29所示。圖2-29 銷毀二叉樹的測試結(jié)果二叉樹銷毀后，進(jìn)行判斷是否為空，應(yīng)該返回空樹，測試結(jié)果如圖2-30所示。圖2-30 驗(yàn)證二叉樹為空2.4 實(shí)驗(yàn)小結(jié)黑體4號加粗，間距前后0.5行通過本次實(shí)驗(yàn)，熟悉了二叉樹的基本操作，學(xué)會(huì)了用二叉樹去解決一些問題，學(xué)習(xí)中的主要收獲為以下幾點(diǎn)：1、 加深了對

51、二叉樹的概念和邏輯結(jié)構(gòu)的理解。2、 掌握了二叉樹的基本操作。3、 通過遞歸算法的編寫加深了對遞歸的認(rèn)識和理解。4、 通過非遞歸算法的編寫加深了對遞歸內(nèi)在機(jī)制的分析以及學(xué)會(huì)了如何用堆棧去代替遞歸達(dá)到相同的目的。5、 規(guī)范了報(bào)告撰寫能力。參考文獻(xiàn)黑體小2號加粗居中，間距前后0.5行1 嚴(yán)蔚敏等. 數(shù)據(jù)結(jié)構(gòu)(C語言版). 清華大學(xué)出版社2 Larry Nyhoff. ADTs, Data Structures, and Problem Solving with C+.  Second Edition, Calvin College, 2005 3 殷立峰. Qt C+跨平臺圖形界面程序設(shè)計(jì)

52、基礎(chǔ). 清華大學(xué)出版社,2014:1921974 嚴(yán)蔚敏等.數(shù)據(jù)結(jié)構(gòu)題集(C語言版). 清華大學(xué)出版社宋體小4號，行間距1.5倍指導(dǎo)教師評定意見黑體小2加粗居中，間距前后0.5行，另起頁一、對實(shí)驗(yàn)報(bào)告的評語二、對實(shí)驗(yàn)報(bào)告評分評分項(xiàng)目(分值)程序內(nèi)容(36.8分)程序規(guī)范(9.2分)報(bào)告內(nèi)容(36.8分)報(bào)告規(guī)范(9.2分)考勤（8分）逾期扣分合 計(jì)(100分)得分附錄A 基于順序存儲結(jié)構(gòu)線性表實(shí)現(xiàn)的源程序黑體小2加粗居中，間距前后0.5行，另起頁#include <stdio.h>#include <malloc.h>#include <stdlib.h>#

53、define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASTABLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int status;typedef int ElemType;typedef struct ElemType * elem;int length;int listsize;SqList;status Initlist(SqList &L) L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZE;return OK;/InitList_Sqstatus DestroyList(SqList &L) if (L.elem != NULL) free(L.