数据结构实验三.doc

文档介绍：实验报告
学院(系)名称:计算机与通信工程学院
姓名
王宏昌
学号
20135628
专业
计算机科学与技术
班级
2班
实验名称
实验三二叉树操作
课程名称
数据结构
课程代码
实验时间
2016
实验地点
7-220
批改意见
成绩
教师签字:
实验目的
理解二叉树的逻辑特点和二叉树的性质;掌握二叉树的二叉链表存储结构,掌握二叉树的创建算法、遍历算法的递归与非递归实现。
实验要求
具体实验题目:(任课教师根据实验大纲自己指定)
第1题为必做题,第2题为选做题目:
:以二叉链表为存储结构,实现二叉树的创建、遍历算法
1)问题描述:在主程序中提供下列菜单:
1…建立树
2…前序遍历树
3…中序(非递归)遍历树
4…后序遍历树
0…结束
2)实验要求:
①定义下列过程:
CreateTree(): 按从键盘输入的前序序列,创建树
PreOrderTree():前序遍历树(递归)
InOrderTree():中序(非递归)遍历树
LaOrderTree(): 后序遍历树(递归)
②每位同学在实验过程中要单步运行程序,跟踪二叉树的创建过程与前序遍历的递归过程。
2. 树的转换:我们都知道用“孩子兄弟”表示法可以将一棵一般的树转换为二叉树。请设计算法将一棵树用这种方法转换为二叉树,并输出转换前和转换后树的前序遍历序列。
实验过程记录(源程序、测试用例、测试结果及心得体会等)
1.
#include<>
#include<>
#define Max 100
typedef struct DoubTree
{
char data;
struct DoubTree *lchild,*rchild;
}DoubTree;
DoubTree *CreateTree()
{
DoubTree *root;
char s;
root=(DoubTree * )malloc(sizeof(DoubTree));
if(!root)
{
printf("ERROR! NO SPACE! EXIT!");
exit(1);
}
scanf("%c", &s);
if(s=='#')
root=NULL;
else
{
root->data=s;
root->lchild=CreateTree();
root->rchild=CreateTree();
}
return root;
}
void PreOrderTree(DoubTree *root)
{
DoubTree *rot;
rot=root;
if(rot==NULL)
return;
printf("%c ",rot->data);
PreOrderTree(rot->lchild);
PreOrderTree(rot->rchild);
}
void InOrderTree(DoubTree *root)
{
DoubTree *rot, *stack[Max];
int top=0;
rot=r