樹 和 二 叉 樹
一、實驗目的 1. 掌握二叉樹的結構特征，以及各種存儲結構的特點及適用范圍。
2. 掌握用指針類型描述、訪問和處理二叉樹的運算。
二、實驗要求 1. 認真閱讀和掌握本實驗的程序。
2. 上機運行本程序。
3. 保存和打印出程序的運行結果，并結合程序進行分析。
4. 按照二叉樹的操作需要，重新改寫主程序并運行，打印出文件清單和運行結果。
三、實驗內容 1. 輸入字符序列，建立二叉鏈表。
2. 按先序、中序和后序遍歷二叉樹（遞歸算法）。
3. 按某種形式輸出整棵二叉樹。
4. 求二叉樹的高度。
5. 求二叉樹的葉節點個數。
6. 交換二叉樹的左右子樹。
7. 借助隊列實現二叉樹的層次遍歷。
8. 在主函數中設計一個簡單的菜單，分別調試上述算法。
為了實現對二叉樹的有關操作，首先要在計算機中建立所需的二叉樹。建立二叉樹有各種不同的方法。一種方法是利用二叉樹的性質 5 來建立二叉樹，輸入數據時要將節點的序號（按滿二叉樹編號）和數據同時給出：（序號，數據元素 0）。另一種方法是主教材中介紹的方法，這是一個遞歸方法，與先序遍歷有點相似。數據的組織是先序的順序，但是另有特點，當某結點的某孩子為空時以字符“#”來充當，也要輸入。若當前數據不為“#”，則申請一個結點存入當前數據。遞歸調用建立函數，建立當前結點的左右子樹。
四、解題思路 1、先序遍歷：○1 訪問根結點，○ 2 先序遍歷左子樹，○ 3 先序遍歷右子樹 2、中序遍歷：○1 中序遍歷左子樹，○ 2 訪問根結點，○ 3 中序遍歷右子樹 3、后序遍歷：○1 后序遍歷左子樹，○ 2 后序遍歷右子樹，○ 3 訪問根結點 4、層次遍歷算法：采用一個隊列 q，先將二叉樹根結點入隊列，然后退隊列，輸出該結點；若它有左子樹，便將左子樹根結點入隊列；若它有右子樹，便將右子樹根結點入隊列，直到隊列空為止。因為隊列的特點是先進后出，所以能夠達到按層次遍歷二叉樹的目的。
五、程序清單 #include<stdio.h> #include<stdlib.h> #define M 100
typedef char Etype;
//定義二叉樹結點值的類型為字符型 typedef struct BiTNode
//樹結點結構 {
Etype data;
struct BiTNode *lch,*rch; }BiTNode,*BiTree; BiTree que[M]; 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 treedepth(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;
do{
printf("\n\n\n");
printf("\n===================主菜單===================");
printf("\n\n
1.建立二叉樹方法 1");
printf("\n\n
2.建立二叉樹方法 2");
printf("\n\n
3.先序遞歸遍歷二叉樹");
printf("\n\n
4.中序遞歸遍歷二叉樹");
printf("\n\n
5.后序遞歸遍歷二叉樹");
printf("\n\n
6.層次遍歷二叉樹");
printf("\n\n
7.計算二叉樹的高度");
printf("\n\n
8.計算二叉樹中葉結點個數");
printf("\n\n
9.交換二叉樹的左右子樹");
printf("\n\n
10.打印二叉樹");
printf("\n\n
0.結束程序運行");
printf("\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;
//調用性質 5 建立二叉樹算法
case 2:printf("\n 請輸入二叉樹各結點值:");fflush(stdin);
t=creat_bt2();break;
//調用遞歸建立二叉樹算法
case 3:if(t)
{printf("先序遍歷二叉樹:");
preorder(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");
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("二叉樹的葉子結點數為：%d\n",leafcount(t));
printf("二叉樹的葉結點為：");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);
printf("\n");
}
else printf("二叉樹為空！\n");
break;
case 0:exit(0);
}
//switch
}while(k>=1&&k<=10);
printf("\n 再見！按回車鍵，返回…\n");
ch=getchar(); }
//main
//利用二叉樹性質 5，借助一維數組 V 建立二叉樹 BiTNode *creat_bt1() { BiTNode *t,*p,*v[20];int i,j;Etype e; /*輸入結點的序號 i、結點的數據 e*/ printf("\n 請輸入二叉樹各結點的編號和對應的值（如 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;
v[i]=p;
if(i==1)
t=p;
//序號為 1 的結點是根
else
{
j=i/2;
if(i%2==0)v[j]->lch=p;
//序號為偶數，作為左孩子
else
v[j]->rch=p;
//序號為奇數，作為右孩子
}
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(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->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);
} } //postorder
void enqueue(BiTree T) {
if(front!=(rear+1)%M)
{rear=(rear+1)%M;
que[rear]=T;} } BiTree delqueue( ) {
if(front==rear)return NULL;
front=(front+1)%M;
return(que[front]); } 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->rch);
max=(hl>hr)?hl:hr;
return (max+1);
}
else return (0); }
void prtbtree(BiTree bt,int level)
//逆時針旋轉 90 度輸出二叉樹樹形 {int j; if(bt) {prtbtree(bt->rch,level+1);
for(j=0;j<=6*level;j++)printf(" "); printf("%c\n",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)
//計算葉結點數 { if(bt!=NULL) {leafcount(bt->lch); leafcount(bt->rch); if((bt->lch==NULL)&&(bt->rch==NULL))
count++; } return(count); }
void paintleaf(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##。
圖 11.2
二叉樹示意圖
運行結果：
===================主菜單===================
1.建立二叉樹方法 1
2.建立二叉樹方法 2
3.先序遞歸遍歷二叉樹
4.中序遞歸遍歷二叉樹
5.后序遞歸遍歷二叉樹
6.層次遍歷二叉樹
7.計算二叉樹的高度
8.計算二叉樹中葉結點個數
9.交換二叉樹的左右子樹
10.打印二叉樹
0.結束程序運行 ============================================
請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 1 請輸入二叉樹各結點的編號和對應的值（如 1，a）：1，a 請繼續輸入二叉樹各結點的編號和對應的值：2，b 請繼續輸入二叉樹各結點的編號和對應的值：3，c 請繼續輸入二叉樹各結點的編號和對應的值：4，d 請繼續輸入二叉樹各結點的編號和對應的值：6，e 請繼續輸入二叉樹各結點的編號和對應的值：7，f 請繼續輸入二叉樹各結點的編號和對應的值：9，g 請繼續輸入二叉樹各結點的編號和對應的值：13，h 請繼續輸入二叉樹各結點的編號和對應的值：0，#
===================主菜單===================");
1.建立二叉樹方法 1
2.建立二叉樹方法 2
3.先序遞歸遍歷二叉樹
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.建立二叉樹方法 1
2.建立二叉樹方法 2
3.先序遞歸遍歷二叉樹
4.中序遞歸遍歷二叉樹
5.后序遞歸遍歷二叉樹
6.層次遍歷二叉樹
7.計算二叉樹的高度
8.計算二叉樹中葉結點個數
9.交換二叉樹的左右子樹
10.打印二叉樹
0.結束程序運行 ============================================
請輸入您的選擇(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.計算二叉樹中葉結點個數
9.交換二叉樹的左右子樹
10.打印二叉樹
0.結束程序運行 ============================================
請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 5 后序遍歷二叉樹：g
d
b
h
e
f
c
a
===================主菜單===================");
1.建立二叉樹方法 1
2.建立二叉樹方法 2
3.先序遞歸遍歷二叉樹
4.中序遞歸遍歷二叉樹
5.后序遞歸遍歷二叉樹
6.層次遍歷二叉樹
7.計算二叉樹的高度
8.計算二叉樹中葉結點個數
9.交換二叉樹的左右子樹
10.打印二叉樹
0.結束程序運行 ============================================
請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 6 層次遍歷二叉樹：
97 98 99100101102103104
===================主菜單===================");
1.建立二叉樹方法 1
2.建立二叉樹方法 2
3.先序遞歸遍歷二叉樹
4.中序遞歸遍歷二叉樹
5.后序遞歸遍歷二叉樹
6.層次遍歷二叉樹
7.計算二叉樹的高度
8.計算二叉樹中葉結點個數
9.交換二叉樹的左右子樹
10.打印二叉樹
0.結束程序運行 ============================================
請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 7 二叉樹的高度為：4
===================主菜單===================");
1.建立二叉樹方法 1
2.建立二叉樹方法 2
3.先序遞歸遍歷二叉樹
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.建立二叉樹方法 1
2.建立二叉樹方法 2
3.先序遞歸遍歷二叉樹
4.中序遞歸遍歷二叉樹
5.后序遞歸遍歷二叉樹
6.層次遍歷二叉樹
7.計算二叉樹的高度
8.計算二叉樹中葉結點個數
9.交換二叉樹的左右子樹
10.打印二叉樹
0.結束程序運行 ============================================
請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 9 交換二叉樹的左右子樹：
d
g
b
a
e
h
c
f
===================主菜單===================");
1.建立二叉樹方法 1
2.建立二叉樹方法 2
3.先序遞歸遍歷二叉樹
4.中序遞歸遍歷二叉樹
5.后序遞歸遍歷二叉樹
6.層次遍歷二叉樹
7.計算二叉樹的高度
8.計算二叉樹中葉結點個數
9.交換二叉樹的左右子樹
10.打印二叉樹
0.結束程序運行 ============================================
請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 10 逆時針旋轉 90 度輸出的二叉樹：
d
g
b
a
e
h
c
f
===================主菜單===================");
1.建立二叉樹方法 1
2.建立二叉樹方法 2
3.先序遞歸遍歷二叉樹
4.中序遞歸遍歷二叉樹
5.后序遞歸遍歷二叉樹
6.層次遍歷二叉樹
7.計算二叉樹的高度
8.計算二叉樹中葉結點個數
9.交換二叉樹的左右子樹
10.打印二叉樹
0.結束程序運行 ============================================
請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 2 請輸入二叉樹各結點值：abd#g###ce#h##f##
===================主菜單===================");
1.建立二叉樹方法 1
2.建立二叉樹方法 2
3.先序遞歸遍歷二叉樹
4.中序遞歸遍歷二叉樹
5.后序遞歸遍歷二叉樹
6.層次遍歷二叉樹
7.計算二叉樹的高度
8.計算二叉樹中葉結點個數
9.交換二叉樹的左右子樹
10.打印二叉樹
0.結束程序運行 ============================================
請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 0 請按任意鍵繼續. . .
六、調試心得及收獲 建立二叉樹有兩種方法：一種方法是利用二叉樹的性質 5 來建立二叉樹；另一種方法是主教材中介紹的方法，這是一個遞歸方法，與先序遍歷有點相似。建立后，通過先序、中序、后序遍歷，對二叉樹有了進一步的理解與掌握。對二叉樹中各種計算也更了解了！
七、其他所想到的 一個二叉樹，有許多部分構成，每一個部分都需要精心編寫，才能對其進行操作，不至于出錯。
推薦訪問： 實驗 報告 二叉樹下一篇：食品包裝學實驗報告
同志們：今天這個大會，是市委全面落實黨要管黨、從嚴治黨要求的一項重大舉措，也是對縣市區委書記履行基層黨建工作第一責任人情況的一次集中檢閱，同時是對全市基層黨建工作的一次再部署、再落實的會議。前面，**
***年，我認真履行領班子、帶隊伍、抓黨員、保穩定的基層黨建工作思路，以學習貫徹習近平新時代中國特色社會主義思想和黨的十九大歷次全會精神為主線，以市局基層黨建工作考核細則為落腳點，落實全面從嚴治黨主體
根據會議安排，現將2022年履行抓基層黨建工作職責情況報告如下：一、履職工作特色和亮點1 突出政治建設，著力在思想認識上提高。牢固樹立抓黨建就是抓政績的理念，以“黨建工作抓引領、社區治理求突破，為民服
2022年以來，在**黨委的正確領導下，堅持以習近平新時代中國特色社會主義思想為指導，深入學習宣傳貫徹黨的二十大精神，以黨建工作為統領，扎實開展夯實“三個基本”活動，以“四化四力”行動為抓手，聚力創建
各位領導，同志們：根據會議安排，現就2022年度抓基層黨建工作情況匯報如下：一、主要做法及成效（一）強化政治引領。一是不斷強化理論武裝。堅持通過黨組會、中心組學習會和“三會一課”，第一時間、第一議題學
2022年度抓基層黨建工作述職報告按照黨委工作部署，現將本人2022年度抓基層黨建工作情況報告如下：一、2022年度抓基層黨建工作情況（一）旗幟鮮明講政治將旗幟鮮明講政治放在全局發展首要位置，積極開展
2022年，是我在數計系黨總支書記這個新崗位上度過的第一個完整的工作年度。回首一年來在校黨委的正確領導下，與數計系領導班子和全體師生共同走過的日子，艱辛歷歷在目，收獲溫潤心田。作為黨總支書記，我始終牢
按照考核要求，現將本人一年來，作為統戰部長履行職責、廉潔自律等方面情況報告如下：一、著眼增強政治素質，不斷深化理論學習堅持把旗幟鮮明講政治作為履職從政的第一位要求，帶領統戰系統干部堅決擁護“兩個確立”
**年，緊緊圍繞黨工委、管委會的決策部署，全體人員團結協作、凝心聚力，緊扣黨工委“**”基本工作思路，全力開拓進取，認真履職盡責，圓滿完成各項工作任務。一、個人思想政治狀況檸檬文苑www bgzjy
按照縣委關于開展抓基層黨建述職評議會議的有關要求，經請示縣委組織部同意，今天，我們在此召開2022年度基層黨組織書記抓基層黨建述職評議會議。1 首先，請**黨委書記，**同志述職。**黨委能夠主動研究