数据结构_实验三树结构算法设计---梦朝思夕

1、中国矿业大学计算机科学与技术系试验报告课程名称数据结构试验名称实验三树结构算法设计班级信息安全092 姓名梦朝思夕学号_08093739 仪器组号 实验日期10-12-18实验报告要求：1.实验目的 2.实验内容3.实验步骤4.程序清单5.运行结果 6.流程图7 实验体会一实验目的1理解树结构的逻辑特性；2熟练掌握二叉树的逻辑结构特性及各种存储方法。3熟练掌握二插树的各种基本操作，尤其是三种遍历算法以及线索化算法；4进一步了解和掌握类的私有和公有成员函数的定义和使用以及类型的作用域。二、实验要求：1实验之前认真准备，编写好源程序。2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮

2、性的验证。3不断积累程序的调试方法。三、实验内容 基本题(必做)：1试写出中序遍历二叉树的递归算法 和 非递归算法。2写出中序线索二叉树的中序遍历算法。四、程序清单基本题：1. #define maxsize 10#include "stdio.h'*#include "malloc.h"#define null 0typedef struct node char data;struct node *lchild,*rchild; bitree;bi tree *qmaxsize;bitree *creatree ()char ch; int front,

3、rear;bitree *t,*s;t 二 null;front=l,rear=0;ch=getchar();while (ch!='#')s=null;if(ch!=)s=(bitree *)malloc(sizeof (bitree); s->data=ch;s->lchild=s->rchild=null;rear+;qrear=s;if(rear=l) t=s;elseif(s!=null&&qfront!=null)if (rear%2=0)q front ->lchild=s;else qfront->rchild=s;

4、 if(rear%2=l) front+;ch=getchar();return t;void inorder (bitree *t)if(t) inorder(t->lchild);printf(',%4c'*,t->data);inorder(t->rchild);void main()bitree *tr;printf("创建二叉树：n请输入结点信息：”)； tr=creatree();printf(“中序遍历二叉树的结果为：”)；inorder(tr);printf("n");2. #define maxsize 100#

5、include "stdio.h"#include "malloc.h"#definenull0# define stackmaxsize 100typedef struct node char data;struct node *lchild,*rchild; bitree;typedef struct bitree stack fstackmaxsize;int top;stack;void initstack (stack *s)(*s).top=-l;void push(stack *s,bilree *ch)(*s).top+;(*s).sta

6、ck(*s).top=*ch;bitree *pop(stack *s)bitree pl,*p=&pl;*p=(*s).stack(*s).top;(*s).top;return p;1int empty(stack *s)if(*s).top=二 1 )return 1;else return 0;bitree *qmaxsize;bitree *creatree ()char ch; int front,rear;bitree *t,*s;t=null;front=l,rear=0; ch=getchar(); while (ch!二#) s=null; if(ch!=) s=(

7、bitree *)malloc(sizeof (bitree); s->data=ch;s->lchild=s->rchild=null;rear+;qfrear=s; if(rear=l) t=s;elseif (s!=null&&qfront!=null)if (rear%2=0)qfront->lchild=s;else qfront->rchild=s; if(rear%2=l) front+;1 ch=getchar();return t;void inorder (bitree *t)bitree *p=t;stack sl*s=&s1;initstack(s);while (p!=null|(!empty(s) if(p!=null) push(s,p);p=p->lchild;else p=pop(s);p