2023年實(shí)驗(yàn)二叉樹(shù)實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)四二叉樹(shù)的操作班級(jí)：計(jì)算機(jī)10（）2班姓名:唐自鴻學(xué)號(hào)：完畢日期：2023.6.14題目:對(duì)于給定的一二叉樹(shù)，實(shí)現(xiàn)各種約定的遍歷。一、實(shí)驗(yàn)?zāi)康模海?）掌握二叉樹(shù)的定義和存儲(chǔ)表達(dá)，學(xué)會(huì)建立一棵特定二叉樹(shù)的方法；（2）掌握二叉樹(shù)的遍歷算法（先序、中序、后序遍歷算法）的思想，并學(xué)會(huì)遍歷算法的遞歸實(shí)現(xiàn)和非遞歸實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容:構(gòu)造二叉樹(shù)，再實(shí)現(xiàn)二叉樹(shù)的先序、中序、后序遍歷，最后記錄二叉樹(shù)的深度。三、實(shí)驗(yàn)環(huán)節(jié)：（一）需求分析.二叉樹(shù)的建立一方面要建立一個(gè)二叉鏈表的結(jié)構(gòu)體,包含根節(jié)點(diǎn)和左右子樹(shù)。由于樹(shù)的每一個(gè)左右子樹(shù)又是一顆二叉樹(shù)，所以用遞歸的方法來(lái)建立其左右子樹(shù)。二叉樹(shù)的遍歷是一種把二叉樹(shù)的每一個(gè)節(jié)點(diǎn)訪問(wèn)并輸出的過(guò)程，遍歷時(shí)根結(jié)點(diǎn)與左右孩子的輸出順序構(gòu)成了不同的遍歷方法,這個(gè)過(guò)程需要按照不同的遍歷的方法，先輸出根結(jié)點(diǎn)還是先輸出左右孩子，可以用選擇語(yǔ)句來(lái)實(shí)現(xiàn)。.程序的執(zhí)行命令為：1）構(gòu)造結(jié)點(diǎn)類(lèi)型，然后創(chuàng)建二又樹(shù)。2）根據(jù)提醒，從鍵盤(pán)輸入各個(gè)結(jié)點(diǎn)。3）通過(guò)選擇一種方式（先序、中序或者后序）遍歷。4）輸出結(jié)果,結(jié)束。（二）概要設(shè)計(jì)1.二叉樹(shù)的二叉鏈表結(jié)點(diǎn)存儲(chǔ)類(lèi)型定義typedefstructNodeDataTypedata;

PostOrder(root->LChi1d)；PostOrder(root—>RChi1d);Visit(root—>data);))intPostTreeDepth(BitTreebt)(inthl,hr,max;if(bt!=NULL){hl=PostTreeDepth(bt—>LChild)：hr=PostTreeDepth(bt->RChild)；max=hl>hr?hI:hr；return(max+1);)elsereturn(0);〃求二叉樹(shù)的深度〃求二叉樹(shù)的深度〃求二叉樹(shù)的深度〃求左子樹(shù)的深度//求右子樹(shù)的深度〃得到左、右子樹(shù)深度較大者〃返回樹(shù)的深度//假如是空樹(shù),則返回〃求二叉樹(shù)的深度〃求左子樹(shù)的深度//求右子樹(shù)的深度〃得到左、右子樹(shù)深度較大者〃返回樹(shù)的深度//假如是空樹(shù),則返回0inth;intlayer;inttreeleaf；1ayer=0;printf("請(qǐng)輸入二叉樹(shù)中的元素(以擴(kuò)展先序遍歷序列輸入，其中.代表空子樹(shù))：\rT);OreatBiTree(&T)：printf("先序遍歷序列為:");PreOrder(T)；printf("\n中序遍歷序列為:")；InOrder(T)：printf("\n后序遍歷序列為：")；PostOrder(T);h=PostTreeDepth(T);printf("\n");printf("此二義樹(shù)的深度為:％小斤'刈;}structNode*LChild;structNode*RChi1d;JBitNode,*BitTree;.建立如下圖所示二叉樹(shù):voidCreatBiTree(BitTree*bt)用擴(kuò)展先序遍歷序列創(chuàng)建二叉樹(shù)，假如是當(dāng)前樹(shù)根置為空，否則申請(qǐng)一個(gè)新節(jié)點(diǎn)。.本程序包含四個(gè)模塊1)主程序模塊：2)先序遍歷模塊3)中序遍歷模塊4)后序遍歷模塊(三)具體設(shè)計(jì).建立二又樹(shù)存儲(chǔ)類(lèi)型〃=========4勾造二叉樹(shù)=======voidCreatBiTree(BitTree*bt)〃用擴(kuò)展先序遍歷序列創(chuàng)建二叉樹(shù)，假如是當(dāng)前樹(shù)根置為空，否則申請(qǐng)一個(gè)新節(jié)點(diǎn)//{Charch；ch=getchar();if(ch==,./)*bt=NULL;else*bt=(BitTree)ma1Ioc(sizeof(BitNode));//申請(qǐng)一段關(guān)于該節(jié)點(diǎn)類(lèi)型的存儲(chǔ)空間(*bt)—>data=ch;〃生成根結(jié)點(diǎn)CreatBiTree(&((*bt)->LChild))；〃構(gòu)造左子樹(shù)CreatBiTree(&((*bt)->RChi1d));〃構(gòu)造右子樹(shù))).編程實(shí)現(xiàn)以上二叉樹(shù)的前序、中序和后序遍歷操作，輸出遍歷序列1)先序遍歷二叉樹(shù)的遞歸算法如下：voidPreOrder(BitTreeroot)(if(root!=NULL)(Visit(root—>data)；Pre0rder(root->LChild);//遞歸調(diào)用核心Pre0rder(root—>RChi1d);))2)中序遍歷二叉樹(shù)的遞歸算法如下：voidIn0rder(BitTreeroot)(if(root!=NULL)InOrder(root->LChild)；Visit(root->data)；1nOrder(root->RChild);))3)后序遍歷二叉樹(shù)的遞歸算法如下：voidPostOrder(BitTreeroot)(if(root!=NULL)(PostOrder(root->LChiId)：Pos10rder(root->RChiId);Visit(root->data);})4)計(jì)算二叉樹(shù)的深度算法如下：intPostTreeDepth(BitTreebt)//求二叉樹(shù)的深度inthl,hr.max;if(bt!=NULL)(hl=PostTreeDepth(bt->LChild);〃求左子樹(shù)的深度hr=PostTreeDepth(bt->RChild);//求右子樹(shù)的深度max=hl>hr?hl:hr;//得到左、右子樹(shù)深度較大者〃返回樹(shù)的深度return(max+1);

elsereturn(0);〃返回樹(shù)的深度elsereturn(0);elsereturn(0);//假如是空樹(shù)，則返回0四、調(diào)試分析及測(cè)試結(jié)果elsereturn(0);//假如是空樹(shù)，則返回0.進(jìn)入演示程序后的顯示主界面：請(qǐng)輸入二叉樹(shù)中的元素；先序、中序和后序遍歷分別輸出結(jié)果。.測(cè)試結(jié)果以擴(kuò)展先序遍歷序列輸入，其中.代表空子樹(shù)：ABC..DE.G..F...先序遍歷序列為:ABCDEGF中序遍歷序列為:CBEGDFA后序遍歷序列為:CGEFDBA此二叉樹(shù)的深度為:5.程序運(yùn)營(yíng)結(jié)果1）輸入二叉樹(shù)中的元素（以擴(kuò)展先序遍歷序列輸入，其中.代表空子樹(shù)），顯示截圖為：?*C:\ProgramFiles（x86）\MicrosoftVisualStudio\MyProjects\ee\Debug\ee.exe"請(qǐng)輸入二叉樹(shù)中的元素V以擴(kuò)展先序遍歷序列輸入.其中.代表空"子樹(shù)）：圖一2）輸出結(jié)果,顯示界面為:

S3■"C:\ProgramFiles(x86)\MicrosoftVisualStudio\MyPrqiects\ee\Debug\ee.exe"八S3八.Disw叉wc.tylyij-八.Disw八.Disw叉wc.tylyij-G..F...萬(wàn)莊列為：ABCDEGF力序歹?為：CBEGDFA無(wú)序歹J為：CGEFDBA用的深度為邙anykeytocontinue圖二4.調(diào)試分析：本程序通過(guò)度別調(diào)用先序遍歷、中序遍歷以及后序遍歷函數(shù)對(duì)二叉樹(shù)中的元素進(jìn)行遍歷，整個(gè)程序基本滿足實(shí)驗(yàn)規(guī)定，但是在一些細(xì)節(jié)問(wèn)題上面還是存在缺陷，比如大小寫(xiě)字母不同也會(huì)導(dǎo)致程序無(wú)法運(yùn)營(yíng)，這就需要我們?cè)诮鉀Q問(wèn)題上認(rèn)真細(xì)致，尚有就是程序并不是很完善，總之，我會(huì)在此后更加努力，是程序更完美。六、實(shí)驗(yàn)總結(jié).二叉樹(shù)對(duì)于進(jìn)行表達(dá)式的前綴，中綴和后綴的表達(dá)有明顯的優(yōu)勢(shì)，既方便，又容易理解。其先序，中序和后序分別相應(yīng)這表達(dá)式的前綴，中綴和后綴。.在建樹(shù)與進(jìn)行樹(shù)的遍歷的時(shí)候一定要理解其建樹(shù)與遍歷的整個(gè)過(guò)程。不然就會(huì)連為什么這樣做都不知道。在遍歷樹(shù)的時(shí)候最常用到的就是棧的結(jié)構(gòu)了（非遞歸）。.本次實(shí)驗(yàn)讓我更加了解了哈夫曼樹(shù)的構(gòu)造和生成方法，以及如何用順序結(jié)構(gòu)來(lái)存儲(chǔ)哈夫曼樹(shù)及構(gòu)樹(shù)過(guò)程的信息，如何進(jìn)行編碼、譯碼。也感知到模塊程序設(shè)計(jì)在大程序設(shè)計(jì)使用中的普遍性，該實(shí)驗(yàn)是最佳的證明，通過(guò)模塊程序設(shè)計(jì)，能使程序可讀可寫(xiě)性明顯加強(qiáng)。通過(guò)本次實(shí)驗(yàn)，使我初步掌握了二叉樹(shù)的結(jié)構(gòu)特性以及各種存儲(chǔ)的結(jié)構(gòu)的特點(diǎn)和合用范圍，掌握了哈夫曼樹(shù)的定義和思想，初步掌握了用凹入法顯示樹(shù)。但是程序仍有樹(shù)的顯示不夠完善的缺陷，在此后的學(xué)習(xí)中，我會(huì)不斷學(xué)習(xí)，在學(xué)習(xí)中注意改變。附錄源程序清單:include<stdio.h>include<stdlib.h>inc1ude<ma1Ioc.h>incIude<conio.h>typedefintDataType;typedefstructNode〃創(chuàng)建結(jié)點(diǎn)類(lèi)型結(jié)構(gòu)體(DataTypedata；structNode*LChild；structNode*RChild;}BitNode,*BitTree;voidCreatBiTree(BitTree*bt)//用擴(kuò)展先序遍歷序列創(chuàng)建二叉樹(shù)，假如是當(dāng)前樹(shù)根置為空，否則申請(qǐng)一個(gè)新節(jié)點(diǎn)//{charch；ch=getchar()；if(ch==z.')*bt=NULL；else(*bt=(BitTreeJmalloc(sizeof(BitNode));(*bt)->data=ch;CreatBiTree(&((*bt)—>LChild));CreatBiTree(&((*bt)->RChild))；))voidvisit(charch)〃訪問(wèn)根節(jié)點(diǎn)printf("%cM,ch);voidPreOrder(BitTreeroot)//先序遍歷二叉樹(shù)的遞歸算法(if(root!=NULL){Visit(root—>data);PreOrder(root->LChi1d);PreOrder(roo