1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)二根據(jù)二叉樹的抽象數(shù)據(jù)類型的定義，使用二叉鏈表實(shí)現(xiàn)一個(gè)二叉樹學(xué)生姓名： 郭江楓班 級： 2017211125班內(nèi)序號： 10學(xué) 號： 2017210722日 期： 2018年5月24日1實(shí)驗(yàn)要求根據(jù)二叉樹的抽象數(shù)據(jù)類型的定義，使用二叉鏈表實(shí)現(xiàn)一個(gè)二叉樹基本要求：根據(jù)二叉樹的抽象數(shù)據(jù)類型的定義，使用二叉鏈表實(shí)現(xiàn)一個(gè)二叉樹。 二叉樹的基本功能：1、二叉樹的建立2、前序遍歷二叉樹3、中序遍歷二叉樹4、后序遍歷二叉樹5、按層序遍歷二叉樹6、求二叉樹的深度7、求指定結(jié)點(diǎn)到根的路徑8、二叉樹的銷毀9、其他：自定義操作編寫測試main()函數(shù)測試線性表的正確性2. 程序分析2

2、.1 存儲結(jié)構(gòu) 編碼表存儲結(jié)構(gòu)：二叉樹二叉鏈表示例如圖：lrcdatarchlrcdatarchlrcdatarchlrcdatarchlrcdatarchlrcdatarchlrcdatarch二叉樹結(jié)點(diǎn)結(jié)構(gòu): templatestruct node/定義結(jié)點(diǎn)T data;/數(shù)據(jù)node*lch;/左孩子node*rch;/右孩子;2.2 關(guān)鍵算法分析實(shí)現(xiàn)該項(xiàng)目需要有如下步驟：步驟一：創(chuàng)建二叉樹步驟二：前序遍歷步驟三：中序遍歷步驟四：后序遍歷步驟五：層序遍歷步驟六：計(jì)算樹的深度步驟七：求指定結(jié)點(diǎn)到根的路徑步驟八：二叉樹的銷毀步驟一：根據(jù)順序存儲結(jié)構(gòu)和性質(zhì)5，可知如果當(dāng)前節(jié)點(diǎn)的位置為i，則左孩

3、子位置為2i，右孩子為2i+1.所以，創(chuàng)建二叉樹以順序存儲結(jié)構(gòu)為輸入，采用先建立根結(jié)點(diǎn)，再建立左右孩子的方法遞歸建立二叉鏈表的二叉樹。templatevoid creat(node*&R, T data, int i, int n)/創(chuàng)建二叉樹if (i = n&datai - 1)/如果n個(gè)數(shù)據(jù)沒有存儲完并且數(shù)據(jù)不為空R = new node;/定義一個(gè)新結(jié)點(diǎn)R-data = datai - 1;/將第i個(gè)數(shù)據(jù)賦給R的datacreat(R-lch, data, 2 * i, n);/遞歸，建立左子樹creat(R-rch, data, 2 * i + 1, n);/遞歸，建立右子樹else

4、 R = NULL;/如果不滿足，則為空步驟二：由二叉樹的前序遍歷定義，結(jié)合遞歸，寫出前序遍歷的遞歸算法。templatevoid preorder(node*R)/前序遍歷if (R != NULL)/如果R不為空，則執(zhí)行以下操作cout data;/輸出R的數(shù)據(jù)preorder(R-lch);/遍歷左子樹preorder(R-rch);/遍歷右子樹 步驟三：由二叉樹的中序遍歷定義，結(jié)合遞歸，寫出中序遍歷的遞歸算法。templatevoid inorder(node*R)/中序遍歷if (R != NULL)/如果R不為空，則執(zhí)行以下操作inorder(R-lch);/遍歷左子樹cout d

5、ata;/輸出R的數(shù)據(jù)inorder(R-rch);/遍歷右子樹步驟四： 由二叉樹的后序遍歷定義，結(jié)合遞歸，寫出后序遍歷的遞歸算法。templatevoid postorder(node*R)/后序遍歷if (R != NULL)/如果R不為空，則執(zhí)行以下操作postorder(R-lch);/遍歷左子樹postorder(R-rch);/遍歷右子樹cout data;/輸出R的數(shù)據(jù)步驟五：在進(jìn)行層序遍歷時(shí)，對某一層的結(jié)點(diǎn)訪問完畢后，在按照它們的訪問次序?qū)Ω鱾€(gè)結(jié)點(diǎn)的左孩子和右孩子順序訪問，這樣一層一層進(jìn)行，先訪問的結(jié)點(diǎn)其左右孩子也要先訪問，這與隊(duì)列的特性比較吻合。因此，我們可以利用隊(duì)列來實(shí)現(xiàn)二

6、叉鏈表的層序遍歷。templatevoid levelorder(node*R)/層序遍歷node*queue1000;int f = 0, r = 0;/初始化空隊(duì)列if (R != NULL)queue+r = R;/根結(jié)點(diǎn)入隊(duì)while (f != r)node*p = queue+f;/隊(duì)頭元素出隊(duì)cout data;/輸出隊(duì)頭元素if (p-lch != NULL)queue+r = p-lch;/如果左子樹不為空，則將左子樹元素入隊(duì)if (p-rch != NULL)queue+r = p-rch;/如果右子樹不為空，則將右子樹元素入隊(duì)步驟六：結(jié)合遞歸函數(shù)分別依次遍歷左右子樹，并在

7、每次某結(jié)點(diǎn)的左右孩子均為空時(shí)返回他的深度，然后進(jìn)行左右子樹的比較，選取大的那個(gè)數(shù)作為樹的深度templateint count(node*R)/計(jì)算樹的深度if (R = NULL)return 0;/如果結(jié)點(diǎn)為空，則返回0elseint m = count(R-lch);/遍歷左子樹int n = count(R-rch);/遍歷右子樹return m = n ? m + 1 : n + 1;/返回m和n中較大的樹步驟七：通過遞歸判斷尋找我們要找的那個(gè)數(shù)據(jù)，找到后返回一個(gè)true，并且輸出該數(shù)據(jù)，由于要判斷，所以要使用bool函數(shù)templatebool road(node *R, T a)

8、if (R = NULL)/如果R為空，則返回falsereturn false;if (R-data = a | road(R-lch, a) | road(R-rch, a)/如果R的數(shù)據(jù)為a或者R的左子樹有a或者R的右子樹有a，則執(zhí)行下一步cout data; /路徑上的結(jié)點(diǎn)標(biāo)識打印出來return true;return false;步驟八：二叉鏈表屬于動態(tài)的存儲分配，需要在析構(gòu)函數(shù)中釋放二叉鏈表的所有結(jié)點(diǎn)。為了防止內(nèi)存泄露，釋放結(jié)點(diǎn)應(yīng)該先釋放該結(jié)點(diǎn)的左右子樹，左右子樹全部釋放完畢后再釋放結(jié)點(diǎn)，采用后序遍歷的方法templatevoid releae(node*R)/銷毀二叉樹if (R != NULL)releae(R-lch);/遞歸左子樹releae(R-rch);/遞歸右子樹delete R;/delete掉結(jié)點(diǎn)時(shí)間復(fù)雜度：O（n） 空間復(fù)雜度：O（n2）2.3 其他此實(shí)驗(yàn)主要是遞歸和隊(duì)列的應(yīng)用，在鏈表的基礎(chǔ)上創(chuàng)建一棵二叉樹并進(jìn)行一系列操作。開始3. 程序運(yùn)行結(jié)果創(chuàng)建二叉樹計(jì)算樹的深度用戶輸入要找的數(shù)據(jù)前序遍歷中序遍歷尋找數(shù)據(jù)并打印路徑層序遍歷銷毀二叉樹結(jié)束測試條件：任意輸入一個(gè)存儲好的數(shù)據(jù)本次實(shí)