数据结构实验报告二叉树

1、实 验 报 告实验名称二叉树实验评分：实验课时4课时实验地点综合楼E405实验时间2016年4月 24日 星期三 第5周实验目的及要求实验目的：通过序列构造二叉树的实验，进一步熟悉二叉树遍历及构造二叉树的过程，掌握基本知识点，发现理论学习中的不足；理清学习脉络；能独立思考，根据具体的序列组织数据，合理显示二叉树。实验要求：（1）用树形结构画出一棵二叉树（在结论中画出），采用凹入表示法和括号表示法正确输出该树。 （2）分析该二叉树的先序遍历、中序遍历和后序遍历的结果。（3）根据二叉树的基本运算，设计先序遍历和中序遍历（或者中序遍历和后序遍历），确定二叉树的算法。（4）在不改变原有二叉树结构的条件

2、下，将二叉树左右孩子进行交换，并采用凹入表示法和括号表示法输出原有二叉树及交换子树后的二叉树。实验设备（软件、硬件及耗材）软件环境：Win7 microsoft visual6+ 硬件环境：intel core i5 cpu,4G内存，64位操作系统实验内容（算法、程序、步骤、方法及数据记录）实验内容（算法、程序、步骤、方法及数据记录）实验内容（算法、程序、步骤、方法及数据记录）实验内容（算法、程序、步骤、方法及数据记录）一，源代码（1）：头文件#include<stdio.h>#include<malloc.h>#define maxsize 100typedef c

3、har elemtype;typedef struct nodeelemtype data;struct node *lchild;struct node *rchild;btnode;extern void createbtnode(btnode *&b,char *str);extern void dispbtnode(btnode *b);extern void destroybtnode(btnode *&b);extern void preorder(btnode *b);extern void inorder(btnode *b);extern void posto

4、rder(btnode *b);extern btnode *createbt1(char *pre,char *in,int n);extern btnode *createbt2(char *post,char *in,int n,int m);extern void dispbtnode1(btnode *b);extern btnode * revers(btnode *b);extern btnode *rchildnode(btnode *p);extern btnode *lchildnode(btnode *p);二源代码（2）：主函数：包括括号表示法，凹入表示法以及根据先序，

5、中序确定二叉树。#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"

6、);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(&q

7、uot;先序中序构造一棵二叉树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&q

8、uot;);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 =createbt

9、1(pre+1,in,k);s->rchild =createbt1(pre+k+1,p+1,n-k-1);return s;void dispbtnode1(btnode *b)btnode *stmaxsize,*p;int levelmaxsize2,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

10、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*maxsize/width;i+=2)printf("-");printf("n");top-;if(p->rchild!=NULL)top+;sttop=p->rchild;leveltop0=n+width;leveltop1=1;i

11、f(p->lchild!=NULL)top+;sttop=p->lchild;leveltop0=n+width;leveltop1=0;2） 先序，中序、后序遍历功能实现，因为想自己更能读懂理解程序，没有使用递归算法。#include "btnodes.h"void preorder(btnode *b)/先序遍历btnode *stmaxsize,*p;int top=-1;if(b!=NULL)top+;sttop=b;while(top>-1)p=sttop;top-;printf("%c",p->data);if(p-&

12、gt;rchild!=NULL)top+;sttop=p->rchild;if(p->lchild!=NULL)top+;sttop=p->lchild;printf("n");void inorder(btnode *b)/中序遍历btnode *stmaxsize,*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"

13、,p->data); p=p->rchild;printf("n");void postorder(btnode *b)/后序遍历btnode *stmaxsize;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

14、 b=b->rchild; flag=0;while(top!=-1);printf("n");3） 二叉树的基本运算：#include"btnodes.h"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 ')'

15、;: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",

16、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;