實(shí)驗(yàn)六-二叉樹實(shí)驗(yàn)報告(1)

1、實(shí)驗(yàn)四 二叉樹的操作題目：對于給定的一二叉樹，實(shí)現(xiàn)各種約定的遍歷。一、實(shí)驗(yàn)?zāi)康模?1掌握二叉樹的定義和存儲表示，學(xué)會建立一棵特定二叉樹的方法； 2掌握二叉樹的遍歷算法先序、中序、后序遍歷算法的思想，并學(xué)會 遍歷算法的遞歸實(shí)現(xiàn)和非遞歸實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容： 構(gòu)造二叉樹，再實(shí)現(xiàn)二叉樹的先序、中序、后序遍歷，最后統(tǒng)計(jì) 二叉樹的深度。三、實(shí)驗(yàn)步驟： 一 需求分析1. 二叉樹的建立首先要建立一個二叉鏈表的結(jié)構(gòu)體，包含根節(jié)點(diǎn)和左右子樹。 因?yàn)闃涞拿恳粋€左右子樹又是一顆二叉樹，所以用遞歸的方法來建立其左右子 樹。二叉樹的遍歷是一種把二叉樹的每一個節(jié)點(diǎn)訪問并輸出的過程， 遍歷時根結(jié) 點(diǎn)與左右孩子的輸出順序構(gòu)成了

2、不同的遍歷方法， 這個過程需要按照不同的遍歷 的方法，先輸出根結(jié)點(diǎn)還是先輸出左右孩子，可以用選擇語句來實(shí)現(xiàn)。2程序的執(zhí)行命令為：1構(gòu)造結(jié)點(diǎn)類型，然后創(chuàng)立二叉樹。2根據(jù)提示，從鍵盤輸入各個結(jié)點(diǎn)。3通過選擇一種方式先序、中序或者后序遍歷。 4輸出結(jié)果，結(jié)束。 二 概要設(shè)計(jì)1. 二叉樹的二叉鏈表結(jié)點(diǎn)存儲類型定義typedef struct NodeDataType data;struct Node *LChild;struct Node *RChild;BitNode,*BitTree;2. 建立如以下圖所示二叉樹： void CreatBiTreeBitTree *bt 用擴(kuò)展先序遍歷序列創(chuàng) 建二

3、叉樹，如果是當(dāng)前樹根置為空，否那么申請一個新節(jié)點(diǎn)。3. 本程序包含四個模塊1) 主程序模塊:2) 先序遍歷模塊3) 中序遍歷模塊4) 后序遍歷模塊三詳細(xì)設(shè)計(jì)/=構(gòu)造二叉樹=如果是當(dāng)前樹根置為空,void CreatBiTree(BitTree *bt)用擴(kuò)展先序遍歷序列創(chuàng)立二叉樹,否那么申請一個新節(jié)點(diǎn)char ch;ch=getchar();if(ch='.')*bt=NULL;else*bt=(BitTree)malloc(sizeof(BitNode);申請一段關(guān)于該節(jié)點(diǎn)類型的存儲空間(*bt)->data=ch;/ 生成根結(jié)點(diǎn)CreatBiTree(&(*b

4、t)->LChild);/ 構(gòu)造左子樹CreatBiTree(&(*bt)->RChild);/ 構(gòu)造右子樹2.編程實(shí)現(xiàn)以上二叉樹的前序、中序和后序遍歷操作，輸出遍歷序列1先序遍歷二叉樹的遞歸算法如下：void PreOrder(BitTree root)if (root!=NULL)Visit(root ->data);PreOrder(root ->LChild); / 遞歸調(diào)用核心PreOrder(root ->RChild);2中序遍歷二叉樹的遞歸算法如下:voidIn Order(BitTree root)if (root!=NULL)InOrd

5、er(root ->LChild);Visit(root ->data);InOrder(root ->RChild);3后序遍歷二叉樹的遞歸算法如下： void PostOrder(BitTree root)if(root!=NULL)PostOrder(root ->LChild);PostOrder(root ->RChild);Visit(root ->data);4計(jì)算二叉樹的深度算法如下/求二叉樹的深度/求左子樹的深度/求右子樹的深度/得到左、右子樹深度較大者/返回樹的深度/ 如果是空樹，那么返回 0int PostTreeDepth(BitTr

6、ee bt)int hl,hr,max;if(bt!=NULL)hl=PostTreeDepth(bt->LChild); hr=PostTreeDepth(bt->RChild);max=hl>hr?hl:hr; return(max+1);else return(0);四、調(diào)試分析及測試結(jié)果1. 進(jìn)入演示程序后的顯示主界面： 請輸入二叉樹中的元素； 先序、中序和后序遍歷分別輸出結(jié)果以擴(kuò)展先序遍歷序列輸入，其中代表空子樹：ABC.DE.G.F 先序遍歷序列為： ABCDEGF中序遍歷序列為： CBEGDFA后序遍歷序列為： CGEFDBA此二叉樹的深度為： 51輸入二叉樹中

7、的元素以擴(kuò)展先序遍歷序列輸入，其中.代表空子樹，顯示截圖為：圖一2輸出結(jié)果，顯示界面為：'C:Prcgram Files (xSSJMicrosoft Visual StudioMyProiectsXeeDebLig?e.eKe*圖二4. 調(diào)試分析：本程序通過分別調(diào)用先序遍歷、中序遍歷以及后序遍歷函數(shù)對二叉樹中的元 素進(jìn)行遍歷，整個程序根本滿足實(shí)驗(yàn)要求，但是在一些細(xì)節(jié)問題上面還是存在缺 陷，比方大小寫字母不同也會導(dǎo)致程序無法運(yùn)行，這就需要我們在處理問題上認(rèn) 真細(xì)致，還有就是程序并不是很完善，總之，我會在今后更加努力，是程序更完 美。六、實(shí)驗(yàn)總結(jié)1. 二叉樹對于進(jìn)行表達(dá)式的前綴， 中綴和

8、后綴的表示有明顯的優(yōu)勢， 既方便， 又容易理解。其先序，中序和后序分別對應(yīng)這表達(dá)式的前綴，中綴和后綴。2. 在建樹與進(jìn)行樹的遍歷的時候一定要理解其建樹與遍歷的整個過程。 不然 就會連為什么這樣做都不知道。 在遍歷樹的時候最常用到的就是棧的結(jié)構(gòu)了 非 遞歸。3. 本次實(shí)驗(yàn)讓我更加了解了哈夫曼樹的構(gòu)造和生成方法，以及如何用順序結(jié) 構(gòu)來存儲哈夫曼樹及構(gòu)樹過程的信息， 如何進(jìn)行編碼、 譯碼。 也感知到模塊程序 設(shè)計(jì)在大程序設(shè)計(jì)使用中的普遍性，該實(shí)驗(yàn)是最好的證明，通過模塊程序設(shè)計(jì)， 能使程序可讀可寫性明顯加強(qiáng)。通過本次實(shí)驗(yàn)， 使我初步掌握了二叉樹的結(jié)構(gòu)特性以及各種存儲的結(jié)構(gòu)的特 點(diǎn)和適用范圍， 掌握了哈

9、夫曼樹的定義和思想， 初步掌握了用凹入法顯示樹。 不 過程序仍有樹的顯示不夠完善的缺點(diǎn)， 在今后的學(xué)習(xí)中， 我會不斷學(xué)習(xí)， 在學(xué)習(xí) 中注意改變。附錄源程序清單 :#include<stdio.h>#include<stdlib.h>#include <malloc.h>#include <conio.h>typedef int DataType;typedef struct Node/創(chuàng)立結(jié)點(diǎn)類型結(jié)構(gòu)體DataType data;struct Node *LChild;struct Node *RChild;BitNode,*BitTree;vo

10、id CreatBiTree(BitTree *bt) /用擴(kuò)展先序遍歷序列創(chuàng)立二叉樹， 如果是當(dāng)前樹根置為空， 否那么申請一個新節(jié)點(diǎn) /char ch;ch=getchar();if(ch='.')*bt=NULL;else*bt=(BitTree)malloc(sizeof(BitNode);(*bt)->data=ch;CreatBiTree(&(*bt)->LChild);CreatBiTree(&(*bt)->RChild);void visit(char ch)/ 訪問根節(jié)點(diǎn)printf("%c",ch);voi

11、d PreOrder(BitTree root) / 先序遍歷二叉樹的遞歸算法if (root!=NULL)Visit(root ->data);PreOrder(root ->LChild);PreOrder(root ->RChild);void InOrder(BitTree root)/ 中序遍歷二叉樹的遞歸算法if (root!=NULL)InOrder(root ->LChild);Visit(root ->data);InOrder(root ->RChild);void PostOrder(BitTree root)if(root!=NULL

12、)PostOrder(root ->LChild);PostOrder(root ->RChild);Visit(root ->data);int PostTreeDepth(BitTree bt)int hl,hr,max;if(bt!=NULL)hl=PostTreeDepth(bt->LChild); hr=PostTreeDepth(bt->RChild); max=hl>hr?hl:hr;return(max+1);else return(0);void main()/后序遍歷求二叉樹的遞歸算法/求二叉樹的深度/求左子樹的深度/求右子樹的深度/得到左、右子樹深度較大者 /返回樹的深度/ 如果是空樹，那么返回 0 BitTree T; int h;int layer; int treeleaf;layer=0;printf("請輸入二叉樹中的元素(以擴(kuò)展先序遍歷序列輸入,其中代表空子樹):n");CreatBiTree(&T);printf("