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

《数据结构课程设计-线索二叉树算法的实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。这种加上了线索的二叉树称为线索二叉树(Threaded  BinaryTree)。对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。运用VC++编写一个程序实现前序

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

4、叉树、遍历二叉树、线索化二叉树。其中，遍历和线索化都包含了先、中、后三种序列，而且对三种序列线索化后的二叉树也进行了遍历。该程序采用VC6.0作为软件开发环境，采用C语言的各种语句和结构实现二叉树的一系列操作，并采用友好的界面向用户提供所操作的过程和数据状态，操作简单，界面清晰，易于被用户所接受。关键字：线索化；遍历；二叉树；先序；中序；后序目录1课题描述12任务分析23逻辑设计及描述33.1二叉树的存储33.2二叉树的遍历43.3二叉树的线索化43.4线索化二叉树的遍历73.5主函数104程序编码12总结21参考文献221课题描述本程序重在设计二叉树的各种线索化实现，以C

5、语言作为编程语言，实现对二叉树的先、中、后三种序列的线索化。旨在使用户在使用过程中能直接调用各种所需函数，以及了解二叉树的各种线索化过程。其中各函数分别为：BiThrTreeCreateBiTree()；//创建二叉树;BiThrTreeCopyBiTree(BiThrTree&rt)//复制一棵二叉树;voidPreOrderTraverse(BiThrTreeT)//先序遍历二叉树;voidInOrderTraverse(BiThrTreeT)//中序遍历二叉树;voidPostOrderTraverse(BiThrTreeT)//后序遍历二叉树;boolPreOrde

6、rThreading(BiThrTree&Thrt,BiThrTreeT)//先序线索化二叉树;voidPreThreading(BiThrTreep)//先序搜索结点的建立;boolInOrderThreading(BiThrTree&Thrt,BiThrTreeT)//中序线索化二叉树;voidInThreading(BiThrTreep)//中序搜索结点的建立;voidbackThreading(BiThrTreep)//后序搜索结点的建立;BiThrTreebackorderThreading(BiThrTree&rt)//后序线索化二叉树;BiThrTreepar

7、ent(BiThrTree&thrt,BiThrTree&p)//查找结点voidPreOrderTraverse_Thr(BiThrTreeThrt)//遍历先序线索化二叉树;voidInOrderTraverse_Thr(BiThrTreeThrt)//遍历中序线索化二叉树;voidbackorderTraver(BiThrTreeThrt)//遍历后序线索化二叉树;voidInOrder_Thr_T(BiThrTreeThrt,BiThrTree&T)//将线索化后的二叉树还原;开发工具：C语言运行环境：Vi