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

实验三二叉树的基本操作学院:物理与电子学院班级:电信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的四种遍历顺序ABDCEHJKLMNFGI3、程序编写上图转化为二叉树括号表示法为A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)程序:#include #include #define MaxSize 100typedef char ElemType;typedef struct nodeElemType 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 *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;default: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!=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;elsep=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(lchildhrchildh)?(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 *quMaxSize;int front,rear;front=rear=-1;rear+;qurear=b;while(front!=rear)front=(front+1)%MaxSize;p=qufront;printf(%c,p-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);/自行输入括号表示的二叉树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的深度:%dn,BTNodeHeight(b);/输出b的高度printf(二叉树b的结点个数:%dn,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);四、实验心得与小结通过本次实验，我熟悉二叉树的基本知识内容，对课本的知识有了更加深刻的理解与掌握掌握。通过查阅资料以及百度一些前人的程序设计，我学到了很多原来在课堂上掌握不到的东西，这次是