中序遍历线索化二叉树算法的设计与实现实验报告.docVIP

数学与计算科学学院

实验报告

实验工程名称中序遍历线索化二叉树算法的设计与实现

所属课程名称数据结构A

实验类型设计型

实验日期2014.11.26

班级信计1302班

学号201353100216

姓名危志鹏

成绩

一、实验概述：

【实验目的】

1.掌握二叉链表及线索二叉链表的特点及根本运算。

【实验原理】

//-----二叉树的二叉线索存储表示-----

TypedefenumPointerTag{Link,Thread};

TypedefstructBiThrNode{

TElemTypedata;

StructBiThrNode*lchild,*rchild;

PointerTagLTag,RTag;

}BiThrNode,*BiThrTree;

【实验环境】

VC++6.0

二、实验内容：

【实验方案】

在VC++环境下，编写二叉树的线索链表存储结构，中序遍历二叉线索树T的非递归算法，以及将二叉树T的中序线索化算法，对每个数据元素均调用函数Visit。最后设计主函数，调用以上算法，验证算法的正确性，调试运行，得出结果。

【实验过程】〔实验步骤、记录、数据、分析〕

运行VC++6.0，建立新的命令文件；

将程序输入，如下，发现一个错误。

经过查找，发现一个错误，然后改正如下

然后进行调试，发现调试出错。

【实验结论】〔结果〕

【实验小结】〔收获体会〕

这次实验又出现了和上次一样的错误：程序无错误，但结果不能运行。经过屡次的检查终于解决了问题，相信这样的错误不会再有第三次了。

三、指导教师评语及成绩：

评语

评语等级

优

良

中

及格

不及格

1.实验报告按时完成,字迹清楚,文字表达流畅,逻辑性强

2.实验方案设计合理

3.实验过程〔实验步骤详细,记录完整,数据合理,分析透彻〕

4实验结论正确.

成绩：

指导教师签名：

批阅日期：

附录1：源程序

#includestdio.h

#includestdlib.h

#defineOK1

#defineERROR0

#defineOVERFLOW-2

typedefintStatus;

typedefcharTElemType;

typedefenumPointerTag{Link,Thread};//Link==0:指针，Thread==1:线索

typedefstructBiThrNode{

TElemTypedata;

structBiThrNode*lchild,*rchild;//左右孩子指针

PointerTagLTag,RTag;//左右标志

}BiThrNode,*BiThrTree;

StatusVisit(TElemTypee){

printf(%c,e);//输出元素e的值

returnOK;

}

StatusCreateBiThrTree(BiThrTreeT){

//按先序次序输入二叉树中结点的值〔一个字符〕，空格字符表示空数，

//构造二叉链表表示的二叉树T

TElemTypech;

scanf(%c,ch);

if(ch==)T=NULL;

else{

if(!(T=(BiThrNode*)malloc(sizeof(BiThrNode))))exit(OVERFLOW);

T-data=ch;//生成根节点

T-LTag=Link;

T-RTag=Link;

CreateBiThrTree(T-lchild);//构造左子树

CreateBiThr