1、實(shí)驗(yàn)報(bào)告第 7 頁(yè) 共 7 頁(yè)一、實(shí)驗(yàn)?zāi)康?、熟悉二叉樹樹的基本操作。2、掌握二叉樹的實(shí)現(xiàn)以及實(shí)際應(yīng)用。3、加深二叉樹的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境1臺(tái)WINDOWS環(huán)境的PC機(jī)，裝有Visual C+ 6.0。三、實(shí)驗(yàn)內(nèi)容【問(wèn)題描述】現(xiàn)需要編寫一套二叉樹的操作函數(shù)，以便用戶能夠方便的利用這些函數(shù)來(lái)實(shí)現(xiàn)自己的應(yīng)用。其中操作函數(shù)包括：1> 創(chuàng)建二叉樹CreateBTNode(*b,*str)：根據(jù)二叉樹括號(hào)表示法的字符串*str生成對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2> 輸出二叉樹DispBTNode(*b)：以括號(hào)表示法輸出一棵二叉樹。3> 查找結(jié)點(diǎn)FindNode(

2、*b,x)：在二叉樹b中尋找data域值為x的結(jié)點(diǎn),并返回指向該結(jié)點(diǎn)的指針。4> 求高度BTNodeDepth(*b)：求二叉樹b的高度。若二叉樹為空,則其高度為0；否則,其高度等于左子樹與右子樹中的最大高度加l。5> 求二叉樹的結(jié)點(diǎn)個(gè)數(shù)NodesCount(BTNode *b)6> 先序遍歷的遞歸算法：void PreOrder(BTNode *b) 7> 中序遍歷的遞歸算法：void InOrder(BTNode *b) 8> 后序遍歷遞歸算法：void PostOrder(BTNode *b) 9> 層次遍歷算法void LevelOrder(BTNo

3、de *b)【基本要求】實(shí)現(xiàn)以上9個(gè)函數(shù)。主函數(shù)中實(shí)現(xiàn)以下功能：創(chuàng)建下圖中的樹b輸出二叉樹b找到H節(jié)點(diǎn)，輸出其左右孩子值輸出b的高度輸出b的節(jié)點(diǎn)個(gè)數(shù)輸出b的四種遍歷順序ABDCEHJKLMNFGI上圖轉(zhuǎn)化為二叉樹括號(hào)表示法為A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)程序:#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;/*數(shù)據(jù)元素*/struct node *lchild;/*指

4、向左孩子*/struct node *rchild;/*指向右孩子*/ BTNode;void CreateBTNode(BTNode *&b,char *str);/創(chuàng)建BTNode *FindNode(BTNode *b,ElemType x);/查找節(jié)點(diǎn)int BTNodeHeight(BTNode *b);/求高度void DispBTNode(BTNode *b);/輸出int NodesCount(BTNode *b);/二叉樹的結(jié)點(diǎn)個(gè)數(shù)void PreOrder(BTNode *b);/先序遍歷遞歸void InOrder(BTNode *b);/中序遍歷遞歸void P

5、ostOrder(BTNode *b);/后序遍歷遞歸void LevelOrder(BTNode *b);/層次遍歷/創(chuàng)建void CreateBTNode(BTNode *&b,char *str)BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0;char ch;b=NULL;ch=strj;while(ch!='0')switch(ch)case '(':top+;Sttop=p;k=1;break;case ')':top-;break;case ',':k=2;break;de

6、fault:p=(BTNode *)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rchild=NULL;if(b=NULL)b=p;elseswitch(k)case 1:Sttop->lchild=p;break;case 2:Sttop->rchild=p;break;j+;ch=strj;/輸出void DispBTNode(BTNode *b)if(b!=NULL)printf("%c",b->data);if(b->lchild!=NULL|b->rchild!=NUL

7、L)printf("(");DispBTNode(b->lchild);if(b->rchild!=NULL)printf(",");DispBTNode(b->rchild);printf(")");/查找節(jié)點(diǎn)BTNode *FindNode(BTNode *b,ElemType x)BTNode *p;if(b=NULL)return b;else if(b->data=x)return b;elsep=FindNode(b->lchild,x);if(p!=NULL)return p;elseret

8、urn FindNode(b->rchild,x); /求高度 int BTNodeHeight(BTNode *b) int lchildh,rchildh; if(b=NULL) return (0); else lchildh=BTNodeHeight(b->lchild); rchildh=BTNodeHeight(b->rchild); return(lchildh>rchildh)?(lchildh+1):(rchildh+1); /二叉樹的結(jié)點(diǎn)個(gè)數(shù) int NodesCount(BTNode *b)if(b=NULL)return 0;elsereturn

9、 NodesCount(b->lchild)+NodesCount(b->rchild)+1; /先序遍歷遞歸void PreOrder(BTNode *b)if(b!=NULL)printf("%c",b->data);PreOrder(b->lchild);PreOrder(b->rchild);/中序遍歷遞歸void InOrder(BTNode *b)if(b!=NULL)InOrder(b->lchild);printf("%c",b->data);InOrder(b->rchild);/后序遍歷

10、遞歸void PostOrder(BTNode *b)if(b!=NULL)PostOrder(b->lchild);PostOrder(b->rchild);printf("%c",b->data);/層次遍歷void LevelOrder(BTNode *b)BTNode *p;BTNode *quMaxSize;int front,rear;front=rear=-1;rear+;qurear=b;while(front!=rear)front=(front+1)%MaxSize;p=qufront;printf("%c",p-&

11、gt;data);if(p->lchild!=NULL)rear=(rear+1)%MaxSize;qurear=p->lchild;if(p->rchild!=NULL)rear=(rear+1)%MaxSize;qurear=p->rchild;void main()BTNode *b,*p,*lp,*rp;char str="A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)"/根據(jù)樹形圖改寫成的/二叉樹括號(hào)表示法的字符串*str/char str100;scanf("%s",&str);/自行輸入括號(hào)表

12、示的二叉樹CreateBTNode(b,str); /創(chuàng)建樹bprintf("n");printf("輸出二叉樹:");/輸出二叉樹bDispBTNode(b);printf("n");printf("'H'結(jié)點(diǎn):");/找到'H'節(jié)點(diǎn)，輸出其左右孩子值p=FindNode(b,'H');printf("n");if (p!=NULL) printf("左孩子節(jié)點(diǎn)的值");printf("%c",p->

13、lchild->data);printf("n");printf("右孩子節(jié)點(diǎn)的值");printf("%c",p->rchild->data);printf("n");/此處輸出p的左右孩子節(jié)點(diǎn)的值printf("n");printf("二叉樹b的深度:%dn",BTNodeHeight(b);/輸出b的高度printf("二叉樹b的結(jié)點(diǎn)個(gè)數(shù):%dn",NodesCount(b);/輸出b的節(jié)點(diǎn)個(gè)數(shù)printf("n"

14、;);printf(" 先序遍歷序列:n");/輸出b的四種遍歷順序printf(" 算法:");PreOrder(b);printf("n");printf(" 中序遍歷序列:n");printf(" 算法:");InOrder(b);printf("n");printf(" 后序遍歷序列:n");printf(" 算法:");PostOrder(b);printf("n"); printf(" 層次遍歷序列:n");printf(" 算法:");LevelOrder(b); printf(