實驗報告-數(shù)據(jù)結(jié)構(gòu)與算法

實驗報告課程名稱數(shù)據(jù)結(jié)構(gòu)與算法實驗學(xué)期2015年春季學(xué)期所在學(xué)院交通科學(xué)與工程學(xué)院所屬專業(yè)交通信息與控制工程系年級2012專業(yè)班級學(xué)生姓名學(xué)號指導(dǎo)教師實驗最終成績實驗報告（三）實驗題目二叉樹的基本操作及應(yīng)用實驗時間2015年6月10日實驗地點B07-B214實驗成績實驗性質(zhì)□應(yīng)用性□設(shè)計性□綜合性教師評閱：評閱教師簽名：一、實驗?zāi)康?熟悉二叉樹的存儲結(jié)構(gòu)和對二叉樹的基本操作。2掌握對二叉樹前序、中序、后序遍歷操作的具體實現(xiàn)。3學(xué)習(xí)利用遞歸方法編寫對二叉樹這種遞歸數(shù)據(jù)結(jié)構(gòu)進行處理的算法。4會應(yīng)用二叉樹的基本操作解決簡單的實際問題二、實驗內(nèi)容和要求(說明算法的時間復(fù)雜度)1基于二叉鏈表的存儲格式，輸入二叉樹的先序序列，用*代表空節(jié)點，如ABD**CE**F**建立二叉樹，然后中序遍歷二叉樹，輸出節(jié)點的值。2針對建好的二叉樹，編寫遞歸程序，求樹中葉子節(jié)點個數(shù)。3針對建好的二叉樹，編寫遞歸程序，求二叉樹的高度。4針對建好的二叉樹，試編寫二叉樹的前序非遞歸遍歷算法。4.這是用非遞歸實現(xiàn)先序遍歷的voidPreOrder(TreeT){StackS; Treep; InitStack(&S);//造一個棧待會兒用 p=T;//用p指針來不斷處理結(jié)點操作while(p||!IsEmpty(S)) {while(p) { printf("%c",p->element);//只要不空則把p指的數(shù)據(jù)輸出 Push(&S,p);p=p->lchild;//繼續(xù)往左邊找 }//一旦停下來說明找到了空結(jié)點，則開始往上一層的右邊找一下 if(!IsEmpty(S)) {//棧非空 p=Pop(&S);//退棧，找到剛才說的上一層 p=p->rchild;//找右邊了 } }//只要while還循環(huán)說明沒有遍歷完，現(xiàn)在再一次從剛才的右邊執(zhí)行先序遍歷};四、實驗結(jié)果（設(shè)計文檔、文稿存放路徑，可以截圖描述實驗結(jié)果）#include<stdio.h>#include"3.h"intmain(void)//改主程序?qū)?yīng)上圖結(jié)果{ TreepTree; inti,j; pTree=CreateBTree();//創(chuàng)建二叉樹pTree i=CountLeaf(pTree); printf("Thereare%dleaves!",i);//遞歸程序數(shù)葉節(jié)點 j=CountLevel(pTree); printf("Thereare%dlevels!",j);//遞歸程序數(shù)層數(shù) PreOrder(pTree);//按照前序遍歷輸出該書的元素 return0;}五、實驗分析總結(jié)本次實驗采用二叉樹存儲了一系列的字符串，通過函數(shù)TreeCreateBTree(void)得到一個根據(jù)輸入創(chuàng)建的二叉樹結(jié)構(gòu)，時間復(fù)雜度是O（n）；通過函數(shù)intCountLeaf(TreeT)遞歸返回葉子個數(shù)，時間復(fù)雜度O(n)；通過intCountLevel(TreeT)返回最深路徑得到樹的深度，時間復(fù)雜度O（n）；；最后用voidPreOrder(TreeT)實現(xiàn)非遞歸寫法的二叉樹先序遍歷，時間復(fù)雜度為O(n).綜上所述，因為都是要遍歷B數(shù)的每個節(jié)點，所以程序執(zhí)行的時間長度和輸入的字符串長度n是線性增長的。他們的時間復(fù)雜度都是O(n).這次實驗，我更深刻的理解了B數(shù)的基本性質(zhì)如遞歸性，利用遞歸，我們可以很方便的寫出各種對樹的操作；熟悉了創(chuàng)建樹，遍歷樹的基本方法；體會了算法的代碼實現(xiàn)細節(jié)。最后，特別是在用非遞歸方法實現(xiàn)遍歷的函數(shù)中，我更加深刻的理解到了數(shù)是如何遍