數(shù)據(jù)結構實驗報告

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

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

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

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

5、 T; char ch; if(ch=getchar()=#) return(NULL); else T=(BTNode *)malloc(sizeof(BTNode); / 分配空間，生成結點T-data=ch; T-lchild=CreatBTree(); T-rchild=CreatBTree(); return(T); 2、而有關先序、中序、后序遍歷的遞歸操作為：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); -完整版學習資料分享/中序遍歷右字樹/后序遍歷/后序遍歷左子樹/后序遍歷右子樹/訪問結點- -WORD 格式-可編輯-專業(yè)資料- /中序遍歷右字樹/后序遍歷/后序遍歷左子樹/后序遍歷右子樹/訪問結點- Inorder(T-rchild); void Postorder(BTree T) if(T) Postorder(T-lchild); Postorder(T-rchild); printf(%c,T-data); 3、本程序包含的模塊（1）結點單元模塊（2）構建先序二叉樹模塊（3）二叉樹遍歷模塊（4）主程序模

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

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

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

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

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

12、hild); Postorder(T-rchild); printf(%c,T-data); 4、主程序模塊的鏈接。在這個模塊中，不僅要實現(xiàn)二叉樹先序序列從鍵盤的輸入，還要實現(xiàn)選擇三個遍歷的輸出。主函數(shù)的作用旨在使每個程序模塊能夠鏈接在一起，調用各個函數(shù)以實現(xiàn)最終的目的。void main() BTree root; int i; printf(n); printf( 請輸入二叉樹的先序序列，用 #代表虛結點 :); 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( 先序遍歷結果為 :); -完整版學習資料分享1、2、3 數(shù)字實現(xiàn)Preorder - Inorder Postorde-WORD 格式-可編輯-專業(yè)資1、2、3 數(shù)字實現(xiàn)Preorder - Inorder PostordePreorder(root); break; case 2:printf( 中序遍歷結果為 :); Inorder(root); break; case 3:printf( 后序遍歷結果為 :); Postord

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

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

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

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

18、元素類型/自定義二叉樹的結點類型/定義二叉樹的指針- （九）附錄：源程序清單#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; -完整版學習資料分享/支持在鍵盤上輸入先序二叉樹/讀入#，返回空指針/構造左子樹/構造右子樹/先序遍歷/訪問結點/先序遍歷左子樹/先序遍歷右子樹/中序遍歷/中序遍歷左子

19、樹/訪問結點/中序遍歷右字樹/后序遍歷- -WORD 格式-可編輯-專業(yè)資料- /支持在鍵盤上輸入先序二叉樹/讀入#，返回空指針/構造左子樹/構造右子樹/先序遍歷/訪問結點/先序遍歷左子樹/先序遍歷右子樹/中序遍歷/中序遍歷左子樹/訪問結點/中序遍歷右字樹/后序遍歷- if(ch=getchar()=#) return(NULL); else T=(BTNode *)malloc(sizeof(BTNode); / 分配空間，生成結點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) -完整版學習資料分享/后序遍歷左子樹/后序遍歷右子樹/訪問結點/二叉樹的根結點/返回根結點/do 做循環(huán)打印遍歷結果輸入菜單序號- -WORD 格式-可編輯-專業(yè)資/后序遍歷左子樹/后序遍歷右子樹/訪問結點/二叉樹

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