二叉树基本操作--实验报告

第1页共7页实验报告一、实验目的1、熟悉二叉树树的基本操作。2、掌握二叉树的实现以及实际应用。3、加深二叉树的理解，逐步培养解决实际问题的编程能力。二、实验环境1台WINDOWS环境的PC机，装有VisualC++6.0。三、实验内容【问题描述】现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：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先序遍历的递归算法：voidPreOrder(BTNode*b)7中序遍历的递归算法：voidInOrder(BTNode*b)8后序遍历递归算法：voidPostOrder(BTNode*b)9层次遍历算法voidLevelOrder(BTNode*b)【基本要求】实现以上9个函数。主函数中实现以下功能：创建下图中的树b输出二叉树b找到’H’节点，输出其左右孩子值输出b的高度输出b的节点个数第2页共7页输出b的四种遍历顺序上图转化为二叉树括号表示法为A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))程序:#includestdio.h#includemalloc.h#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;/*数据元素*/structnode*lchild;/*指向左孩子*/structnode*rchild;/*指向右孩子*/}BTNode;voidCreateBTNode(BTNode*&b,char*str);//创建BTNode*FindNode(BTNode*b,ElemTypex);//查找节点intBTNodeHeight(BTNode*b);//求高度voidDispBTNode(BTNode*b);//输出intNodesCount(BTNode*b);//二叉树的结点个数voidPreOrder(BTNode*b);//先序遍历递归voidInOrder(BTNode*b);//中序遍历递归voidPostOrder(BTNode*b);//后序遍历递归ABDCEHJKLMNFGI第3页共7页voidLevelOrder(BTNode*b);//层次遍历//创建voidCreateBTNode(BTNode*&b,char*str){BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;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){case1:St[top]-lchild=p;break;case2:St[top]-rchild=p;break;}}}j++;ch=str[j];}}//输出voidDispBTNode(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());}}}第4页共7页//查找节点BTNode*FindNode(BTNode*b,ElemTypex){BTNode*p;if(b==NULL)returnb;elseif(b-data==x)returnb;else{p=FindNode(b-lchild,x);if(p!=NULL)returnp;elsereturnFindNode(b-rchild,x);}}//求高度intBTNodeHeight(BTNode*b){intlchildh,rchildh;if(b==NULL)return(0);else{lchildh=BTNodeHeight(b-lchild);rchildh=BTNodeHeight(b-rchild);return(lchildhrchildh)?(lchildh+1):(rchildh+1);}}//二叉树的结点个数intNodesCount(BTNode*b){if(b==NULL)return0;elsereturnNodesCount(b-lchild)+NodesCount(b-rchild)+1;}//先序遍历递归voidPreOrder(BTNode*b){if(b!=NULL){printf(%c,b-data);PreOrder(b-lchild);PreOrder(b-rchild);第5页共7页}}//中序遍历递归voidInOrder(BTNode*b){if(b!=NULL){InOrder(b-lchild);printf(%c,b-data);InOrder(b-rchild);}}//后序遍历递归voidPostOrder(BTNode*b){if(b!=NULL){PostOrder(b-lchild);PostOrder(b-rchild);printf(%c,b-data);}}//层次遍历voidLevelOrder(BTNode*b){BTNode*p;BTNode*qu[MaxSize];intfront,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;}}}voidmain()第6页共7页{BTNode*b,*p,*lp,*rp;charstr[]=A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)));//根据树形图改写成的//二叉树括号表示法的字符串*str//charstr[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);}第7页共7页四、实验心得与小结通过实验，我熟悉二叉树树的基本操作，掌握二叉树的实现以及实际应用。加深了对二叉树的理解，逐步培养解决实际问题的编程能力以及进一步了解了二叉树图转化为括号表示法。递归的使用，要注意，初始时的状态以及如何使用递归，注意普遍性，思考时从普通的开始。通过这次上机操作，让我明白书本上的程序一定要自己去调试，这样才能将书本程序与老师讲的内容融会贯通，达到温故而知新。五、指导教师评议成绩评定：指导教师签名：