中序线索化二叉树实验报告数据结构.docx

长 沙 理 工 大 学数学与计算科学学院实 验 报 告实验项目名称 二叉树的中序线索化 所属课程名称 数据结构 实 验 类 型 验证型、设计型 实 验 日 期 2014年11月26日 班 级 学 号 姓 名 成 绩 一、实验概述：【实验目的】熟悉二叉树存储结构，掌握线索二叉链表的特点及基本运算【实验原理】1、二叉树的特点：（1）是一种树形结构；（2）每个节点至多有两颗子树；（3）且子树有左右之分，其次序不能颠倒。2、二叉树的顺序存储表示：#define MAX_TREE_SIZE 100 //二叉树的最大节点数Typedf TelemType SqBiTree[MAX_TREE_SIZE]; //0号单元存储根节点SqBiTree bt;- - -二叉树的二叉链表存储表示- - - typedef?struct?BiTNode{TElemType????data;struct?BiTNode?*lchild,*rchild; //左右孩子指针}BiTNode,*BiTree;【实验环境】VC++ 6.0二、实验内容：【实验方案】在Vc++环境下:构造二叉树T;编写二叉树T的中序线索化及中序遍历算法;设计主函数;调用以上算法，验证算法的正确性，调试运行，得出结果。【实验过程】（实验步骤、记录、数据、分析）1．输入头文件与宏定义，二叉树的存储结构，二叉树的中序线索化算法及中序遍历算法，设计主函数，定义数据类型，写入VC++6.0；2.对程序进行第一次调试，出现以下错误：3.检查源程序，分析错误原因输入错误，将上述算法中的“p!”误输为“p1”针对错误，对源程序进行修改；4.对源程序进行第二次调试，仍存在以下错误：5.仔细核查源程序，寻找错误源头；上述算法“BiThreTree *InOrderThrTree(BiThreTree T)”中二叉树“T”前缺少标识符“*”针对错误，再次对源程序进行修改；6.对源程序进行第三次调试运行，未再出现错误；7.输入任意数据如“abc de f g ”，验证算法的正确性；【实验结论】（结果）【实验小结】（收获体会）通过本次实验，我更加熟练地掌握了线索二叉链表的特点及基本运算。在实验中遇到了一些问题，但通过同学的指导最终解决了。完成这次作业后使我又进一步提高了程序编写的能力和增加了我对数据结构的兴趣。三、指导教师评语及成绩：评 语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确. 成 绩： 指导教师签名： 批阅日期：附录1：源 程 序#include stdio.h#includestdlib.h#include malloc.htypedef enum{Link,Thread} PointerTag; //指针标志typedef char DataType;typedef struct BiThreTree{ //定义结点元素 PointerTag LTag,RTag; DataType data; struct BiThreTree *lchild,*rchild; }BiThreTree;BiThreTree *pre; //全局变量，用于二叉树的线索化BiThreTree *CreateTree() //按前序输入建立二叉树{ BiThreTree *T; DataType e; scanf(%c,e); if(e== ) T=NULL; else {T=(BiThreTree *)malloc(sizeof(BiThreTree)); T-data=e; T-LTag=Link; //初始化时指针标志均为Link T-RTag=Link; T-lchild=CreateTree(); T-rchild=CreateTree(); } return T;}void InThread(BiThreTree *T){ BiThreTree *p; p=T; if(p) { InThread(p-lchild); if(!p-lchild) { p-LTag=Thread; p-lchild=pre; } if(!pre-rchild) { pre-RTag=Thread; pre-rchild=p; } pre=p; InThread(p-rchild); }}BiThreTree *InOrderThrTree(BiThreTree *