1、樹和二叉樹、實驗目的1. 掌握二叉樹的結構特征，以及各種存儲結構的特點及適用圍2. 掌握用指針類型描述、訪問和處理二叉樹的運算。、實驗要求1. 認真閱讀和掌握本實驗的程序。2. 上機運行本程序。3. 保存和打印出程序的運行結果，并結合程序進行分析。4. 按照二叉樹的操作需要，重新改寫主程序并運行，打印出文件清單和運 行結果。三、實驗容1. 輸入字符序列，建立二叉鏈表。2. 按先序、中序和后序遍歷二叉樹（遞歸算法） 。3. 按某種形式輸出整棵二叉樹。4. 求二叉樹的高度。5. 求二叉樹的葉節點個數。6. 交換二叉樹的左右子樹。7. 借助隊列實現二叉樹的層次遍歷。8. 在主函數中設計一個簡單的菜單

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

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

4、struct BiTNode/ 樹結點結構Etype data;struct BiTNode *lch,*rch;BiTNode,*BiTree;BiTree queM;int front=0,rear=0;/函數原型聲明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 tre

5、edepth(BiTree);void prtbtree(BiTree,int);void exchange(BiTree);int leafcount(BiTree);void paintleaf(BiTree);BiTNode *t;int count=0;/主函數void main()char ch;int k;doprintf("nnn");一亠gm -亠步出printf("n= 主菜單 =printf("nn1.建立二叉樹方法 1");printf("nn2.建立二叉樹方法 2");printf("nn3

6、.先序遞歸遍歷二叉樹 ");printf("nn4.中序遞歸遍歷二叉樹 ");printf("nn5.后序遞歸遍歷二叉樹 ");printf("nn6.層次遍歷二叉樹 ");printf("nn7.計算二叉樹的高度 ");printf("nn8.計算二叉樹中葉結點個數 ");printf("nn9.交換二叉樹的左右子樹 ");printf("nn10.打印二叉樹 ");printf("nn printf("n=0.結束程序運行

7、 ");printf("n 請輸入您的選擇 (0,1,2,3,4,5,6,7,8,9,10)");scanf("%d",&k);switch(k)case 1:t=creat_bt1( );break;/ 調用性質 5 建立二叉樹算法case 2:printf("n 請輸入二叉樹各結點值 :");fflush(stdin);t=creat_bt2();break;/ 調用遞歸建立二叉樹算法case 3:if(t)printf(" 先序遍歷二叉樹 :");preorder(t);printf(&qu

8、ot;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");break;case 6:if(t

9、)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(" 二叉樹的葉子結點數為： %dn",leafcount(t);printf("

10、; 二叉樹的葉結點為： ");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(" 逆時針旋轉 90 度輸出的二叉樹： n");prtbtree(t,0);

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

12、對應的值(如 1， a)：");scanf("%d,%c",&i,&e);while(i!=0&&e!='#')/當 i 為 0， e 為 '#'時，結束循環p=(BiTNode*)malloc(sizeof(BiTNode);p->data=e;p->lch=NULL;p->rch=NULL;vi=p;if(i=1)t=p; /序號為 1 的結點是根elsej=i/2;if(i%2=0)vj->lch=p;else vj->rch=p;/序號為偶數，作為左孩子/序號為奇

13、數，作為右孩子");printf("n 請繼續輸入二叉樹各結點的編號和對應的值： scanf("%d,%c",&i,&e);return(t);/creat_bt1;/模仿先序遞歸遍歷方法，建立二叉樹BiTNode *creat_bt2()BiTNode *t;Etype e;scanf("%c",&e);if(e='#')t=NULL;/對于 '#'值，不分配新結點else/左孩子獲得新指針值 /右孩子獲得新指針值t=(BiTNode *)malloc(sizeof(BiTNo

14、de); 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->lch);printf("%3c",p->data)

15、;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(front=rear)return NULL;front=(front+1)%M;return(qu

16、efront);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)int hl,hr,max;if(bt!=NULL) hl=treedepth(bt->lch); hr=treedepth(bt->r

17、ch); max=(hl>hr)?hl:hr; return (max+1);else return (0);void prtbtree(BiTree bt,int level)int j;if(bt)prtbtree(bt->rch,level+1);/層次遍歷二叉樹/計算二叉樹的高度/逆時針旋轉 90 度輸出二叉樹樹形for(j=0;j<=6*level;j+)printf(" "); printf("%cn",bt->data); prtbtree(bt->lch,level+1);void exchange(BiTr

18、ee 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) / 計算葉結點數 if(bt!=NULL) leafcount(bt->lch); leafcount(bt->rch); if(bt->lch=NULL)&&(bt->rch=NULL) count+;return(count);void paintleaf(

19、BiTree bt)/ 輸出葉結點if(bt!=NULL)if(bt->lch=NULL&&bt->rch=NULL) printf("%3c",bt->data);paintleaf(bt->lch);paintleaf(bt->rch);圖 11.2 所示二叉樹的輸入數據順序應該是：abd#g#ce#h#f# 。b圖11.2二叉樹示意圖運行結果：=王采單= 1建立二叉樹方法 12建立二叉樹方法23先序遞歸遍歷二叉樹4中序遞歸遍歷二叉樹5后序遞歸遍歷二叉樹6層次遍歷二叉樹7計算二叉樹的高度8計算二叉樹中葉結點個數9. 交換二叉

20、樹的左右子樹10. 打印二叉樹0.結束程序運行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 11，a): 1， a2, b3, c4, d6, e7, f9, g13, h請輸入二叉樹各結點的編號和對應的值(如 請繼續輸入二叉樹各結點的編號和對應的值 請繼續輸入二叉樹各結點的編號和對應的值 請繼續輸入二叉樹各結點的編號和對應的值 請繼續輸入二叉樹各結點的編號和對應的值 請繼續輸入二叉樹各結點的編號和對應的值 請繼續輸入二叉樹各結點的編號和對應的值 請繼續輸入二叉樹各結點的編號和對應的值 請繼續輸入二叉樹各結點的編號和對應的值=主菜單=");1建立二叉樹方法 12建立

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

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

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

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