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

《中序线索化二叉树实验报告数据结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学与计算科学学院实验报告实验项目名称二叉树的中序线索化所属课程名称数据结构实验类型验证型、设计型实验日期2014年11月26日班级学号姓名成绩6一、实验概述：【实验目的】熟悉二叉树存储结构，掌握线索二叉链表的特点及基本运算【实验原理】1、二叉树的特点：（1）是一种树形结构；（2）每个节点至多有两颗子树；（3）且子树有左右之分，其次序不能颠倒。2、二叉树的顺序存储表示：#defineMAX_TREE_SIZE100//二叉树的最大节点数TypedfTelemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根节点SqBiTreebt;---二叉树的二叉链表存储表

2、示---typedef struct BiTNode{TElemType    data;struct BiTNode *lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;【实验环境】VC++6.0二、实验内容：【实验方案】在Vc++环境下:(1)构造二叉树T;(2)编写二叉树T的中序线索化及中序遍历算法;(3)设计主函数;(4)调用以上算法，验证算法的正确性，调试运行，得出结果。【实验过程】（实验步骤、记录、数据、分析）1．输入头文件与宏定义，二叉树的存储结构，二叉树的中序线索化算法及中序遍历算法，设计主函数，定义数据类型，写入VC++6.0；2.对程

3、序进行第一次调试，出现以下错误：63.检查源程序，分析错误原因输入错误，将上述算法中的“p!”误输为“p1”针对错误，对源程序进行修改；4.对源程序进行第二次调试，仍存在以下错误：5.仔细核查源程序，寻找错误源头；6上述算法“BiThreTree*InOrderThrTree(BiThreTreeT)”中二叉树“T”前缺少标识符“*”针对错误，再次对源程序进行修改；6.对源程序进行第三次调试运行，未再出现错误；7.输入任意数据如“abcdefg”，验证算法的正确性；【实验结论】（结果）【实验小结】（收获体会）通过本次实验，我更加熟练地掌握了线索二叉链表的特点及基本运算。在实验中遇到了

4、一些问题，但通过同学的指导最终解决了。完成这次作业后使我又进一步提高了程序编写的能力和增加了我对数据结构的兴趣。6三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确.成绩：指导教师签名：批阅日期：6附录1：源程序#include#include#includetypedefenum{Link,Thread}PointerTag;//指针标志typedefcharDataType;t

5、ypedefstructBiThreTree{//定义结点元素PointerTagLTag,RTag;DataTypedata;structBiThreTree*lchild,*rchild;}BiThreTree;BiThreTree*pre;//全局变量，用于二叉树的线索化BiThreTree*CreateTree()//按前序输入建立二叉树{BiThreTree*T;DataTypee;scanf("%c",&e);if(e=='')T=NULL;else{T=(BiThreTree*)malloc(sizeof(BiThreTree));T->data=e;T->LTag=L

6、ink;//初始化时指针标志均为LinkT->RTag=Link;T->lchild=CreateTree();T->rchild=CreateTree();}returnT;}voidInThread(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);6}}BiThreTree*In

7、OrderThrTree(BiThreTree*T)//中序线索化二叉树{BiThreTree*Thre;//Thre为头结点的指针Thre=(BiThreTree*)malloc(sizeof(BiThreTree));Thre->lchild=T;Thre->rchild=Thre;pre=Thre;InThread(T);pre->RTag=Thread;pre->rchild=Thre;Thre->rchild=pre;returnThre;}vo