實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)報(bào)告（三）實(shí)驗(yàn)題目二叉樹的基本操作及應(yīng)用實(shí)驗(yàn)時(shí)間6月10日實(shí)驗(yàn)地點(diǎn)B07-B214實(shí)驗(yàn)成績實(shí)驗(yàn)性質(zhì)□應(yīng)用性□設(shè)計(jì)性□綜合性教師評閱：評閱教師簽名：一、實(shí)驗(yàn)?zāi)康?熟悉二叉樹的存儲構(gòu)造和對二叉樹的基本操作。2掌握對二叉樹前序、中序、后序遍歷操作的具體實(shí)現(xiàn)。3學(xué)習(xí)運(yùn)用遞歸辦法編寫對二叉樹這種遞歸數(shù)據(jù)構(gòu)造進(jìn)行解決的算法。4會應(yīng)用二叉樹的基本操作解決簡樸的實(shí)際問題二、實(shí)驗(yàn)內(nèi)容和規(guī)定(闡明算法的時(shí)間復(fù)雜度)1基于二叉鏈表的存儲格式，輸入二叉樹的先序序列，用*代表空節(jié)點(diǎn)，如ABD**CE**F**建立二叉樹，然后中序遍歷二叉樹，輸出節(jié)點(diǎn)的值。2針對建好的二叉樹，編寫遞歸程序，求樹中葉子節(jié)點(diǎn)個數(shù)。3針對建好的二叉樹，編寫遞歸程序，求二叉樹的高度。4針對建好的二叉樹，試編寫二叉樹的前序非遞歸遍歷算法。三、重要設(shè)計(jì)思想與算法（此處不夠可加頁，或在背面書寫）該實(shí)驗(yàn)重要涉及一下幾個函數(shù)，算法核心分別在各函數(shù)中。建立樹的構(gòu)造。typedef structBiTNode{ charelement; Treelchild,rchild;};//B數(shù)的基本結(jié)點(diǎn)輸入ABD**CE**F***TreeCreateBTree(void)//能夠返回一種Tree指針{ TreepTree; charval; scanf("%c",&val); printf("%c",val); if(val=='*'||val=='^p')returnNULL;//根據(jù)輸入字符先序建樹 else//*代表空 { pTree=(Tree)malloc(sizeof(structBiTNode)); if(pTree==NULL) { printf("內(nèi)存分派失??！"); exit(-1);//避免程序不懂得空間不夠用了 } pTree->element=val; pTree->lchild=CreateBTree(); pTree->rchild=CreateBTree();//遞歸，NLR地創(chuàng)立結(jié)點(diǎn) } returnpTree;};數(shù)葉結(jié)點(diǎn)個數(shù)intCountLeaf(TreeT){ if(T==NULL)return0; if(!T->lchild&&!T->rchild) { return1;//兩個兒子都空則闡明是葉子，返回1 } else { returnCountLeaf(T->lchild)+CountLeaf(T->rchild);//數(shù)左右子樹總共的葉結(jié)點(diǎn) } };3.數(shù)樹的深度intCountLevel(TreeT){ if(!T)return0; else { intLeft=CountLevel(T->lchild);intRight=CountLevel(T->rchild); return1+(Left>Right?Left:Right);//三目運(yùn)算取最大 }};//最后數(shù)得樹的最深層數(shù)，也是遞歸typedefstruct{ Treeelements[MAXSIZE];//注意這里放的是指針 inttop;}Stack;//這是一種用于裝Tree指針的棧4.這是用非遞歸實(shí)現(xiàn)先序遍歷的voidPreOrder(TreeT){StackS; Treep; InitStack(&S);//造一種棧待會兒用 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)成果（設(shè)計(jì)文檔、文稿寄存途徑，能夠截圖描述實(shí)驗(yàn)成果）#include<stdio.h>#include"3.h"intmain(void)//改主程序?qū)?yīng)上圖成果{ 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)采用二叉樹存儲了一系列的字符串，通過函數(shù)TreeCreateBTree(void)得到一種根據(jù)輸入創(chuàng)立的二叉樹構(gòu)造，時(shí)間復(fù)雜度是O（n）；通過函數(shù)intCountLeaf(TreeT)遞歸返回葉子個數(shù)，時(shí)間復(fù)雜度O(n)；通過intCountLevel(TreeT)返回最深途徑得到樹的深度，時(shí)間復(fù)雜度O（n）；；最后用voidPreOrder(TreeT)實(shí)現(xiàn)非遞歸寫法的二叉樹先序遍歷，時(shí)間復(fù)雜度為O(n).總而言之，由于都是要遍歷B數(shù)的每個節(jié)點(diǎn)，因此程序執(zhí)行的時(shí)間長度和輸入的字符串長度n是線性增加的。他們的時(shí)間復(fù)雜度都是O(n).這次實(shí)驗(yàn)，我更深刻的理解了B數(shù)的基本性質(zhì)如遞歸性，運(yùn)用遞歸，我們能夠很方便的寫出多個對樹的操作；熟悉了創(chuàng)立樹，遍歷樹的基本辦法；體會了算法的代碼實(shí)現(xiàn)