【2017年整理】数据结构实验三.doc
文本预览下载声明
实验报告
学院（系）名称：计算机与通信工程学院
姓名 王宏昌 学号专业 计算机科学与技术 班级 2班 实验名称 实验三 二叉树操作 课程名称 数据结构 课程代码 实验时间 2016 实验地点 7-220 批改意见 成绩
教师签字： 实验目的和二叉树性质掌握二叉树二叉二叉树遍历算法实验要求1）问题描述：在主程序中提供下列菜单：
1…建立树
2…前序遍历树
3…中序(非递归)遍历树
4…后序遍历树
0…结束
2）实验要求：
① 定义下列过程：
CreateTree(): 按从键盘输入的前序序列，创建树
PreOrderTree()：前序遍历树（递归）
InOrderTree()：中序(非递归)遍历树
LaOrderTree(): 后序遍历树（递归）
② 每位同学在实验过程中要单步运行程序，跟踪二叉树的创建过程与前序遍历的递归过程。
2. 树的转换我们都知道用“兄弟”可以将一棵一般的树转换为二叉树请将树用这种方法转换为二叉树，并输出转换前和转换后树的。
1.
#includestdio.h
#includestdlib.h
#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=root;
if(!rot)
return;
while(!(rot==NULLtop==0))
{
while(rot)
{
if(topMax-1)
{
stack[top]=rot;
top++;
}
else
{
printf(ERROR! FULL!);
return;
}
rot=rot-lchild;
}
if(top=0)
return;
else
{
top--;
rot=stack[top];
printf(%c ,stack[top]-data);
rot=rot-rchild;
}
}
}
void LaOrderTree(DoubTree *root)
{
DoubTree *rot;
rot=root;
if(rot==NULL)
return;
LaOrderTree(rot-lchild);
LaOrderTree(rot-rchild);
printf(%c ,rot-data);
}
int main()
{
DoubTree *DTree;
printf(Enter Tree`s Order: );
DTree=CreateTree();
printf(Recursion: PreOrder is: );
PreOrderTree(DTree);
printf(\nNon-Recursion: InOrder is: );
InOrderTree(DTree);
printf(\nRecursion: LaOrder is: );
LaOrderTree(DTree);
return 0;
}
第2页 共4页
显示全部