樹和二叉樹實驗報告

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

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

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

4、Node /樹結(jié)點結(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.建立二叉樹方法1"); printf("nn 2.建立二叉樹方法2"); printf("nn 3.先

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

7、rintf("n="); printf("n 請輸入您的選擇(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建立二叉樹算法 case 2:printf("n請輸入二叉樹各結(jié)點值:");fflush(stdin); t=creat_bt2();break; /調(diào)用遞歸建立二叉樹算法 case 3:if(t) printf("先序遍歷二叉樹:"); preorde

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

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

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

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

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

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

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

15、>lch); printf("%3c",p->data); inorder(p->rch); /inorder/后序遞歸遍歷二叉樹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) /層次遍歷二叉樹 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) /計算二叉

17、樹的高度 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) /逆時針旋轉(zhuǎn)90度輸出二叉樹樹形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) /交換二叉樹左右子樹BiTree p;if(bt)p=bt->lch;bt->lch=bt->rch;bt->rch=p;exchange(bt->lch);exchange(bt->rch);int leafcount(BiTree bt) /計算葉結(jié)點數(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é)點 if(bt!=NULL) if(bt->lch=NULL&&bt->rch=NULL) printf("%3c",bt->data); paintleaf(bt->lch); paintleaf(bt->rch); 圖11.2所示二叉樹的輸入數(shù)據(jù)順序應該是：abd#g#ce#h#f#。圖11.2 二叉樹示意圖運行結(jié)果：=主菜單= 1.建立二叉樹方法1 2.建立二叉樹方法2 3.先序遞歸遍

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

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

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

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

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