数据结构课程设计-线索二叉树算法的实现

《数据结构课程设计-线索二叉树算法的实现》由会员分享，可在线阅读，更多相关《数据结构课程设计-线索二叉树算法的实现（28页珍藏版）》请在金锄头文库上搜索。

1、数据结构课程设计设 计 说 明 书线索二叉树算法的实现学 生 姓 名学 号班 级成 绩指 导 教 师计算机科学与技术系2011 年 9 月 9 日数据结构课程设计评阅书题 目 线索二叉树算法的实现学生姓名 学号指导教师评语及成绩成绩： 教师签名： 年 月 日答辩教师评语及成绩成绩： 教师签名： 年 月 日教研室意见总成绩： 室主任签名： 年 月 日注: 指导老师成绩 60%，答辩成绩 40%，总成绩合成后按五级制计入。课程设计任务书20112012 学年第 1 学期专业： 计算机科学与技术 学号： 姓名： 穆闻 课程设计名称： 数据结构课程设计 设 计 题 目： 线索二叉树的实现 完 成 期

2、限：自 2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周设计内容：n 个结点的二叉链表中含有 n+1 个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为线索）。这种加上了线索的二叉树称为线索二叉树(Threaded BinaryTree)。对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。根据线索性质的不同，线索二

3、叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。运用 VC+编写一个程序实现前序线索二叉树、中序线索二叉树和后序线索二叉树，其中遍历要求用先左后右的递归或非递归算法来实现。要求:1） 阐述设计思想，画出流程图；2） 任意建立一棵二叉树，采用前序、中序、后序三种方法线索化二叉树；3） 说明测试方法，写出完整的运行结果；4） 从时间、空间对算法分析；5） 较好的界面设计；6） 编写课程设计报告。以上要求中第一个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。指导教师（签字）：

4、 教研室主任（签字）： 批准日期： 年 月 日摘 要这是一个关于线索二叉树的程序，该程序具有创建二叉树、遍历二叉树、线索化二叉树。其中，遍历和线索化都包含了先、中、后三种序列，而且对三种序列线索化后的二叉树也进行了遍历。该程序采用 VC 6.0 作为软件开发环境，采用 C 语言的各种语句和结构实现二叉树的一系列操作，并采用友好的界面向用户提供所操作的过程和数据状态，操作简单，界面清晰，易于被用户所接受。关键字：线索化；遍历；二叉树；先序；中序；后序目 录1 课题描述 .12 任务分析 .23 逻辑设计及描述 .33.1 二叉树的存储 .33.2 二叉树的遍历 .43.3 二叉树的线索化 .43

5、.4 线索化二叉树的遍历 .73.5 主函数 .104 程序编码 .12总结 .21参考文献 .221 1 课题描述本程序重在设计二叉树的各种线索化实现，以 C 语言作为编程语言，实现对二叉树的先、中、后三种序列的线索化。旨在使用户在使用过程中能直接调用各种所需函数，以及了解二叉树的各种线索化过程。其中各函数分别为：BiThrTree CreateBiTree()；/ 创建二叉树;BiThrTree CopyBiTree(BiThrTree void PreOrderTraverse(BiThrTree T)/先序遍历二叉树;void InOrderTraverse(BiThrTree T)

6、/中序遍历二叉树;void PostOrderTraverse(BiThrTree T)/后序遍历二叉树;bool PreOrderThreading(BiThrTree void PreThreading(BiThrTree p)/先序搜索结点的建立;bool InOrderThreading(BiThrTree void InThreading(BiThrTree p)/中序搜索结点的建立;void backThreading(BiThrTree p)/后序搜索结点的建立;BiThrTree backorderThreading(BiThrTree BiThrTree parent(BiT

7、hrTree &thrt,BiThrTree &p)/查找结点void PreOrderTraverse_Thr(BiThrTree Thrt)/遍历先序线索化二叉树;void InOrderTraverse_Thr(BiThrTree Thrt)/遍历中序线索化二叉树;void backorderTraver(BiThrTree Thrt)/遍历后序线索化二叉树;void InOrder_Thr_T(BiThrTree Thrt,BiThrTree 开发工具：C 语言运行环境：Visual c+6.0。2 2 任务分析这是一个能对二叉树线索化的程序，其中包括对二叉树的先序、中序、后序线索化，

8、最后遍历线索化并输出遍历结果。其中线索化要实现对同一个树的线索化，即应具备还原线索化后二叉树的程序，并重新对二叉树线索化。主要的功能模块流程图如图 2.1 所示。创建一棵二叉树递归先序遍历 递归中序遍历 递归后序遍历先序线索化中序线索化后序线索化遍历先序线索化 遍历中序线索化 遍历后序线索化图 2.1 模块流程图3 3 逻辑设计及描述3.1 二叉树的存储1.创建二叉树（ CreateBiTree(T)）设计思想：在用户需要创建二叉树时，屏幕提醒输入树的各个结点，包括空结点的输入，完成输入后，程序自动依次读入各个结点，以空结点作为判断结点位置的主要依据，对每个结点申请一定的存放空间，然后依次存放

9、各结点。设计流程如图 3.1 所示。b e g i nYc h = = # N Y! ( T = ( B i T h r T r e e ) m a l l o c ( s i z eo f ( B i T h r N o d e ) ) )T = N U L LR e t u r n 0 ;R e t u r n Tc h a r c h ;T - d a t a = c h ;N 结束b e g i nB i T h r T r e e t r e e ;Yr t = = N U L Lr e t u r n t r e e ;! ( t r e e = ( B i T h r T r e

10、 e ) m a l l o c ( s iz e o f ( B i T h r N o d e ) ) )Yt r e e - d a t a = r t - d a t a ;R e t u r n 0 ;T r e e = N U L LN结束N图 3.1 CreateBiTree(T ) 创建二叉树 图 3.2 CopyBiTree(rt)复制一棵二叉树2.复制二叉树（CopyBiTree(rt)）设计思想：该函数的功能主要是为了避免前后两次的线索化混乱，其实质是重建二叉树以方便下一次的线索化。复制的方法无外乎将各个结点拷贝至另一棵树，因为是完全一样的二叉树,所以连左右标志域也要一起

11、复制,结点位置不能发生任何变化。设计流程如图 3.2所示，算法如算法 3.1 所示。BiThrTree CopyBiTree(BiThrTree &rt)BiThrTree tree;if(rt=NULL) tree=NULL;elseif(!(tree=(BiThrTree)malloc(sizeof(BiThrNode) return 0;tree-data=rt-data;/复制结点4 tree-LTag=rt-LTag;tree-RTag=rt-RTag;/复制左右标志域tree-lchild=CopyBiTree(rt-lchild);tree-rchild=CopyBiTree(r

12、t-rchild);/复制左右孩子 return tree;算法 3.13.2 二叉树的遍历1. 先、中、后遍历二叉树，因为三种遍历方法的区别只是将输出结点的位置调换一下就可以实现，所以在此只列举先序遍历方法的设计思想，该函数是用递归的方法依次遍历根结点、左子、右子，中序遍历则是左子、根结点、右子，后序遍历只需将根结点的访问放在最后面执行即可。设计流程如图3.3，主要算法如算法 3.2 所示。void PreOrderTraverse(BiThrTree T)/前序遍历if (T!=NULL)printf(%c ,T-data); /*访问根结点*/PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); 算法 3.2b e g i nYT ! = N U L L Np r i n t f ( % c , T - d a t a ) ;P r e O r d e r T r a v e r s e ( T - l c h i l d )P r e O r d e r T r a v e r s e ( T -