1、實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)項(xiàng)目 計(jì)算機(jī)軟件基礎(chǔ) 實(shí)驗(yàn)2 二叉樹(shù) 實(shí)驗(yàn)儀器 電腦 學(xué)院/班級(jí) 學(xué)號(hào)/姓名 實(shí)驗(yàn)日期 一、實(shí)驗(yàn)名稱(chēng) 二叉樹(shù)的應(yīng)用二、實(shí)驗(yàn)?zāi)康?掌握二叉樹(shù)的鏈?zhǔn)胶晚樞虼鎯?chǔ)結(jié)構(gòu)，利用隊(duì)列對(duì)二叉樹(shù)進(jìn)行運(yùn)算。三、實(shí)驗(yàn)內(nèi)容（1）編寫(xiě)函數(shù)creatbt,其功能是將一維數(shù)組方式存儲(chǔ)的二叉樹(shù)轉(zhuǎn)化為鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)，返回root指針。（2）編寫(xiě)函數(shù)freebt，其功能是釋放二叉樹(shù)鏈表節(jié)點(diǎn)的存儲(chǔ)空間。函數(shù)原型為：void freebt (TNODE * root)（3）編寫(xiě)函數(shù)實(shí)現(xiàn)前序、中序和后序遍歷；（4）用下面的應(yīng)用程序作測(cè)試，檢查輸出結(jié)果：void main() int t_array14=8,11,2

2、,3,9,15,6,-1,-1,-1,10,-1,-1,13; /-1表示空struct tnode *root;root=creatbt(t_array,14,0);preorder(root);inorder(root);postorder(root);freebt(root);int t_array14=8,11,2,3,9,15,6,-1,-1,-1,10,-1,-1,13;/-1表示空前序：8,11,3,9,10,2,15,6,13中序: 3,11,9,10,8,15,2,13,6后序：3,10,9,11,15,13,6,2,8層次：8,11,2,3,9,15,6,10,13結(jié)點(diǎn)總個(gè)

3、數(shù)：9個(gè)葉子個(gè)數(shù)：4個(gè)（5）（選做）編寫(xiě)函數(shù)計(jì)算二叉樹(shù)結(jié)點(diǎn)總數(shù)和葉子結(jié)點(diǎn)的個(gè)數(shù)；int node_sum(TNODE *bt) ;int leaf_sum(TNODE *bt);（6）（選做）編寫(xiě)算法實(shí)現(xiàn)對(duì)樹(shù)中結(jié)點(diǎn)按層次遍歷的函數(shù)，函數(shù)原型為：void leveltrav(TNODE * bt);算法概述：i.設(shè)置一個(gè)隊(duì)列，TNODE *queueMAXSIZE 其元素的數(shù)據(jù)類(lèi)型為T(mén)NODE *，將bt(根root)入隊(duì)；ii.重復(fù)以下過(guò)程直至隊(duì)空：取出隊(duì)頭元素到bt，若bt->lchild不為空，則輸出bt->lchild->data，且bt->lchild入隊(duì)；若b

4、t->rchild不為空，則輸出bt->rchild->data，且bt>rchild入隊(duì)。（7）(選做) 把二叉樹(shù)所有結(jié)點(diǎn)的左右子樹(shù)交換void exchage(TNODE *bt); 交換后為前序：8,2,6,13,15,11,9,10,3中序: 6,13,2,15,8,10,9,11,3,后序：13,6,15,2,10,9,3,11,8層次：8,2,11,6,15,9,3,13,10四、調(diào)試結(jié)果分析圖1、運(yùn)行界面五、實(shí)驗(yàn)心得本次試驗(yàn)是關(guān)于二叉樹(shù)的常見(jiàn)操作，主要是二叉樹(shù)的建立和遍歷，在這次實(shí)驗(yàn)中我是按先序方式建立二叉樹(shù)的，而遍歷方式則相對(duì)要多一些，有遞歸的先序、中序

5、、后序遍歷，和非遞歸的先序、中序、后序遍歷，此外還有層次遍歷，其中遞歸的三種遍歷大同小異，此處僅以中序代替，非遞歸遍歷則通過(guò)棧來(lái)實(shí)現(xiàn)，在入棧出棧中要注意一些邊界條件，否則會(huì)出現(xiàn)運(yùn)行錯(cuò)誤，層次遍歷通過(guò)隊(duì)列實(shí)現(xiàn)；在本此實(shí)驗(yàn)中嗎，棧隊(duì)列我調(diào)用了庫(kù)函數(shù)里的模板，這樣是整個(gè)程序看起來(lái)簡(jiǎn)單多了；二叉樹(shù)高度和葉子個(gè)數(shù)的計(jì)算和遍歷相差不大，只是加些判斷條件，這里不再贅述，總體來(lái)說(shuō)，本次試驗(yàn)不太好做，期間出現(xiàn)了很多邏輯錯(cuò)誤，變量初始化的問(wèn)題等，不過(guò)經(jīng)過(guò)仔細(xì)排查最后都一一解決了。附錄：實(shí)驗(yàn)代碼#include <stdio.h>#include <stdlib.h>#include <

6、;malloc.h>#include <string.h>int count=0;typedef struct TNODEint data;struct TNODE *lchild,*rchild;TNODE;TNODE *creatbt(int T,int n,int i) /遞歸 創(chuàng)建二叉樹(shù)程序 TNODE *r; if (i>n-1|Ti=-1) /-1表示空 總計(jì)n個(gè)數(shù)存儲(chǔ)在 0-n-1 return (NULL); r=(TNODE *)malloc(sizeof(TNODE); r->data=Ti; r->lchild=creatbt(T,n,

7、2*i+1); r->rchild=creatbt(T,n,2*i+2); return(r);void preorder(struct TNODE *BT) /前序遍歷二叉樹(shù) if(BT!=NULL) printf("%d, ",BT->data); preorder(BT->lchild); preorder(BT->rchild); void inorder(struct TNODE *BT) /中序遍歷二叉樹(shù) if(BT!=NULL) inorder(BT->lchild); printf("%d, ",BT->

8、;data); inorder(BT->rchild); void postorder(struct TNODE *BT) /后序遍歷二叉樹(shù) if(BT!=NULL) postorder(BT->lchild); postorder(BT->rchild); printf("%d, ",BT->data); int leaf_sum(struct TNODE *BT) /求葉子節(jié)點(diǎn)數(shù) if(!BT) return 0; else if(!BT->lchild&&!BT->rchild) return 1; else ret

9、urn leaf_sum(BT->lchild)+leaf_sum(BT->rchild);int node_sum(struct TNODE *BT) /計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)，需定義全局變量count if(BT) node_sum(BT->lchild); node_sum(BT->rchild); count+; /結(jié)點(diǎn)個(gè)數(shù) return count;void leveltrav(struct TNODE *BT) /按層次遍歷二叉樹(shù)TNODE *p; TNODE *qu9; int front,rear; front=rear=-1; rear+; qurear=

10、BT; while(front!=rear) front=(front+1)%9; p=qufront; printf("%d,",p->data); if(p->lchild!=NULL) rear=(rear+1)%9; qurear=p->lchild; if(p->rchild!=NULL) rear=(rear+1)%9; qurear=p->rchild; void exchage(struct TNODE *BT) struct TNODE *temp; if (BT = NULL) return; exchage(BT ->

11、;lchild); /交換左子樹(shù) exchage(BT ->rchild); /交換右子樹(shù) temp = NULL; temp = BT ->lchild; /交換 BT->lchild=BT->rchild; BT->rchild=temp;void freebt(struct TNODE *BT) /釋放二叉樹(shù)的所有結(jié)點(diǎn) if(BT=NULL) /*若是空樹(shù)*/ return; freebt(BT->lchild);/*遞歸調(diào)用*/ freebt(BT->rchild); BT->lchild=NULL; BT->rchild=NULL

12、; free(BT);void main() int t_array14=8,11,2,3,9,15,6,-1,-1,-1,10,-1,-1,13; /-1表示空 struct TNODE *root; root=creatbt(t_array,14,0); printf("二叉樹(shù)先序遍歷結(jié)果是：n");preorder(root);printf("n");printf("二叉樹(shù)中序遍歷結(jié)果是：n");inorder(root);printf("n");printf("二叉樹(shù)后序遍歷結(jié)果是：n"

13、);postorder(root);printf("n"); printf("二叉樹(shù)葉子節(jié)點(diǎn)的個(gè)數(shù)是:n %dn",leaf_sum(root); printf("二叉樹(shù)結(jié)點(diǎn)總個(gè)數(shù)是:n %dn",node_sum(root);printf("二叉樹(shù)層次遍歷結(jié)果是：n");leveltrav(root);printf("nn");exchage(root); /二叉樹(shù)所有結(jié)點(diǎn)的左右子樹(shù)交換 printf("二叉樹(shù)所有結(jié)點(diǎn)的左右子樹(shù)交換nn");printf("交換后二叉樹(shù)先序遍歷結(jié)果是：n");preorder(root);printf("n");printf("交換后二叉樹(shù)中序遍歷結(jié)果是：n");inorder(root);printf(