1、云南大學數(shù)學與統(tǒng)計學實驗教學中心 yv. /樹作為一種非線性結(jié)構(gòu)在軟件設(shè)計中是應(yīng)用及為廣泛的數(shù)據(jù)結(jié)構(gòu)，而對樹的基本操作的基礎(chǔ) 又集中于遍歷操作上，本實習在課堂討論的三種遍歷方法的基礎(chǔ)上，要求同學自行設(shè)計不同的遍 歷方法并是實現(xiàn)，此外，還要求實現(xiàn)二叉樹的一些其它運算。實驗報告 yv. /樹作為一種非線性結(jié)構(gòu)在軟件設(shè)計中是應(yīng)用及為廣泛的數(shù)據(jù)結(jié)構(gòu)，而對樹的基本操作的基礎(chǔ) 又集中于遍歷操作上，本實習在課堂討論的三種遍歷方法的基礎(chǔ)上，要求同學自行設(shè)計不同的遍 歷方法并是實現(xiàn)，此外，還要求實現(xiàn)二叉樹的一些其它運算。課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法學期：2011-2012學年第二學期成績：指導教師：學生姓名：學生學

2、號：上亠實驗名稱：一叉樹的建立及其基本運算的實現(xiàn)實驗要求：必做實驗學時：8學時聲實驗編號：5實驗日期：第9-12周完成日期：2010-6-9學院：數(shù)學與統(tǒng)計學院專業(yè):信息與計算科學年級：4 2010級N一、實驗?zāi)康亩嶒瀮?nèi)容1、以二叉鏈表作為二叉樹的存貯結(jié)構(gòu)，以交互方式非遞歸的創(chuàng)建一棵給定的二叉樹。2、根據(jù)所給定的二叉鏈表表示的二叉樹，分層打印這棵二叉數(shù)上的各結(jié)點。 要求每層先打印層號，然后再從左到右打印該層中各結(jié)點的值。3以樹狀形式打印這棵二叉樹。例：如下的樹樹狀打印的結(jié)果為B 尖A eD EDFB4、用非遞歸方式，后序遍歷一棵給定的二叉樹，并用上述建立的二叉樹為例，打印出其后 序遍歷的結(jié)

3、果。三、實驗環(huán)境Windows XP程序設(shè)計語言C四、實驗過程1.實驗要求：（1丿每一小問題的程序設(shè)計以一個C的函數(shù)對應(yīng)，若要增加問題要求，只要增加函數(shù)即可。 算法要考慮通用性，對給定的不同輸入可以創(chuàng)建不同的二叉樹，并進行相應(yīng)有運算。（2）二叉鏈表的類型定義采用課堂所用的。 測試數(shù)據(jù)：對如下給定的二叉樹進行測試：F7F7實現(xiàn)提示：（1）實驗內(nèi)容的 1，2 兩題的求解思路是類似的，均可采用分層遍歷樹的思想來實現(xiàn)。 實現(xiàn)算法時應(yīng)引入一個指針隊列以記錄已建立或已遍歷過的結(jié)點。對 2，考慮到 分層打印，可以在隊列中加入空指針 NULL 作為層次的間隔。（2）對實驗內(nèi)容 3 可在課堂講的 6 種遍歷方法

4、中省略的 3 種中考慮。附加要求:、求出給定給定二叉樹中結(jié)點的個數(shù)并輸出。求出給定給定二叉樹中葉結(jié)點的個數(shù)并輸出。Q.自己設(shè)計一個帶有創(chuàng)新意義的與樹有關(guān)的題目，并給出程序解答。2.實驗設(shè)計的（各）流程圖：（以下內(nèi)容請同學認真填寫）3程序設(shè)計的關(guān)鍵代碼及解釋：（注意對程序代碼給出必要的注解，保證可讀性） #include#include#include#define null 0 typedef struct BiTree char data; struct BiTree *lchild,*rchild;BiTree,*BT;BT CreatBitree(BT Tree, BT Q)int fr

5、ont=0,rear=0; char ch1,ch2; BT p,q;printf(若節(jié)點為空請用代替n); printf(請輸入根節(jié)點：”)；ch1=getchar(); p=(BiTree *)malloc(sizeof(BiTree);p-data =ch1; Tree=p;Qrear=Tree; rear+; while(front != rear) q=Qfront; front+;printf(請輸入%c的左孩子chi和右孩子ch2 :,q-data); getchar();ch1=getchar(); ch2=getchar(); if(chi !=)p=(BiTree *)ma

6、lloc(sizeof(BiTree); p-data =ch1; q-lchild=p; Qrear+=p;else q-lchild=null; if(ch2 !=) p=(BiTree *)malloc(sizeof(BiTree); p-data =ch2; q-rchild=p; Qrear+=p;else q-rchild=null;return Tree;void LevelTravers(BT Tree, BT Q)BT q;int front=0,rear=0,i=0;Qrear+=null;Qrear+=Tree;printf(nnn);while (front != re

7、ar)q=Qfront+; if(q!=null) printf(%2c,q-data); if(q-lchild != null)Qrear+=q-lchild; if(q-rchild != null)Qrear+=q-rchild; elseQrear+=null;if(q=null&Qfront=null) return; printf(nLEVEL %2d:,+i);printf(nvoid NodeCounter(BT Tree,BT Q)int front=0,rear=0;BT q;Qrear+=Tree;while(front!=rear)q=Qfront+;if(q-lch

8、ild !=null)Qrear+=q-lchild;if(q-rchild !=null)Qrear+=q-rchild; putchar(n); printf(nprintf(樹的節(jié)點為：)；for(front=0;front!=rear;front+)q=Qfront; printf(%2c,q-data);printf(n 樹的節(jié)點總數(shù)為 %dn,rear);void LevesCounter(BT Tree,BT Q)int front=0,rear=0;int i=0;BT q;Qrear+=Tree; while(front!=rear) q=Qfront+; if(q-lchi

9、ld !=null) Qrear+=q-lchild; if(q-rchild !=null) Qrear+=q-rchild;printf(nprintf(樹的葉子為：”)； for(front=0;front!=rear;front+) q=Qfront;if(q-lchild =null&q-rchild =null) printf(%2c,q-data); i+;nn);nn);1/f1/fprintf(n 葉子節(jié)點總數(shù)為 %dn,i);printf(nnn);void PrintTree(BT Tree, int i)int j;if(Tree-rchild)PrintTree(Tr

10、ee-rchild,i+1); for(j=1;jdata); if(Tree-lchild)PrintTree(Tree-lchild,i+1);void PostOrderTraverse(BT Tree, BT Q) int top =0;int tag20; BT q; q = Tree;printf(nprintf(后序非遞歸遍歷的結(jié)果為：”); dowhile (q != null)top+;Qtop=q;tagtop =0; q=q-lchild;if(top0) q=Qtop; if(tagtop=1) i printf(%2c,q-data); top-;q=null; el

11、se tagtop=1; q=q-rchild;while(q !=null II top !=0); printf(n); main()BT root=NULL,Q50; int i=1;root=CreatBitree(root, Q); LevelTravers(root,Q);putchar(n); NodeCounter(root,Q); LevesCounter(root,Q); PrintTree(root,i);PostOrderTraverse(root,Q);4.實驗（程序運行）結(jié)果的粘貼：（必需是你的程序運行結(jié)果截圖）五、實驗總結(jié)1遇到的問題及分析：（請結(jié)合你的試驗過程認

12、真總結(jié)）對樹的操作，遞歸遍歷很容易理解，把遞歸轉(zhuǎn)化成非遞歸，我感覺還是有一些難度，拿遍歷來說，遞 歸的時候只用考慮根，左孩和右孩，非遞歸的時候往往要借助隊列跟棧，而且要站在整體的角度上來考 慮這個問題。2解決方案（列出遇到的問題和解決辦法，列出沒有解決的問題）：遇到的問題： 解決分層打印沒什么思路，只是老師提示要用隊列解決辦法： 后來看了精品那本書，跟同學討論，并在紙上模擬運行，通過了再上級調(diào)試的 沒有解決的問題： 1）附加要求里面要求自己設(shè)計創(chuàng)新的題目，我跟同學思考來用模擬小球掉落的正態(tài) 分布，我們用系統(tǒng)產(chǎn)生的隨機數(shù)的奇偶性決定往左還是往右，不過模擬的結(jié)果不太理想，小球總是會掉落在兩端，所以就沒有在實驗報告上給出。3體會和收獲。根據(jù)老師給的思路，實現(xiàn)起