数据结构实验报告.doc

数学与计算机学院
实验报告
( / 学年第学期)
课程名称
数据结构
课程代码
任课教师
龚俊
指导教师
龚俊
学生姓名
袁红梅
学号
332008090101014
年级
08级(3)
专业
计算机科学与技术
综合成绩
实验名称
实验四
指导教师
龚俊
实验类型
□验证
√综合
实验学时
2
实验日期
实验时间

实验编号
1
分组号
1
实验地点
6A-418
实验目的和要求
1)熟练掌握二叉树的二叉链表表示及前序创建算法与实现;
2)熟练掌握二叉树的前序、中序和后序递归遍历算法与实现;
3)掌握中序遍历线索二叉树的基本算法与实现
4)掌握中序遍历线索化二叉树的算法与实现;
5)按照实验题目要求独立完成实验内容(提交程序清单及相关实验数据与运行结果);
6)认真书写实验报告,并按时提交。
二、实验环境(实验设备)
硬件:微型计算机设备一套
软件:
Windows XP
Visual VC++
三、实验内容
实验内容:
1)按照先序序列建立下图所示二叉树的二插链表树,结点元素类型取字符型,树的字符序列从键盘逐个动态输入。
2)在第1)步建立好的二叉链表树上实施前序、中序和后序递归遍历,并输出相应遍历序列。
3) 在第1) 步建立好的二叉链表树上实施前序遍历的叶子结点输出。
4) 在第1) 步建立好的二叉链表树上实施前序遍历的非叶子结点输出。
5)中序线索化第1)步所建立的二叉链表树(选做)。
6)中序遍历第5)步所建立的线索二叉树,并输出遍历结果(选做)
实验解答:
定义四个结构体
struct elem_N
{
int data;
elem_N *next;
};
struct elem_T
{
char data;
elem_T *next;
};
struct stack_N
{
elem_N *top;
int length;
};
struct stack_T
{
elem_T *top;
int length;
};
,T栈函数
void Init_stack_N(stack_N *S)
{
S->top=NULL;
S->length=0;
}
void Init_stack_T(stack_T *S)
{
S->top=NULL;
S->length=0;
}
,T函数的出栈函数
void Push_N(stack_N *S,int e)
{
elem_N *p;
p=new elem_N;
if(!p)exit(0);
p->data=e;
p->next=S->top;
S->top=p;
S->length++;
}
void Push_T(stack_T *S,char e)
{
elem_T *p;
p=new elem_T;
if(!p)exit(0);
p->data=e;
p->next=S->top;
S->top=p;
S->length++;
}
,T栈的顶点函数