二叉树基本操作--实验报告.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);四、实验心得与小结通过本次实验，我熟悉二叉树的基本知识内容，对课本的知识有了更加深刻的理解与掌握掌握。通过查阅资料以及百度一些前人的程序设计，我学到了很多原来在课堂上掌握不到的东西，这次是我的第一次完成了二叉树的实现以及实际应用。加深了对二叉树的理解，。本次实验还运用到了递归的使用，是非常新的体验，原来都是停留在概念上的运用递归处理，这次运用到了实际的实验编程中，受益匪浅。这次实验，让我明白了一个道理，实践出真知，只有通过自己的双手实践，才能更好的理解知识与运用。 【本文档内容可以自由复制内容或自由编辑修改内容期待你的好评和关注，我们将会做得更好】精选范本,供参考！