樹(shù)和二叉樹(shù)實(shí)驗(yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 樹(shù) 和 二 叉 樹(shù) 一、 實(shí)驗(yàn)?zāi)康?. 掌握二叉樹(shù)的結(jié)構(gòu)特征，以及各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。2. 掌握用指針類型描述、訪問(wèn)和處理二叉樹(shù)的運(yùn)算。二、 實(shí)驗(yàn)要求1. 認(rèn)真閱讀和掌握本實(shí)驗(yàn)的程序。2. 上機(jī)運(yùn)行本程序。3. 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。4. 按照二叉樹(shù)的操作需要，重新改寫(xiě)主程序并運(yùn)行，打印出文件清單和運(yùn)行結(jié)果。三、 實(shí)驗(yàn)內(nèi)容1. 輸入字符序列，建立二叉鏈表。2. 按先序、中序和后序遍歷二叉樹(shù)（遞歸算法）。3. 按某種形式輸出整棵二叉樹(shù)。4. 求二叉樹(shù)的高度。5. 求二叉樹(shù)的葉節(jié)點(diǎn)個(gè)數(shù)。6. 交換二叉樹(shù)的左右子樹(shù)。7. 借助隊(duì)列實(shí)現(xiàn)二

2、叉樹(shù)的層次遍歷。8. 在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)試上述算法。為了實(shí)現(xiàn)對(duì)二叉樹(shù)的有關(guān)操作，首先要在計(jì)算機(jī)中建立所需的二叉樹(shù)。建立二叉樹(shù)有各種不同的方法。一種方法是利用二叉樹(shù)的性質(zhì)5來(lái)建立二叉樹(shù)，輸入數(shù)據(jù)時(shí)要將節(jié)點(diǎn)的序號(hào)（按滿二叉樹(shù)編號(hào)）和數(shù)據(jù)同時(shí)給出：（序號(hào)，數(shù)據(jù)元素0）。另一種方法是主教材中介紹的方法，這是一個(gè)遞歸方法，與先序遍歷有點(diǎn)相似。數(shù)據(jù)的組織是先序的順序，但是另有特點(diǎn)，當(dāng)某結(jié)點(diǎn)的某孩子為空時(shí)以字符“#”來(lái)充當(dāng)，也要輸入。若當(dāng)前數(shù)據(jù)不為“#”，則申請(qǐng)一個(gè)結(jié)點(diǎn)存入當(dāng)前數(shù)據(jù)。遞歸調(diào)用建立函數(shù)，建立當(dāng)前結(jié)點(diǎn)的左右子樹(shù)。4、 解題思路1、 先序遍歷：訪問(wèn)根結(jié)點(diǎn)，先序遍歷左子樹(shù)，先序遍歷

3、右子樹(shù)2、 中序遍歷：中序遍歷左子樹(shù)，訪問(wèn)根結(jié)點(diǎn)，中序遍歷右子樹(shù)3、 后序遍歷：后序遍歷左子樹(shù)，后序遍歷右子樹(shù)，訪問(wèn)根結(jié)點(diǎn)4、 層次遍歷算法：采用一個(gè)隊(duì)列q，先將二叉樹(shù)根結(jié)點(diǎn)入隊(duì)列，然后退隊(duì)列，輸出該結(jié)點(diǎn)；若它有左子樹(shù)，便將左子樹(shù)根結(jié)點(diǎn)入隊(duì)列；若它有右子樹(shù)，便將右子樹(shù)根結(jié)點(diǎn)入隊(duì)列，直到隊(duì)列空為止。因?yàn)殛?duì)列的特點(diǎn)是先進(jìn)后出，所以能夠達(dá)到按層次遍歷二叉樹(shù)的目的。五、程序清單#include<stdio.h>#include<stdlib.h>#define M 100typedef char Etype; /定義二叉樹(shù)結(jié)點(diǎn)值的類型為字符型typedef struct BiT

4、Node /樹(shù)結(jié)點(diǎn)結(jié)構(gòu) Etype data; struct BiTNode *lch,*rch;BiTNode,*BiTree;BiTree queM;int front=0,rear=0;/函數(shù)原型聲明BiTNode *creat_bt1();BiTNode *creat_bt2();void preorder(BiTNode *p);void inorder(BiTNode *p);void postorder(BiTNode *p);void enqueue(BiTree);BiTree delqueue( );void levorder(BiTree);int treedepth(B

5、iTree);void prtbtree(BiTree,int);void exchange(BiTree);int leafcount(BiTree);void paintleaf(BiTree);BiTNode *t;int count=0;/主函數(shù)void main() char ch; int k; do printf("nnn"); printf("n=主菜單="); printf("nn 1.建立二叉樹(shù)方法1"); printf("nn 2.建立二叉樹(shù)方法2"); printf("nn 3.先

6、序遞歸遍歷二叉樹(shù)"); printf("nn 4.中序遞歸遍歷二叉樹(shù)"); printf("nn 5.后序遞歸遍歷二叉樹(shù)"); printf("nn 6.層次遍歷二叉樹(shù)"); printf("nn 7.計(jì)算二叉樹(shù)的高度"); printf("nn 8.計(jì)算二叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù)"); printf("nn 9.交換二叉樹(shù)的左右子樹(shù)"); printf("nn 10.打印二叉樹(shù)"); printf("nn 0.結(jié)束程序運(yùn)行"); p

7、rintf("n="); printf("n 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)"); scanf("%d",&k); switch(k) case 1:t=creat_bt1( );break; /調(diào)用性質(zhì)5建立二叉樹(shù)算法 case 2:printf("n請(qǐng)輸入二叉樹(shù)各結(jié)點(diǎn)值:");fflush(stdin); t=creat_bt2();break; /調(diào)用遞歸建立二叉樹(shù)算法 case 3:if(t) printf("先序遍歷二叉樹(shù):"); preorde

8、r(t); printf("n"); else printf("二叉樹(shù)為空!n"); break; case 4:if(t) printf("中序遍歷二叉樹(shù):"); inorder(t); printf("n"); else printf("二叉樹(shù)為空!n"); break; case 5:if(t) printf("后序遍歷二叉樹(shù):"); postorder(t); printf("n"); else printf("二叉樹(shù)為空!n"

9、); break; case 6:if(t) printf("層次遍歷二叉樹(shù)："); levorder(t); printf("n"); else printf("二叉樹(shù)為空！n"); break; case 7:if(t) printf("二叉樹(shù)的高度為：%d",treedepth(t); printf("n"); else printf("二叉樹(shù)為空！n"); break; case 8:if(t) printf("二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為：%dn",le

10、afcount(t); printf("二叉樹(shù)的葉結(jié)點(diǎn)為：");paintleaf(t); printf("n"); else printf("二叉樹(shù)為空！n"); break; case 9:if(t) printf("交換二叉樹(shù)的左右子樹(shù)：n"); exchange(t); prtbtree(t,0); printf("n"); else printf("二叉樹(shù)為空！n"); break; case 10:if(t) printf("逆時(shí)針旋轉(zhuǎn)90度輸出的二叉樹(shù)

11、：n"); prtbtree(t,0); printf("n"); else printf("二叉樹(shù)為空！n"); break; case 0:exit(0); /switch while(k>=1&&k<=10); printf("n再見(jiàn)！按回車鍵，返回n"); ch=getchar(); /main/利用二叉樹(shù)性質(zhì)5，借助一維數(shù)組V建立二叉樹(shù)BiTNode *creat_bt1() BiTNode *t,*p,*v20;int i,j;Etype e;/*輸入結(jié)點(diǎn)的序號(hào)i、結(jié)點(diǎn)的數(shù)據(jù)e*/pr

12、intf("n請(qǐng)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值（如1，a）：");scanf("%d,%c",&i,&e);while(i!=0&&e!='#') /當(dāng)i為0，e為'#'時(shí)，結(jié)束循環(huán) p=(BiTNode*)malloc(sizeof(BiTNode); p->data=e; p->lch=NULL; p->rch=NULL; vi=p; if(i=1) t=p; /序號(hào)為1的結(jié)點(diǎn)是根 else j=i/2; if(i%2=0)vj->lch=p; /序號(hào)為偶數(shù)，作

13、為左孩子 else vj->rch=p; /序號(hào)為奇數(shù)，作為右孩子 printf("n請(qǐng)繼續(xù)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值："); scanf("%d,%c",&i,&e);return(t);/creat_bt1;/模仿先序遞歸遍歷方法，建立二叉樹(shù)BiTNode *creat_bt2() BiTNode *t; Etype e; scanf("%c",&e); if(e='#')t=NULL; /對(duì)于'#'值，不分配新結(jié)點(diǎn) else t=(BiTNode *)mallo

14、c(sizeof(BiTNode); t->data=e; t->lch=creat_bt2(); /左孩子獲得新指針值 t->rch=creat_bt2(); /右孩子獲得新指針值 return(t); /creat_bt2/先序遞歸遍歷二叉樹(shù)void preorder(BiTNode *p)if(p) printf("%3c",p->data); preorder(p->lch); preorder(p->rch); /preorder/中序遞歸遍歷二叉樹(shù)void inorder(BiTNode *p)if(p) inorder(p-

15、>lch); printf("%3c",p->data); inorder(p->rch); /inorder/后序遞歸遍歷二叉樹(shù)void postorder(BiTNode *p) if(p) postorder(p->lch); postorder(p->rch); printf("%3c",p->data); /postordervoid enqueue(BiTree T) if(front!=(rear+1)%M) rear=(rear+1)%M; querear=T;BiTree delqueue( ) if

16、(front=rear)return NULL; front=(front+1)%M; return(quefront);void levorder(BiTree T) /層次遍歷二叉樹(shù) BiTree p; if(T) enqueue(T); while(front!=rear) p=delqueue( ); printf("%3d",p->data); if(p->lch!=NULL)enqueue(p->lch); if(p->rch!=NULL)enqueue(p->rch); int treedepth(BiTree bt) /計(jì)算二叉

17、樹(shù)的高度 int hl,hr,max; if(bt!=NULL) hl=treedepth(bt->lch); hr=treedepth(bt->rch); max=(hl>hr)?hl:hr; return (max+1); else return (0);void prtbtree(BiTree bt,int level) /逆時(shí)針旋轉(zhuǎn)90度輸出二叉樹(shù)樹(shù)形int j;if(bt)prtbtree(bt->rch,level+1);for(j=0;j<=6*level;j+)printf(" ");printf("%cn"

18、,bt->data);prtbtree(bt->lch,level+1);void exchange(BiTree bt) /交換二叉樹(shù)左右子樹(shù)BiTree p;if(bt)p=bt->lch;bt->lch=bt->rch;bt->rch=p;exchange(bt->lch);exchange(bt->rch);int leafcount(BiTree bt) /計(jì)算葉結(jié)點(diǎn)數(shù)if(bt!=NULL)leafcount(bt->lch);leafcount(bt->rch);if(bt->lch=NULL)&&

19、(bt->rch=NULL) count+;return(count);void paintleaf(BiTree bt) /輸出葉結(jié)點(diǎn) if(bt!=NULL) if(bt->lch=NULL&&bt->rch=NULL) printf("%3c",bt->data); paintleaf(bt->lch); paintleaf(bt->rch); 圖11.2所示二叉樹(shù)的輸入數(shù)據(jù)順序應(yīng)該是：abd#g#ce#h#f#。圖11.2 二叉樹(shù)示意圖運(yùn)行結(jié)果：=主菜單= 1.建立二叉樹(shù)方法1 2.建立二叉樹(shù)方法2 3.先序遞歸遍

20、歷二叉樹(shù) 4.中序遞歸遍歷二叉樹(shù) 5.后序遞歸遍歷二叉樹(shù) 6.層次遍歷二叉樹(shù) 7.計(jì)算二叉樹(shù)的高度 8.計(jì)算二叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù) 9.交換二叉樹(shù)的左右子樹(shù) 10.打印二叉樹(shù) 0.結(jié)束程序運(yùn)行= 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 1請(qǐng)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值（如1，a）：1，a請(qǐng)繼續(xù)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：2，b請(qǐng)繼續(xù)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：3，c請(qǐng)繼續(xù)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：4，d請(qǐng)繼續(xù)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：6，e請(qǐng)繼續(xù)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：7，f請(qǐng)繼續(xù)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：9，g請(qǐng)繼續(xù)輸入二

21、叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：13，h請(qǐng)繼續(xù)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：0，#=主菜單="); 1.建立二叉樹(shù)方法1 2.建立二叉樹(shù)方法2 3.先序遞歸遍歷二叉樹(shù) 4.中序遞歸遍歷二叉樹(shù) 5.后序遞歸遍歷二叉樹(shù) 6.層次遍歷二叉樹(shù) 7.計(jì)算二叉樹(shù)的高度 8.計(jì)算二叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù) 9.交換二叉樹(shù)的左右子樹(shù) 10.打印二叉樹(shù) 0.結(jié)束程序運(yùn)行= 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 3先序遍歷二叉樹(shù)：a b d g c e h f=主菜單="); 1.建立二叉樹(shù)方法1 2.建立二叉樹(shù)方法2 3.先序遞歸遍歷二叉樹(shù) 4.中序遞歸遍歷二叉樹(shù) 5.后序

22、遞歸遍歷二叉樹(shù) 6.層次遍歷二叉樹(shù) 7.計(jì)算二叉樹(shù)的高度 8.計(jì)算二叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù) 9.交換二叉樹(shù)的左右子樹(shù) 10.打印二叉樹(shù) 0.結(jié)束程序運(yùn)行= 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 4中序遍歷二叉樹(shù)：d g b a e h c f =主菜單="); 1.建立二叉樹(shù)方法1 2.建立二叉樹(shù)方法2 3.先序遞歸遍歷二叉樹(shù) 4.中序遞歸遍歷二叉樹(shù) 5.后序遞歸遍歷二叉樹(shù) 6.層次遍歷二叉樹(shù) 7.計(jì)算二叉樹(shù)的高度 8.計(jì)算二叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù) 9.交換二叉樹(shù)的左右子樹(shù) 10.打印二叉樹(shù) 0.結(jié)束程序運(yùn)行= 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,1

23、0) 5后序遍歷二叉樹(shù)：g d b h e f c a =主菜單="); 1.建立二叉樹(shù)方法1 2.建立二叉樹(shù)方法2 3.先序遞歸遍歷二叉樹(shù) 4.中序遞歸遍歷二叉樹(shù) 5.后序遞歸遍歷二叉樹(shù) 6.層次遍歷二叉樹(shù) 7.計(jì)算二叉樹(shù)的高度 8.計(jì)算二叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù) 9.交換二叉樹(shù)的左右子樹(shù) 10.打印二叉樹(shù) 0.結(jié)束程序運(yùn)行= 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 6層次遍歷二叉樹(shù)： 97 98 =主菜單="); 1.建立二叉樹(shù)方法1 2.建立二叉樹(shù)方法2 3.先序遞歸遍歷二叉樹(shù) 4.中序遞歸遍歷二叉樹(shù) 5.后序遞歸遍歷二叉樹(shù) 6.層次遍歷二叉樹(shù) 7.計(jì)

24、算二叉樹(shù)的高度 8.計(jì)算二叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù) 9.交換二叉樹(shù)的左右子樹(shù) 10.打印二叉樹(shù) 0.結(jié)束程序運(yùn)行= 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 7二叉樹(shù)的高度為：4=主菜單="); 1.建立二叉樹(shù)方法1 2.建立二叉樹(shù)方法2 3.先序遞歸遍歷二叉樹(shù) 4.中序遞歸遍歷二叉樹(shù) 5.后序遞歸遍歷二叉樹(shù) 6.層次遍歷二叉樹(shù) 7.計(jì)算二叉樹(shù)的高度 8.計(jì)算二叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù) 9.交換二叉樹(shù)的左右子樹(shù) 10.打印二叉樹(shù) 0.結(jié)束程序運(yùn)行= 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 8二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為：3二叉樹(shù)的葉結(jié)點(diǎn)為： g h f=主菜單="); 1.建立二叉樹(shù)方法1 2.建立二叉樹(shù)方法2 3.先序遞歸遍歷二叉樹(shù) 4.中序遞歸遍歷二叉樹(shù) 5.后序遞歸遍歷二叉樹(shù) 6.層次遍歷二叉樹(shù) 7.計(jì)算二叉樹(shù)的高度 8.計(jì)算二叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù) 9.交換二叉樹(shù)的左右子樹(shù) 10.打印二叉樹(shù) 0.結(jié)束程序運(yùn)行= 請(qǐng)輸入您的選擇(0,1,2,