實(shí)驗(yàn)報(bào)告-數(shù)據(jù)結(jié)構(gòu)與算法

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