1、實驗報告第 7 頁 共 7 頁一、實驗目的1、熟悉二叉樹樹的基本操作。2、掌握二叉樹的實現以及實際應用。3、加深二叉樹的理解，逐步培養解決實際問題的編程能力。二、實驗環境1臺WINDOWS環境的PC機，裝有Visual C+ 6.0。三、實驗內容【問題描述】現需要編寫一套二叉樹的操作函數，以便用戶能夠方便的利用這些函數來實現自己的應用。其中操作函數包括：1> 創建二叉樹CreateBTNode(*b,*str)：根據二叉樹括號表示法的字符串*str生成對應的鏈式存儲結構。2> 輸出二叉樹DispBTNode(*b)：以括號表示法輸出一棵二叉樹。3> 查找結點FindNode(

2、*b,x)：在二叉樹b中尋找data域值為x的結點,并返回指向該結點的指針。4> 求高度BTNodeDepth(*b)：求二叉樹b的高度。若二叉樹為空,則其高度為0；否則,其高度等于左子樹與右子樹中的最大高度加l。5> 求二叉樹的結點個數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)【基本要求】實現以上9個函數。主函數中實現以下功能：創建下圖中的樹b輸出二叉樹b找到H節點，輸出其左右孩子值輸出b的高度輸出b的節點個數輸出b的四種遍歷順序ABDCEHJKLMNFGI上圖轉化為二叉樹括號表示法為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;/*數據元素*/struct node *lchild;/*指

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

5、ostOrder(BTNode *b);/后序遍歷遞歸void LevelOrder(BTNode *b);/層次遍歷/創建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(")");/查找節點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); /二叉樹的結點個數 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)"/根據樹形圖改寫成的/二叉樹括號表示法的字符串*str/char str100;scanf("%s",&str);/自行輸入括號表

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

13、lchild->data);printf("n");printf("右孩子節點的值");printf("%c",p->rchild->data);printf("n");/此處輸出p的左右孩子節點的值printf("n");printf("二叉樹b的深度:%dn",BTNodeHeight(b);/輸出b的高度printf("二叉樹b的結點個數:%dn",NodesCount(b);/輸出b的節點個數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(