《二叉树基本操作--实验报告》由会员分享，可在线阅读，更多相关《二叉树基本操作--实验报告（8页珍藏版）》请在金锄头文库上搜索。
1、实验报告一、实验目的1、熟悉二叉树树的基本操作。2、掌握二叉树的实现以及实际应用。3、加深二叉树的理解，逐步培养解决实际问题的编程能力。二、实验环境1 台 WINDOWS 环境的 PC 机，装有 Visual C+ 6.0。三、实验内容【问题描述】现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。 其中操作函数包括：1创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链 式存储结构。2输出二叉树DispBTNode(*b):以括号表示法输出一棵二叉树。3查找结点FindNode(*b,x):在二叉树b中寻找data
2、域值为x的结点，并返回指向该结点 的指针。4求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空，则其高度为0；否则，其 高度等于左子树与右子树中的最大高度加1。5 求二叉树的结点个数NodesCount(BTNode *b)6 先序遍历的递归算法：void PreOrder(BTNode *b)7中序遍历的递归算法：void InOrder(BTNode *b)8 后序遍历递归算法：void PostOrder(BTNode *b)9 层次遍历算法 void Leve1Order(BTNode *b)【基本要求】实现以上9个函数。主函数中实现以下功能：创建下图中的树b输出二叉
3、树b找到H节点，输出其左右孩子值输出b的高度输出b的节点个数输出b的四种遍历顺序上图转化为二叉树括号表示法为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);/创建
4、 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
5、 *&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;ca
6、se 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
7、(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);elselchildh=BTNodeHeight(b-lchild);rchildh=BTNodeHeight(b-rchild);return(lchildhrchildh)?(lchildh+1):(rchildh+1);二叉树的结点个数int Nodes
8、Count(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 Po
9、stOrder(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)%Max
10、Size;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); /创建树 b printf(n);printf(输出二叉树:，输出二叉树bDispBTNode(b);printf(
11、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)
12、;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);H结亳左孩子节点的僖 右孩子节点的n o c o列EH列HL列NM列DE序BD序BJ序JL序BC历:A历:D历:D历:AOt-SMWM次算 先中后层UJ n a四、实验心得与小结通过实验，我熟悉二叉树树的基本操作，掌握二叉树的实现以及实际应用。力口 深了对二叉树的理解，逐步培养解决实际问题的编程能力以及进一步了解了二叉树 图转化为括号表示法。递归的使用，要注意，初始时的状态以及如何使用递归，注 意普遍性，思考时从普通的开始。通过这次上机操作，让我明白书本上的程序一定 要自己去调试，这样才能将书本程序与老师讲的内容融会贯通，达到温故而知新。五、指导教师评议成绩评定：指导教师签名：
