数据结构实验报告二叉树.doc
-实 验 报 告实验名称二叉树实验评分：实验课时4课时实验地点综合楼E405实验时间2016年4月 24日 星期三 第5周实验目的及要求实验目的：通过序列构造二叉树的实验，进一步熟悉二叉树遍历及构造二叉树的过程，掌握根本知识点，发现理论学习中的缺乏；理清学习脉络；能独立思考，根据具体的序列组织数据，合理显示二叉树。实验要求：1用树形构造画出一棵二叉树在结论中画出，采用凹入表示法和括号表示确输出该树。 2分析该二叉树的先序遍历、中序遍历和后序遍历的结果。3根据二叉树的根本运算，设计先序遍历和中序遍历或者中序遍历和后序遍历，确定二叉树的算法。4在不改变原有二叉树构造的条件下，将二叉树左右孩子进展交换，并采用凹入表示法和括号表示法输出原有二叉树及交换子树后的二叉树。实验设备软件、硬件及耗材软件环境：Win7 microsoft visual6+硬件环境：intel core i5 cpu,4G存，64位操作系统实验容算法、程序、步骤、方法及数据记录实验容算法、程序、步骤、方法及数据记录实验容算法、程序、步骤、方法及数据记录实验容算法、程序、步骤、方法及数据记录一，源代码1：头文件#include<stdio.h>#include<malloc.h>#define ma*size 100typedef char elemtype;typedef struct nodeelemtype data;struct node *lchild;struct node *rchild;btnode;e*tern void createbtnode(btnode *&b,char *str);e*tern void dispbtnode(btnode *b);e*tern void destroybtnode(btnode *&b);e*tern void preorder(btnode *b);e*tern void inorder(btnode *b);e*tern void postorder(btnode *b);e*tern btnode *createbt1(char *pre,char *in,int n);e*tern btnode *createbt2(char *post,char *in,int n,int m);e*tern void dispbtnode1(btnode *b);e*tern btnode * revers(btnode *b);e*tern btnode *rchildnode(btnode *p);e*tern btnode *lchildnode(btnode *p);二源代码2：主函数：包括括号表示法，凹入表示法以及根据先序，中序确定二叉树。#include<stdio.h>#include"btnodes.h"void main()btnode *b;createbtnode(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)");printf("二叉树的根本运算入下：n");printf("1输出二叉树：");dispbtnode(b);printf("n");printf("先序遍历序列:");preorder(b);printf("n");printf("中序遍历序列:");inorder(b);printf("n");printf("后序遍历序列:");postorder(b);printf("n");elemtype pre="ABDEHJKLMNCFGI"elemtype in="DBJHLKMNEAFCGI"b=createbt1(pre,in,14);printf("先序序列:%sn",pre);printf("中序序列:%sn",in);printf("先序中序构造一棵二叉树b:n");printf("括号表示法:");dispbtnode(b);printf("n");printf("凹入表示法:n");dispbtnode1(b);printf("nn");printf("交换左右孩子后的二叉树为:n");createbtnode(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)");revers(b);dispbtnode1(b);printf("(7)释放二叉树bn");destroybtnode(b);3、 源代码3：功能块1） 根据根据先序，中序确定二叉树。以及凹入法表示#include "btnodes.h"btnode *createbt1(char *pre,char *in,int n)btnode *s;char *p;int k;if(n<=0)return NULL;s=(btnode *)malloc(sizeof(btnode);s->data =*pre;for(p=in;p<in+n;p+)if(*p=*pre)break;k=p-in;s->lchild =createbt1(pre+1,in,k);s->rchild =createbt1(pre+k+1,p+1,n-k-1);return s;void dispbtnode1(btnode *b)btnode *stma*size,*p;int levelma*size2,top=-1,n,i,width=4;char type;if(b!=NULL)top+;sttop=b;leveltop0=width;leveltop1=2;while(top>-1)p=sttop;n=leveltop0;switch(leveltop1)case 0:type='l'break;case 1:type='r'break;case 2:type='b'break;for(i=1;i<=n;i+)printf(" ");printf("%c(%c)",p->data,type);for(i=n+1;i<=2*ma*size/width;i+=2)printf("-");printf("n");top-;if(p->rchild!=NULL)top+;sttop=p->rchild;leveltop0=n+width;leveltop1=1;if(p->lchild!=NULL)top+;sttop=p->lchild;leveltop0=n+width;leveltop1=0;2） 先序，中序、后序遍历功能实现，因为想自己更能读懂理解程序，没有使用递归算法。#include "btnodes.h"void preorder(btnode *b)/先序遍历btnode *stma*size,*p;int top=-1;if(b!=NULL)top+;sttop=b;while(top>-1)p=sttop;top-;printf("%c",p->data);if(p->rchild!=NULL)top+;sttop=p->rchild;if(p->lchild!=NULL)top+;sttop=p->lchild;printf("n");void inorder(btnode *b)/中序遍历btnode *stma*size,*p;int top=-1;if(b!=NULL)p=b;while(top>-1|p!=NULL) while(p!=NULL)top+;sttop=p;p=p->lchild;if(top>-1) p=sttop; top-; printf("%c",p->data); p=p->rchild;printf("n");void postorder(btnode *b)/后序遍历btnode *stma*size;btnode *p;int flag,top=-1;if(b!=NULL)dowhile(b!=NULL)top+;sttop=b;b=b->lchild;p=NULL;flag=1;while(top!=-1&&flag) b=sttop;if(b->rchild=p) printf("%c",b->data); top-; p=b;else b=b->rchild; flag=0;while(top!=-1);printf("n");3） 二叉树的根本运算：#include"btnodes.h"void createbtnode(btnode *&b,char *str)btnode *stma*size,*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; else switch(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(")");void destroybtnode(btnode *&b)if(b!=NULL)destroybtnode(b->lchild);destroybtnode(b->rchild);free(b); btnode *lchildnode(btnode *p) return p->lchild ; btnode *rchildnode(btnode *p) return p->rchild ; btnode * revers(btnode *b)/交换左右子树if(b!=NULL)if(b->rchild !=NULL|b->lchild !=NULL) btnode *p,*q; p=revers(b->lchild ); q=b->rchild ; b->rchild =p; b->lchild =q; q=revers(b->rchild);return b;结 论(结果及体会)一、结果如下：BACGDEFIHKJMLN2、 体会： 在这次的实验中主要涉及到采用先序、中序来构造树、在树换他的左右子树。再打代码过程中，因为是照着书打的，ma*width变量没有定义，程序出错，仔细阅读下程序，改了下，解决了问题，在进展交换的时候，因为想的太过复杂，最初编写的时候出现了一点问题，其实就只要定义两个变量，找到左右孩子，进展交换，其中用到两次递归来实现。指导教师评 议指导教师签名：年 月 日. z.
