《二叉树基本操作--实验报告》由会员分享，可在线阅读，更多相关《二叉树基本操作--实验报告（7页珍藏版）》请在金锄头文库上搜索。
1、实验报告第 1 页 共 7 页一、实验目的1、熟悉二叉树树的基本操作。2、掌握二叉树的实现以及实际应用。3、加深二叉树的理解，逐步培养解决实际问题的编程能力。二、实验环境1台WINDOWS环境的PC机，装有Visual C+ 6.0。三、实验内容【问题描述】现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：1 创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链式存储结构。2 输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。3 查找结点FindNode(*b,x)：在二叉树b中
2、寻找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)【基本要求】实现以上9个函数。主函数中实现以下功能：创建下图
3、中的树b输出二叉树b找到H节点，输出其左右孩子值输出b的高度输出b的节点个数输出b的四种遍历顺序ABDCEHJKLMNFGI上图转化为二叉树括号表示法为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
4、 *&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 Crea
5、teBTNode(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-lc
6、hild=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
7、 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
8、); /二叉树的结点个数 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-rc
9、hild);/后序遍历递归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)re
10、ar=(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(输出二叉树:);/输出二叉树bDispBTNod
11、e(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的节点个数print
12、f(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);四、实验心得与小结通过实验，我熟悉二叉树树的基本操作，掌握二叉树的实现以及实际应用。加深了对二叉树的理解，逐步培养解决实际问题的编程能力以及进一步了解了二叉树图转化为括号表示法。递归的使用，要注意，初始时的状态以及如何使用递归，注意普遍性，思考时从普通的开始。通过这次上机操作，让我明白书本上的程序一定要自己去调试，这样才能将书本程序与老师讲的内容融会贯通，达到温故而知新。五、指导教师评议成绩评定： 指导教师签名：
