數(shù)據(jù)結(jié)構(gòu)與算法實驗報告-二叉樹

1、沈 陽 工 程 學(xué) 院學(xué) 生 實 驗 報 告（課程名稱： 數(shù)據(jù)結(jié)構(gòu)與算法 ）實驗題目： 二叉樹 班 級 軟本111 學(xué) 號 04 姓 名 吳月芬 地 點 F座606 指導(dǎo)教師 姜柳 祝世東 實 驗 日 期 : 2012年10月25日 12 / 13文檔可自由編輯打印一、實驗?zāi)康? 掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點及適用范圍。2 掌握用指針類型描述、訪問和處理二叉樹的運算。二、實驗環(huán)境Turbo C或是Visual C+三、實驗內(nèi)容與要求1 輸入字符序列，建立二叉鏈表。2 按先序、中序和后序遍歷二叉樹（遞歸算法）。3 按某種形式輸出整棵二叉樹。4 求二叉樹的高度。5 求二叉樹的葉結(jié)點

2、個數(shù)。6 交換二叉樹的左右子樹。7 借助隊列實現(xiàn)二叉樹的層次遍歷。8 在主函數(shù)中設(shè)計一個簡單的菜單，調(diào)試上述算法，要求1-3必做，4-7為選做。為了實現(xiàn)對二叉樹的有關(guān)操作，首先要在計算機中建立所需的二叉樹。建立二叉樹有各種不同的方法。一種方法是利用二叉樹的性質(zhì)5來建立二叉樹，輸入數(shù)據(jù)時需要將結(jié)點的序號（按滿二叉樹編號）和數(shù)據(jù)同時給出：（序號，數(shù)據(jù)元素）。圖4.1所示二叉樹的輸入數(shù)據(jù)順序應(yīng)該是：（1,a），（2,b），（3,c），（4,d），（6,e），（7,f），（9,g），（13,h）。另一種算法是主教材中介紹的方法，這是一個遞歸方法，與先序遍歷有點相似。數(shù)據(jù)的組織是先序的順序，但是另有特點

3、，當(dāng)某結(jié)點的某孩子為空時以字符“#”來充當(dāng)，也要輸入。這時，圖4.1所示二叉樹的輸入數(shù)據(jù)順序應(yīng)該是：abd#g#ce#h#f#。若當(dāng)前數(shù)據(jù)不為“#”，則申請一個結(jié)點存入當(dāng)前數(shù)據(jù)。遞歸調(diào)用建立函數(shù)，建立當(dāng)前結(jié)點的左右子樹。 四、實驗過程及結(jié)果分析（一）二叉樹1.二叉樹的綜合程序源代碼如下所示：#include <stdio.h>#include <malloc.h>#define NULL 0struct bitree char data; struct bitree * lchild, * rchild;struct bitree * createbitree_1(st

4、ruct bitree * t)int ch;scanf("%d",&ch);if(ch=0)t=NULL;elset->data=ch;t->lchild=(struct bitree *)malloc(sizeof(struct bitree);t->lchild=createbitree_1(t->lchild);t->rchild=(struct bitree *)malloc(sizeof(struct bitree);t->rchild=createbitree_1(t->rchild);return t; st

5、ruct bitree * createbitree_2(struct bitree * t)int ch;scanf("%d",&ch);if(ch=0)t=NULL;elset->lchild=(struct bitree *)malloc(sizeof(struct bitree);t->lchild=createbitree_2(t->lchild);t->data=ch;t->rchild=(struct bitree *)malloc(sizeof(struct bitree);t->rchild=createbitr

6、ee_2(t->rchild);return t;void preorder_1(struct bitree * T) if(T!=NULL) printf("%dtt",T->data); preorder_1(T->lchild); preorder_1(T->rchild); void preorder_yezi(struct bitree * T) if(T!=NULL) if(T->lchild=NULL&&T->rchild=NULL)/只輸出葉子節(jié)點printf("%dtt",T->

7、data); preorder_1(T->lchild); preorder_1(T->rchild); void inorder_1(struct bitree * H) if(H) inorder_1(H->lchild); printf("%dtt",H->data); inorder_1(H->rchild);void preorder_2 (struct bitree * p) struct bitree *s100;int top=-1;while(p!=NULL|top!=-1)while(p!=NULL)top+;stop=p;

8、 printf("%dtt",p->data);p=p->lchild;if(top!=-1)p=stop;top-;p=p->rchild;void preorder_yezi_2 (struct bitree * p) struct bitree *s100;int top=-1;while(p!=NULL|top!=-1)while(p!=NULL)top+;stop=p;if(p->lchild=NULL && p->rchild=NULL)/只輸出葉子節(jié)點 printf("%dtt",p->d

9、ata);p=p->lchild;if(top!=-1)p=stop;top-;p=p->rchild;void inorder_2 (struct bitree * p) struct bitree *s100;int top=-1;while(p!=NULL|top!=-1)while(p!=NULL)top+;stop=p;p=p->lchild;if(top!=-1)p=stop;top-;printf("%dtt",p->data);p=p->rchild;void menu_1()printf("nt* * * * * *

10、 菜 單 * * * * * * *n");printf("t1.樹的建立n");printf("t2.樹的遍歷n");printf("t0.退 出n");void menu_2(int n)if(n=1)printf("nt* * * * * * 菜 單 * * * * * * *n"); printf("nt1.樹的遞歸的先序建立n"); printf("nt2.樹的遞歸的中序建立n"); printf("nt3.樹的非遞歸的先序建立n");

11、 printf("nt4.樹的非遞歸的中序建立n");if(n=2)printf("nt* * * * * * 菜 單 * * * * * * *n");printf("nt1.樹的遞歸的先序遍歷n");printf("nt2.樹的遞歸的中序遍歷n");printf("nt3.樹的非遞歸的先序遍歷n");printf("nt4.樹的非遞歸的中序遍歷n"); printf("nt5.樹的遞歸的先序遍歷葉子節(jié)點n");printf("nt6.樹的非遞

12、歸的先序遍歷葉子節(jié)點n");void main()struct bitree * H;int n,m;H=(struct bitree *)malloc(sizeof(struct bitree);domenu_1();scanf("%d",&n);if(n>2|n<0)printf("ntt您的輸入有誤！");else if(n!=0)menu_2(n);scanf("%d",&m);if(n=1)if(m=1) H=createbitree_1(H);if(m=2)H=createbitree_2(H);if(n=2)if(m=1)preorder_1(H);if(m=2)inorder_1(H);if(m=3)preorder_2(H);if(m=4)inorder_2(H);if(m=5)preorder_yezi(H);if(m=6)preorder_yezi_2(H);while(n!=0);2.運行過程二叉樹遞歸的先序建立過程如圖1.1所示。圖1.1先序建立二叉樹二叉樹的遞歸的先序遍歷如圖1.2所示。圖1.2遞歸先序遍歷二叉樹的遞歸的中序遍歷如圖1.3所示。圖1.3遞歸的中序遍歷二叉樹的非