二叉樹(shù)的基本操作及應(yīng)用

實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)報(bào)告（三）實(shí)驗(yàn)題目二叉樹(shù)的基本操作及應(yīng)用實(shí)驗(yàn)時(shí)間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)康?熟悉二叉樹(shù)的存儲(chǔ)構(gòu)造和對(duì)二叉樹(shù)的基本操作。2掌握對(duì)二叉樹(shù)前序、中序、后序遍歷操作的具體實(shí)現(xiàn)。3學(xué)習(xí)運(yùn)用遞歸辦法編寫(xiě)對(duì)二叉樹(shù)這種遞歸數(shù)據(jù)構(gòu)造進(jìn)行解決的算法。4會(huì)應(yīng)用二叉樹(shù)的基本操作解決簡(jiǎn)樸的實(shí)際問(wèn)題二、實(shí)驗(yàn)內(nèi)容和規(guī)定(闡明算法的時(shí)間復(fù)雜度)1基于二叉鏈表的存儲(chǔ)格式，輸入二叉樹(shù)的先序序列，用*代表空節(jié)點(diǎn)，如ABD**CE**F**建立二叉樹(shù)，然后中序遍歷二叉樹(shù)，輸出節(jié)點(diǎn)的值。2針對(duì)建好的二叉樹(shù)，編寫(xiě)遞歸程序，求樹(shù)中葉子節(jié)點(diǎn)個(gè)數(shù)。3針對(duì)建好的二叉樹(shù)，編寫(xiě)遞歸程序，求二叉樹(shù)的高度。4針對(duì)建好的二叉樹(shù)，試編寫(xiě)二叉樹(shù)的前序非遞歸遍歷算法。三、重要設(shè)計(jì)思想與算法（此處不夠可加頁(yè)，或在背面書(shū)寫(xiě)）該實(shí)驗(yàn)重要涉及一下幾個(gè)函數(shù)，算法核心分別在各函數(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ù)輸入字符先序建樹(shù) 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)個(gè)數(shù)intCountLeaf(TreeT){ if(T==NULL)return0; if(!T->lchild&&!T->rchild) { return1;//兩個(gè)兒子都空則闡明是葉子，返回1 } else { returnCountLeaf(T->lchild)+CountLeaf(T->rchild);//數(shù)左右子樹(shù)總共的葉結(jié)點(diǎn) } };3.數(shù)樹(shù)的深度intCountLevel(TreeT){ if(!T)return0; else { intLeft=CountLevel(T->lchild);intRight=CountLevel(T->rchild); return1+(Left>Right?Left:Right);//三目運(yùn)算取最大 }};//最后數(shù)得樹(shù)的最深層數(shù)，也是遞歸typedefstruct{ Treeelements[MAXSIZE];//注意這里放的是指針 inttop;}Stack;//這是一種用于裝Tree指針的棧4.這是用非遞歸實(shí)現(xiàn)先序遍歷的voidPreOrder(TreeT){StackS; Treep; InitStack(&S);//造一種棧待會(huì)兒用 p=T;//用p指針來(lái)不停解決結(jié)點(diǎn)操作while(p||!IsEmpty(S)) {while(p) { printf("%c",p->element);//只要不空則把p指的數(shù)據(jù)輸出 Push(&S,p);p=p->lchild;//繼續(xù)往左邊找 }//一旦停下來(lái)闡明找到了空結(jié)點(diǎn)，則開(kāi)始往上一層的右邊找一下 if(!IsEmpty(S)) {//棧非空 p=Pop(&S);//退棧，找到剛剛說(shuō)的上一層 p=p->rchild;//找右邊了 } }//只要while還循環(huán)闡明沒(méi)有遍歷完，現(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)立二叉樹(shù)pTree i=CountLeaf(pTree); printf("Thereare%dleaves!",i);//遞歸程序數(shù)葉節(jié)點(diǎn) j=CountLevel(pTree); printf("Thereare%dlevels!",j);//遞歸程序數(shù)層數(shù) PreOrder(pTree);//按照前序遍歷輸出該書(shū)的元素 return0;}五、實(shí)驗(yàn)分析總結(jié)本次實(shí)驗(yàn)采用二叉樹(shù)存儲(chǔ)了一系列的字符串，通過(guò)函數(shù)TreeCreateBTree(void)得到一種根據(jù)輸入創(chuàng)立的二叉樹(shù)構(gòu)造，時(shí)間復(fù)雜度是O（n）；通過(guò)函數(shù)intCountLeaf(TreeT)遞歸返回葉子個(gè)數(shù)，時(shí)間復(fù)雜度O(n)；通過(guò)intCountLevel(TreeT)返回最深途徑得到樹(shù)的深度，時(shí)間復(fù)雜度O（n）；；最后用voidPreOrder(TreeT)實(shí)現(xiàn)非遞歸寫(xiě)法的二叉樹(shù)先序遍歷，時(shí)間復(fù)雜度為O(n).總而言之，由于都是要遍歷B數(shù)的每個(gè)節(jié)點(diǎn)，因此程序執(zhí)行的時(shí)間長(zhǎng)度和輸入的字符串長(zhǎng)度n是線性增加的。他們的時(shí)間復(fù)雜度都是O(n).這次實(shí)驗(yàn)，我更深刻的理解了B數(shù)的基本性質(zhì)如遞歸性，運(yùn)用遞歸，我們能夠很方便的寫(xiě)出多個(gè)對(duì)樹(shù)的操作；熟悉了創(chuàng)立樹(shù)，遍歷樹(shù)的基本辦法；體會(huì)了算法的代碼實(shí)現(xiàn)