实验三二叉树的基本操作学院:物理与电子学院班级:电信1105班姓名:刘岩学号:1404110729一、实验目的1、熟悉二叉树的基本操作，掌握二叉树的实现以及实际应用。
3、加深对于二叉树的理解，逐步培养解决实际问题的编程能力。
二、实验环境1台WINDOWS环境的PC机，装有Visual C++ 6.0。
三、实验内容1、问题描述现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。
其中操作函数包括：1>创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链式存储结构。
2>输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。
3>查找结点FindNode(*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(BTNode *b)2、基本要求实现以上9个函数。
主函数中实现以下功能：创建下图中的树b输出二叉树b找到’H’节点，输出其左右孩子值输出b的高度输出b的节点个数输出b的四种遍历顺序3、程序编写上图转化为二叉树括号表示法为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 node{ElemType data; /*数据元素*/struct node *lchild; /*指向左孩子*/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 PostOrder(BTNode *b);//后序遍历递归void LevelOrder(BTNode *b);//层次遍历//创建void CreateBTNode(BTNode *&b,char *str){BTNode *St[MaxSize],*p=NULL;int top=-1,k,j=0;char ch;b=NULL;ch=str[j];while(ch!='\0'){switch(ch){case '(':top++;St[top]=p;k=1;break;case ')':top--;break;case ',':k=2;break;default:p=(BTNode *)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)b=p;else{switch(k){case 1:St[top]->lchild=p;break;case 2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}//输出void DispBTNode(BTNode *b){if(b!=NULL){printf("%c",b->data);if(b->lchild!=NULL||b->rchild!=NULL){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;else{p=FindNode(b->lchild,x);if(p!=NULL)return p;elsereturn 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 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);}}//后序遍历递归void PostOrder(BTNode *b){if(b!=NULL){PostOrder(b->lchild);PostOrder(b->rchild);printf("%c",b->data);}}//层次遍历void LevelOrder(BTNode *b){BTNode *p;BTNode *qu[MaxSize];int front,rear;front=rear=-1;rear++;qu[rear]=b;while(front!=rear){front=(front+1)%MaxSize;p=qu[front];printf("%c",p->data);if(p->lchild!=NULL){rear=(rear+1)%MaxSize;qu[rear]=p->lchild;}if(p->rchild!=NULL){rear=(rear+1)%MaxSize;qu[rear]=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 str[100];scanf("%s",&str);//自行输入括号表示的二叉树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->lchild->data);printf("\n");printf("右孩子节点的值");printf("%c",p->rchild->data);printf("\n");//此处输出p的左右孩子节点的值}printf("\n");printf("二叉树b的深度:%d\n",BTNodeHeight(b));//输出b的高度printf("二叉树b的结点个数:%d\n",NodesCount(b));//输出b的节点个数printf("\n");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("\n");}四、实验心得与小结通过本次实验，我熟悉二叉树的基本知识内容，对课本的知识有了更加深刻的理解与掌握掌握。
