數(shù)據(jù)結(jié)構(gòu)實驗報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實驗?zāi)康模?）學會用先序創(chuàng)建一棵二叉樹。（2）學會采用遞歸算法對二叉樹進行先序、中序、后序遍歷。（3）學會打印輸出二叉樹的遍歷結(jié)果。實驗內(nèi)容【問題描述】建立一棵二叉樹，并對其進行遍歷（先序、中序、后序），打印輸出遍歷結(jié)果?！净疽蟆繌逆I盤接受輸入（先序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立），并采用遞歸算法對其進行遍歷（先序、中序、后序），將遍歷結(jié)果打印輸出?！緶y試數(shù)據(jù)】ABCDEGF(其中表示空格字符)則輸出結(jié)果為 先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA【選作內(nèi)容】采用非遞歸算法實現(xiàn)二叉樹遍歷。實驗步驟（一）需求分析1、在這個過

2、程中，接受遍歷的二叉樹是從鍵盤接受輸入（先序），以二叉鏈表作為存儲結(jié)構(gòu)，建立的二叉樹。因此，首先要創(chuàng)建一棵二叉樹，而這棵二叉樹是先序二叉樹。本演示程序中，集合的元素設(shè)定為大寫字母ABCDEFG，輸出的先序，中序，后序遍歷分別為ABCDEGF,CBEGDFA,CGBFDBA。二叉樹可以表示為：ABDGFEC接受的輸入數(shù)據(jù)在進行遞歸的先序，中序，后序遍歷后，分別將結(jié)果打印出來。2、在程序運行的過程中可以看到，以計算機提示用戶執(zhí)行的方式進行下去，即在計算機終端上提示“輸入二叉樹的先序序列”后，由用戶在鍵盤上輸入ABC#DE#G#F#，之后相應(yīng)的選擇遍歷及遍歷結(jié)果顯示出來。3、程序執(zhí)行的命令包括：首先

3、是二叉樹的先序序列被創(chuàng)建輸入，其次是對輸入進去的先序序列有次序的進行先序，中序，后序遍歷。最后是打印出二叉樹的遍歷結(jié)果。4、測試數(shù)據(jù)（1）在鍵盤上輸入的先序序列ABC#DE#G#F#（2）先序遍歷結(jié)果ABCDEGF（3）中序遍歷結(jié)果CBEGDFA（4）后序遍歷結(jié)果CGBFDBA（二）概要設(shè)計1、為實現(xiàn)上述程序功能，應(yīng)以二叉樹定義的相關(guān)操作和二叉樹遞歸遍歷的相關(guān)操作為依據(jù)。有關(guān)以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹的操作為：typedef BTNode *BTree; /定義二叉樹的指針BTree CreatBTree(void)BTree T;char ch;if(ch=getchar()=#)r

4、eturn(NULL); /讀入#，返回空指針 elseT=(BTNode *)malloc(sizeof(BTNode); /分配空間，生成結(jié)點T-data=ch;T-lchild=CreatBTree(); /構(gòu)造左子樹T-rchild=CreatBTree(); /構(gòu)造右子樹 return(T);2、而有關(guān)先序、中序、后序遍歷的遞歸操作為：void Preorder(BTree T) /先序遍歷if(T)printf(%c,T-data); /訪問結(jié)點Preorder(T-lchild); /先序遍歷左子樹Preorder(T-rchild); /先序遍歷右子樹void Inorder(

5、BTree T) /中序遍歷if(T)Inorder(T-lchild); /中序遍歷左子樹printf(%c,T-data); /訪問結(jié)點Inorder(T-rchild); /中序遍歷右字樹void Postorder(BTree T) /后序遍歷if(T)Postorder(T-lchild); /后序遍歷左子樹Postorder(T-rchild); /后序遍歷右子樹printf(%c,T-data); /訪問結(jié)點3、本程序包含的模塊（1）結(jié)點單元模塊（2）構(gòu)建先序二叉樹模塊（3）二叉樹遍歷模塊（4）主程序模塊各模塊之間的調(diào)用關(guān)系如下：主程序模塊結(jié)點單元模塊構(gòu)建先序二叉樹模塊二叉樹遍歷

6、模塊（三）詳細設(shè)計1、元素類型，結(jié)點類型和指針類型typedef struct nodechar data; /二叉樹的元素類型struct node *lchild;struct node *rchild;BTNode; /自定義二叉樹的結(jié)類型typedef BTNode *BTree; /定義二叉樹的指針2、定義類型之后，要以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立）。BTree CreatBTree(void)BTree T;char ch; /定義輸入的數(shù)據(jù)類型if(ch=getchar()=#) /支持在鍵盤上輸入先序二叉樹return(NULL); /讀入#，返回空指針對于二

7、叉樹的先序輸入，在輸入中要注意的是對于空指針的把握，由于是先序輸入，在輸入時要在確定的位置輸入“#”號，否則先序二叉樹將不完整。 elseT=(BTNode *)malloc(sizeof(BTNode); /分配空間，生成結(jié)點T-data=ch;T-lchild=CreatBTree(); /構(gòu)造左子樹T-rchild=CreatBTree(); /構(gòu)造右子樹 return(T);當輸入的葉子結(jié)點完整之后，要return(T)，否則輸入將一直持續(xù)下去不能跳出來。在程序的設(shè)計過程中，在適當?shù)奈恢貌迦?對于二叉樹的遍歷有著十分重要的作用，因此要明白二叉樹的先序創(chuàng)建過程如何運行。3、對于二叉樹進行

8、先序、中序、后序的遍歷。void Preorder(BTree T) /先序遍歷if(T)printf(%c,T-data); /訪問結(jié)點Preorder(T-lchild); /先序遍歷左子樹Preorder(T-rchild); /先序遍歷右子樹這個是先序遍歷，先序遍歷與中序遍歷，后序遍歷相似，都是以不同順序訪問子樹及結(jié)點。先序遍歷先訪問根節(jié)點，先序遍歷左子樹，再先序遍歷右子樹。而中序遍歷是中序遍歷左子樹，訪問根節(jié)點，中序遍歷右子樹。后序遍歷是后序遍歷左子樹，后序遍歷右子樹，后序遍歷根節(jié)點。三個遍歷雖說順序不一致，但是在程序的編寫上有很多可以相通的地方。以下分別是中序、后序的程序： voi

9、d Inorder(BTree T) /中序遍歷if(T)Inorder(T-lchild); /中序遍歷左子樹printf(%c,T-data); /訪問結(jié)點Inorder(T-rchild); /中序遍歷右字樹void Postorder(BTree T) /后序遍歷if(T)Postorder(T-lchild); /后序遍歷左子樹Postorder(T-rchild); /后序遍歷右子樹printf(%c,T-data); /訪問結(jié)點4、主程序模塊的鏈接。在這個模塊中，不僅要實現(xiàn)二叉樹先序序列從鍵盤的輸入，還要實現(xiàn)選擇三個遍歷的輸出。主函數(shù)的作用旨在使每個程序模塊能夠鏈接在一起，調(diào)用各

10、個函數(shù)以實現(xiàn)最終的目的。void main()BTree root; /數(shù)的根結(jié)點int i; /可供選擇的整型變量i printf(n);printf(請輸入二叉樹的先序序列，用#代表虛結(jié)點:);root=CreatBTree(); /返回根結(jié)點do /循環(huán)語句printf(*SELECT*n);printf(t1:先序遍歷n);printf(t2:中序遍歷n);printf(t3:后序遍歷n);printf(t0:Exitn);printf(t*n);scanf(%d,&i);/輸入菜單序號switch(i)case 1:printf(先序遍歷結(jié)果為:);Preorder(root);br

11、eak;case 2:printf(中序遍歷結(jié)果為:);Inorder(root);break;case 3:printf(后序遍歷結(jié)果為:);Postorder(root);break;在這三個選擇中，充分調(diào)用了先序、中序、后序遍歷函數(shù)，選擇1、2、3數(shù)字實現(xiàn)對三個遍歷的輸出打印。default:exit(1);printf(n);while(i!=0);5、函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：mainCreatBTreeInorderPreorderPostorder（四）調(diào)試分析1、實驗涉及的部分包括用二叉鏈表創(chuàng)建先序二叉樹，對二叉樹進行三種遍歷，最后是對三種遍歷結(jié)果進行打印。在做

12、這個實驗的過程中，我們首先最先碰到的問題是用二叉鏈表存儲先序二叉樹，由于對二叉樹存儲的不深入了解，我們在輸入數(shù)據(jù)時，只能對其無限輸入，并不能及時的終止，導致的結(jié)果是程序停止不了，運行不下去。不能返回的問題困擾了我們很久，在這個過程中，我們還嘗試了一些用棧來對其進行存儲，通過一遍遍的摸索，最終找到了正確的方法。在這個過程中，我們也對二叉樹的存儲有了更為深刻的了解，相信這在我們以后的學習中也有很大的幫助。2、在實驗過程中，我們還有嘗試了非遞歸的算法對于二叉樹的遍歷，遞歸算法和非遞歸算法各有千秋，產(chǎn)用遞歸算法更為簡單明了。3、根節(jié)點的運用沒有得到合理的開發(fā)，在主程序的鏈接中，創(chuàng)建二叉樹，返回根節(jié)點。

13、接著是一個do循環(huán)對于選擇三種遍歷結(jié)果的打印輸出和退出操作，在開始的程序設(shè)計階段沒有發(fā)揮作用，前期使用的是while和swith語句，沒有返回根結(jié)點，造成算法的運行不能有序進行下去。4、剛開始是忽略了一些細節(jié)問題，對于元素類型，結(jié)點類型的定義沒有認真檢查，程序前期運行過程中有很多的失誤，導致了效率低下。今后一定要重視確定參數(shù)的變量和賦值屬性的區(qū)別和標志。5、程序的設(shè)計基本是由一個個子模塊聯(lián)系到一起，由于前期沒有將這個程序的大致模型框架構(gòu)架好，子模塊之間的聯(lián)系在主程序中就出現(xiàn)了一些問題，因此在以后的實驗過程中，要首先構(gòu)造大框架更有利于子模塊的鏈接。（五）用戶手冊1、本程序的運行環(huán)境為 DOS 操

14、作系統(tǒng)，本程序執(zhí)行文件為“執(zhí)行二叉樹建立與遍歷.exe”。2、進入程序運行后會有說明指示首先創(chuàng)建二叉樹按照完全二叉樹的先序序列輸入，以回車鍵結(jié)束，程序主界面就會形成：3、按照要求輸入各個功能的命令，程序接受命令后立即執(zhí)行并且顯示相應(yīng)的結(jié)果。（六）測試結(jié)果（1）首先二叉鏈表存儲（以先序創(chuàng)建）鍵盤輸入（2）選擇數(shù)字“1”，先序遍歷:(3)選擇數(shù)字“2”，中序遍歷：（4）選擇數(shù)字“3”后序遍歷：（九）附錄：源程序清單#include#include#include/*typedef struct nodechar data; /二叉樹的元素類型struct node *lchild;struct n

15、ode *rchild;BTNode; /自定義二叉樹的結(jié)點類型/*typedef BTNode *BTree; /定義二叉樹的指針BTree CreatBTree(void)BTree T;char ch;if(ch=getchar()=#) /支持在鍵盤上輸入先序二叉樹return(NULL); /讀入#，返回空指針 elseT=(BTNode *)malloc(sizeof(BTNode); /分配空間，生成結(jié)點T-data=ch;T-lchild=CreatBTree(); /構(gòu)造左子樹T-rchild=CreatBTree(); /構(gòu)造右子樹 return(T);/*void Pre

16、order(BTree T) /先序遍歷if(T)printf(%c,T-data); /訪問結(jié)點Preorder(T-lchild); /先序遍歷左子樹Preorder(T-rchild); /先序遍歷右子樹/*void Inorder(BTree T) /中序遍歷if(T)Inorder(T-lchild); /中序遍歷左子樹printf(%c,T-data); /訪問結(jié)點Inorder(T-rchild); /中序遍歷右字樹/*void Postorder(BTree T) /后序遍歷if(T)Postorder(T-lchild); /后序遍歷左子樹Postorder(T-rchild

17、); /后序遍歷右子樹printf(%c,T-data); /訪問結(jié)點/*void main()BTree root; /二叉樹的根結(jié)點int i;printf(n);printf(請輸入二叉樹的先序序列，用#代表虛結(jié)點:);root=CreatBTree(); /返回根結(jié)點do /do做循環(huán)打印遍歷結(jié)果printf(*SELECT*n);printf(t1:先序遍歷n);printf(t2:中序遍歷n);printf(t3:后序遍歷n);printf(t0:Exitn);printf(t*n);scanf(%d,&i);/輸入菜單序號switch(i)case 1:printf(先序遍歷結(jié)果

18、為:);Preorder(root);break;case 2:printf(中序遍歷結(jié)果為:);Inorder(root);break;case 3:printf(后序遍歷結(jié)果為:);Postorder(root);break;default:exit(1);printf(n);while(i!=0);實驗結(jié)果分析通過我們團隊的努力，我們的二叉樹建立與遍歷實驗完成了，在這個實驗過程中，我們碰到了一些問題，比如說二叉樹的存儲沒有能夠準確返回，主函數(shù)與模塊函數(shù)之間沒有實現(xiàn)很好的連接造成調(diào)試程序上用了很多時間。忽略了一些細節(jié)問題，對于元素類型，結(jié)點類型的定義沒有認真檢查，程序前期運行過程中有很多的失誤，導致了效率低下。但是我們充分發(fā)揮了團隊的力量，依次解決了這些問題，實驗結(jié)果的正確性也得到了驗證。雖說可能仍存在一些不足之處，我們也會虛心接受，在過程中力求做到盡可能的完善。而在此次的實驗過程中，和以前的課程設(shè)計有一些不同之處，首次產(chǎn)用團隊合作的方式完成實驗，我們也在這個過程中體會到了團隊合作的好處，大家積極分享彼此的經(jīng)驗，在分工的基礎(chǔ)上合作，在合作的前提下創(chuàng)新。學到了很多