數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、，打印輸出遍歷結(jié)果。，并采用遞歸算，將遍歷結(jié)果打印輸出。先序： ABCDEGF ，以二叉鏈表作為存ABCDEFG ，輸出的先序，中序，后序遍。二叉樹可以表示為：- -WORD 格式，打印輸出遍歷結(jié)果。，并采用遞歸算，將遍歷結(jié)果打印輸出。先序： ABCDEGF ，以二叉鏈表作為存ABCDEFG ，輸出的先序，中序，后序遍。二叉樹可以表示為：- 實(shí)驗(yàn)?zāi)康模?）學(xué)會(huì)用先序創(chuàng)建一棵二叉樹。（2）學(xué)會(huì)采用遞歸算法對二叉樹進(jìn)行先序、中序、后序遍歷。（3）學(xué)會(huì)打印輸出二叉樹的遍歷結(jié)果。實(shí)驗(yàn)內(nèi)容【問題描述】建立一棵二叉樹，并對其進(jìn)行遍歷（先序、中序、后序）【基本要求】從鍵盤接受輸入（先序） ，以二叉鏈表作為存

2、儲(chǔ)結(jié)構(gòu)，建立二叉樹（以先序來建立）法對其進(jìn)行遍歷（先序、中序、后序）【測試數(shù)據(jù)】ABC DEGF(其中表示空格字符 ) 則輸出結(jié)果為中序： CBEGDFA 后序： CGBFDBA 【選作內(nèi)容】采用非遞歸算法實(shí)現(xiàn)二叉樹遍歷。實(shí)驗(yàn)步驟（一）需求分析1、在這個(gè)過程中，接受遍歷的二叉樹是從鍵盤接受輸入（先序）儲(chǔ)結(jié)構(gòu)，建立的二叉樹。因此，首先要?jiǎng)?chuàng)建一棵二叉樹，而這棵二叉樹是先序二叉樹。本演示程序中，集合的元素設(shè)定為大寫字母歷分別為 ABCDEGF,CBEGDFA,CGBFDBA-完整版學(xué)習(xí)資料分享D F ABC#DE#G#F# - -WORD 格式-可編輯-專業(yè)資料- D F ABC#DE#G#F# -

3、 A B C E G 接受的輸入數(shù)據(jù)在進(jìn)行遞歸的先序，中序，后序遍歷后，分別將結(jié)果打印出來。2、在程序運(yùn)行的過程中可以看到，以計(jì)算機(jī)提示用戶執(zhí)行的方式進(jìn)行下去，即在計(jì)算機(jī)終端上提示“輸入二叉樹的先序序列” 后，由用戶在鍵盤上輸入 ABC#DE#G#F#，之后相應(yīng)的選擇遍歷及遍歷結(jié)果顯示出來。3、程序執(zhí)行的命令包括：首先是二叉樹的先序序列被創(chuàng)建輸入，其次是對輸入進(jìn)去的先序序列有次序的進(jìn)行先序，中序，后序遍歷。最后是打印出二叉樹的遍歷結(jié)果。4、測試數(shù)據(jù)（1）在鍵盤上輸入的先序序列（2）先序遍歷結(jié)果 ABCDEGF （3）中序遍歷結(jié)果 CBEGDFA （4）后序遍歷結(jié)果 CGBFDBA （二）概要設(shè)

4、計(jì)1、為實(shí)現(xiàn)上述程序功能，應(yīng)以二叉樹定義的相關(guān)操作和二叉樹遞歸遍歷的相關(guān)操-完整版學(xué)習(xí)資料分享/定義二叉樹的指針/讀入#，返回空指針/構(gòu)造左子樹/構(gòu)造右子樹/先序遍歷/訪問結(jié)點(diǎn)/先序遍歷左子樹/先序遍歷右子樹/中序遍歷/中序遍歷左子樹/訪問結(jié)點(diǎn)- -WORD 格式-可編輯-專業(yè)資料- /定義二叉樹的指針/讀入#，返回空指針/構(gòu)造左子樹/構(gòu)造右子樹/先序遍歷/訪問結(jié)點(diǎn)/先序遍歷左子樹/先序遍歷右子樹/中序遍歷/中序遍歷左子樹/訪問結(jié)點(diǎn)- 作為依據(jù)。有關(guān)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹的操作為：typedef BTNode *BTree; BTree CreatBTree(void) BTree

5、 T; char ch; if(ch=getchar()=#) return(NULL); else T=(BTNode *)malloc(sizeof(BTNode); / 分配空間，生成結(jié)點(diǎn)T-data=ch; T-lchild=CreatBTree(); T-rchild=CreatBTree(); return(T); 2、而有關(guān)先序、中序、后序遍歷的遞歸操作為：void Preorder(BTree T) if(T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); void Inorder(BTree T) if(

6、T) Inorder(T-lchild); printf(%c,T-data); -完整版學(xué)習(xí)資料分享/中序遍歷右字樹/后序遍歷/后序遍歷左子樹/后序遍歷右子樹/訪問結(jié)點(diǎn)- -WORD 格式-可編輯-專業(yè)資料- /中序遍歷右字樹/后序遍歷/后序遍歷左子樹/后序遍歷右子樹/訪問結(jié)點(diǎn)- Inorder(T-rchild); void Postorder(BTree T) if(T) Postorder(T-lchild); Postorder(T-rchild); printf(%c,T-data); 3、本程序包含的模塊（1）結(jié)點(diǎn)單元模塊（2）構(gòu)建先序二叉樹模塊（3）二叉樹遍歷模塊（4）主程序模

7、塊各模塊之間的調(diào)用關(guān)系如下：主程序模塊結(jié)點(diǎn)單元模塊構(gòu)建先序二叉樹模塊二叉樹遍歷模塊（三）詳細(xì)設(shè)計(jì)-完整版學(xué)習(xí)資料分享/二叉樹的元素類型/自定義二叉樹的結(jié)類型/定義二叉樹的指針。/定義輸入的數(shù)據(jù)類型/支持在鍵盤上輸入先序二叉樹/讀入#，返回空指針#”號(hào)，否則先序二叉樹將不完整。/分配空間，生成結(jié)點(diǎn)/構(gòu)造左子樹/構(gòu)造右子樹return(T) ，否則輸入將一直持續(xù)下去不能跳出來。在#對于二叉樹的遍歷有著十分重要的作用，因此- -WORD 格式-可編輯-專業(yè)資/二叉樹的元素類型/自定義二叉樹的結(jié)類型/定義二叉樹的指針。/定義輸入的數(shù)據(jù)類型/支持在鍵盤上輸入先序二叉樹/讀入#，返回空指針#”號(hào)，否則先序

8、二叉樹將不完整。/分配空間，生成結(jié)點(diǎn)/構(gòu)造左子樹/構(gòu)造右子樹return(T) ，否則輸入將一直持續(xù)下去不能跳出來。在#對于二叉樹的遍歷有著十分重要的作用，因此- 1、元素類型，結(jié)點(diǎn)類型和指針類型typedef struct node char data; struct node *lchild; struct node *rchild; BTNode; typedef BTNode *BTree; 2、定義類型之后，要以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹（以先序來建立）BTree CreatBTree(void) BTree T; char ch; if(ch=getchar()=#) ret

9、urn(NULL); 對于二叉樹的先序輸入，在輸入中要注意的是對于空指針的把握， 由于是先序輸入，在輸入時(shí)要在確定的位置輸入“else T=(BTNode *)malloc(sizeof(BTNode); T-data=ch; T-lchild=CreatBTree(); T-rchild=CreatBTree(); return(T); 當(dāng)輸入的葉子結(jié)點(diǎn)完整之后，要程序的設(shè)計(jì)過程中，在適當(dāng)?shù)奈恢貌迦胍靼锥鏄涞南刃騽?chuàng)建過程如何運(yùn)行。-完整版學(xué)習(xí)資料分享/先序遍歷/訪問結(jié)點(diǎn)/先序遍歷左子樹/先序遍歷右子樹/中序遍歷/后序遍歷- -WORD 格式-可編輯-專業(yè)資料- /先序遍歷/訪問結(jié)點(diǎn)/先序

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

11、序的程序：void Inorder(BTree T) if(T) Inorder(T-lchild); /中序遍歷左子樹printf(%c,T-data); /訪問結(jié)點(diǎn)Inorder(T-rchild); /中序遍歷右字樹 void Postorder(BTree T) -完整版學(xué)習(xí)資料分享/后序遍歷左子樹/后序遍歷右子樹/訪問結(jié)點(diǎn)/數(shù)的根結(jié)點(diǎn)/可供選擇的整型變量 i /返回根結(jié)點(diǎn)/循環(huán)語句輸入菜單序號(hào)- -WORD 格式-可編輯-專業(yè)資/后序遍歷左子樹/后序遍歷右子樹/訪問結(jié)點(diǎn)/數(shù)的根結(jié)點(diǎn)/可供選擇的整型變量 i /返回根結(jié)點(diǎn)/循環(huán)語句輸入菜單序號(hào)- if(T) Postorder(T-lc

12、hild); Postorder(T-rchild); printf(%c,T-data); 4、主程序模塊的鏈接。在這個(gè)模塊中，不僅要實(shí)現(xiàn)二叉樹先序序列從鍵盤的輸入，還要實(shí)現(xiàn)選擇三個(gè)遍歷的輸出。主函數(shù)的作用旨在使每個(gè)程序模塊能夠鏈接在一起，調(diào)用各個(gè)函數(shù)以實(shí)現(xiàn)最終的目的。void main() BTree root; int i; printf(n); printf( 請輸入二叉樹的先序序列，用 #代表虛結(jié)點(diǎn) :); root=CreatBTree(); do printf(*SELECT*n); printf(t1: 先序遍歷 n); printf(t2: 中序遍歷 n); printf(t

13、3: 后序遍歷 n); printf(t0:Exitn); printf(t*n); scanf(%d,&i);/switch(i) case 1:printf( 先序遍歷結(jié)果為 :); -完整版學(xué)習(xí)資料分享1、2、3 數(shù)字實(shí)現(xiàn)Preorder - Inorder Postorde-WORD 格式-可編輯-專業(yè)資1、2、3 數(shù)字實(shí)現(xiàn)Preorder - Inorder PostordePreorder(root); break; case 2:printf( 中序遍歷結(jié)果為 :); Inorder(root); break; case 3:printf( 后序遍歷結(jié)果為 :); Postord

14、er(root); break; 在這三個(gè)選擇中，充分調(diào)用了先序、中序、后序遍歷函數(shù)，選擇對三個(gè)遍歷的輸出打印。default:exit(1); printf(n); while(i!=0); 5、函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：main CreatBTree （四）調(diào)試分析1、實(shí)驗(yàn)涉及的部分包括用二叉鏈表創(chuàng)建先序二叉樹，對二叉樹進(jìn)行三種遍歷，最后是對三種遍歷結(jié)果進(jìn)行打印。在做這個(gè)實(shí)驗(yàn)的過程中，我們首先最先碰到的問題是用二叉鏈表存儲(chǔ)先序二叉樹，由于對二叉樹存儲(chǔ)的不深入了解，我們在輸入數(shù)據(jù)時(shí)，只能對其無限輸入，并不能及時(shí)的終止，導(dǎo)致的結(jié)果是程序停止不了，運(yùn)行不下去。不能返回的問題困擾了

15、我們很久，在這個(gè)過程中，我們還嘗試了一些用棧來對其進(jìn)行存儲(chǔ)，通過一遍遍的摸索，最終找到了正確的方法。在這個(gè)過程中，我們也對二叉樹的存儲(chǔ)-完整版學(xué)習(xí)資料分享在主程序的鏈接中， 創(chuàng)建二叉樹，返回根節(jié)點(diǎn)。while 和 swith 語句，沒有返回根結(jié)點(diǎn)，造成算法的DOS在主程序的鏈接中， 創(chuàng)建二叉樹，返回根節(jié)點(diǎn)。while 和 swith 語句，沒有返回根結(jié)點(diǎn)，造成算法的DOS 操作系統(tǒng)，本程序執(zhí)行文件為“執(zhí)行二叉樹建立與遍- 有了更為深刻的了解，相信這在我們以后的學(xué)習(xí)中也有很大的幫助。2、在實(shí)驗(yàn)過程中，我們還有嘗試了非遞歸的算法對于二叉樹的遍歷，遞歸算法和非遞歸算法各有千秋，產(chǎn)用遞歸算法更為簡單明

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

17、程序運(yùn)行后會(huì)有說明指示首先創(chuàng)建二叉樹按照完全二叉樹的先序序列輸入，以回車鍵結(jié)束，程序主界面就會(huì)形成：-完整版學(xué)習(xí)資料分享- -WORD 格式-可編輯-專業(yè)資料- - 3、按照要求輸入各個(gè)功能的命令，程序接受命令后立即執(zhí)行并且顯示相應(yīng)的結(jié)果。（六）測試結(jié)果（1）首先二叉鏈表存儲(chǔ)（以先序創(chuàng)建）鍵盤輸入（2）選擇數(shù)字“ 1”，先序遍歷 : -完整版學(xué)習(xí)資料分享- -WORD 格式-可編輯-專業(yè)資料- - (3)選擇數(shù)字“ 2”，中序遍歷：（4）選擇數(shù)字“ 3”后序遍歷：-完整版學(xué)習(xí)資料分享/二叉樹的元素類型/自定義二叉樹的結(jié)點(diǎn)類型/定義二叉樹的指針- -WORD 格式-可編輯-專業(yè)資料- /二叉樹的

18、元素類型/自定義二叉樹的結(jié)點(diǎn)類型/定義二叉樹的指針- （九）附錄：源程序清單#include #include #include /* typedef struct node char data; struct node *lchild; struct node *rchild; BTNode; /* typedef BTNode *BTree; BTree CreatBTree(void) BTree T; char ch; -完整版學(xué)習(xí)資料分享/支持在鍵盤上輸入先序二叉樹/讀入#，返回空指針/構(gòu)造左子樹/構(gòu)造右子樹/先序遍歷/訪問結(jié)點(diǎn)/先序遍歷左子樹/先序遍歷右子樹/中序遍歷/中序遍歷左子

19、樹/訪問結(jié)點(diǎn)/中序遍歷右字樹/后序遍歷- -WORD 格式-可編輯-專業(yè)資料- /支持在鍵盤上輸入先序二叉樹/讀入#，返回空指針/構(gòu)造左子樹/構(gòu)造右子樹/先序遍歷/訪問結(jié)點(diǎn)/先序遍歷左子樹/先序遍歷右子樹/中序遍歷/中序遍歷左子樹/訪問結(jié)點(diǎn)/中序遍歷右字樹/后序遍歷- if(ch=getchar()=#) return(NULL); else T=(BTNode *)malloc(sizeof(BTNode); / 分配空間，生成結(jié)點(diǎn)T-data=ch; T-lchild=CreatBTree(); T-rchild=CreatBTree(); return(T); /* void Preor

20、der(BTree T) if(T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); /* void Inorder(BTree T) if(T) Inorder(T-lchild); printf(%c,T-data); Inorder(T-rchild); /* void Postorder(BTree T) -完整版學(xué)習(xí)資料分享/后序遍歷左子樹/后序遍歷右子樹/訪問結(jié)點(diǎn)/二叉樹的根結(jié)點(diǎn)/返回根結(jié)點(diǎn)/do 做循環(huán)打印遍歷結(jié)果輸入菜單序號(hào)- -WORD 格式-可編輯-專業(yè)資/后序遍歷左子樹/后序遍歷右子樹/訪問結(jié)點(diǎn)/二叉樹

21、的根結(jié)點(diǎn)/返回根結(jié)點(diǎn)/do 做循環(huán)打印遍歷結(jié)果輸入菜單序號(hào)- if(T) Postorder(T-lchild); Postorder(T-rchild); printf(%c,T-data); /* void main() BTree root; int i; printf(n); printf( 請輸入二叉樹的先序序列，用 #代表虛結(jié)點(diǎn) :); root=CreatBTree(); do 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); break; case 2:printf( 中序遍歷結(jié)果為 :); Inorder(root); break; case 3:printf( 后序遍歷結(jié)果為 :); -完整版學(xué)習(xí)資料分享- -WORD 格式-可編輯-專業(yè)資料- - Postorder(root); break; default:exit(1); printf(n); while(i!=0); 實(shí)驗(yàn)結(jié)果分析通