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

数学与计算科学学院实 验 报 告实验项目名称 中序遍历线索化二叉树算法的设计与实现 所属课程名称 数据结构A 实 验 类 型 设计型 实 验 日 期 2014.11.26 班 级 信计1302班 学 号 201353100216 姓 名 危志鹏 成 绩 一、实验概述：【实验目的】1.掌握二叉链表及线索二叉链表的特点及基本运算。【实验原理】/-二叉树的二叉线索存储表示-Typedef enum PointerTagLink,Thread;Typedef struct BiThrNode TElemType data; Struct BiThrNode *lchild, *rchild; PointerTag LTag,RTag;BiThrNode, *BiThrTree;【实验环境】VC+ 6.0二、实验内容：【实验方案】在VC+环境下，编写二叉树的线索链表存储结构，中序遍历二叉线索树T的非递归算法，以及将二叉树T的中序线索化算法，对每个数据元素均调用函数Visit。最后设计主函数，调用以上算法，验证算法的正确性，调试运行，得出结果。【实验过程】（实验步骤、记录、数据、分析）1. 运行VC+ 6.0，建立新的命令文件；2. 将程序输入，如下，发现一个错误。3. 经过查找，发现一个错误，然后改正如下4. 然后进行调试，发现调试出错。【实验结论】（结果）【实验小结】（收获体会）这次实验又出现了和上次一样的错误：程序无错误，但结果不能运行。经过多次的检查终于解决了问题，相信这样的错误不会再有第三次了。三、指导教师评语及成绩：评 语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确. 成 绩： 指导教师签名： 批阅日期：附录1：源 程 序#include#include#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef char TElemType;typedef enum PointerTagLink,Thread; /Link=0:指针，Thread=1:线索typedef struct BiThrNodeTElemType data;struct BiThrNode *lchild,*rchild; /左右孩子指针PointerTag LTag,RTag; /左右标志BiThrNode,*BiThrTree;Status Visit(TElemType e) printf(%c ,e); /输出元素e的值 return OK;Status CreateBiThrTree(BiThrTree &T)/按先序次序输入二叉树中结点的值（一个字符），空格字符表示空数，/构造二叉链表表示的二叉树TTElemType ch;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); /构造左子树 CreateBiThrTree(T-rchild); /构造右子树 return OK;/CreateBiThrTreeBiThrTree pre; /pre是全局变量void InThreading(BiThrTree p)if(p)InThreading(p-lchild); /左子树线索化if(!p-lchild)p-LTag=Thread;p-lchild=pre; /前驱线索if(!pre-rchild)pre-RTag=Thread;pre-rchild=p; /后继线索pre=p; /保持pre指向p的前驱InThreading(p-rchild); /右子树线索化/if(p)/InThreading(BiThrTree p)Status InOderThreading(BiThrTree &Thrt,BiThrTree T)/中序遍历二叉树T，并将其中序线索化，Thrt指向头结点BiThrTree pre;if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) ) exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread; /建头结点Thrt-rchild=Thrt; /右指针回增if(!T) Thrt-lchild=Thrt; /若二叉树空，则左指针回增elseThrt-lchild=T;pre=Thrt;InThreading(T); /中序遍历进行中序线索化pre-rchild=Thrt;pre-RTag=Thread; /最后一个结点线索化、Thrt-rchild=pre;return OK;/InOrderThreadingStatus InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e)/T指向头结点，头结点的左链lchild指向根结点，可参见线索化算法/中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数Visit。BiThrTree p;p=T-lchild; /p指向根结点while(p!=T) /空数或遍历结束时，p=Twhile(p-LTag=Link) p=p-lchild;if(!Visit(p-data) return ERROR; /访问其左子树为空的结点while(p-RTag=Thread & p-rchild!=T)p=p-rchild;Visit(p-data); /访问后继结点p=p-rchild;return OK;/InOrderTraverse_Thrvoid main()BiThrTre