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

《二叉树基本操作--实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.实验三二叉树的基本操作学院:物理与电子学院班级:电信1105班姓名:刘岩学号:1404110729教育资料.教育资料.一、实验目的1、熟悉二叉树的基本操作，掌握二叉树的实现以及实际应用。3、加深对于二叉树的理解，逐步培养解决实际问题的编程能力。二、实验环境1台WINDOWS环境的PC机，装有VisualC++6.0。三、实验内容1、问题描述现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：1>创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字

2、符串*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>中序遍历的递归算法：voidInOrde

3、r(BTNode*b)8>后序遍历递归算法：voidPostOrder(BTNode*b)9>层次遍历算法voidLevelOrder(BTNode*b)2、基本要求实现以上9个函数。主函数中实现以下功能：创建下图中的树b输出二叉树b找到’H’节点，输出其左右孩子值输出b的高度输出b的节点个数输出b的四种遍历顺序教育资料.ABDCEHJKLMNFGI3、程序编写上图转化为二叉树括号表示法为A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))程序:#include#include<

4、malloc.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;/*数据元素*/structnode*lchild;/*指向左孩子*/structnode*rchild;/*指向右孩子*/}BTNode;voidCreateBTNode(BTNode*&b,char*str);//创建BTNode*FindNode(BTNode*b,ElemTypex);//查找节点intBTNodeHeight(BTNode*b);//求高度v

5、oidDispBTNode(BTNode*b);//输出intNodesCount(BTNode*b);//二叉树的结点个数voidPreOrder(BTNode*b);//先序遍历递归voidInOrder(BTNode*b);//中序遍历递归voidPostOrder(BTNode*b);//后序遍历递归voidLevelOrder(BTNode*b);//层次遍历//创建voidCreateBTNode(BTNode*&b,char*str){教育资料.BTNode*St[MaxSize],*p=NULL;int

6、top=-1,k,j=0;charch;b=NULL;ch=str[j];while(ch!=''){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]->lch

7、ild=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

8、

9、b->rchild!=NULL){printf("(");DispBTNode(b->lchild);if(b->rchild!=NULL)printf(",");DispBTNode(b->rchild);printf(")");}}}

10、//查找节点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;elsereturnFindNod