线索二叉树的实现

《线索二叉树的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计设计说明书线索二叉树的实现学生姓名学号班级成绩指导教师曹记东计算机科学与技术系2010年9月10日数据结构课程设计评阅书题目线索二叉树的实现学生姓名学号指导教师评语及成绩指导教师签名：年月日答辩评语及成绩答辩教师签名：年月日教研室意见总成绩：室主任签名：年月日课程设计任务书2010—2011学年第1学期专业：计算机科学与技术学号：姓名：课程设计名称：数据结构课程设计设计题目：线索二叉树的实现完成期限：自2010年8月30日至2010年9月10日共2周设计内容：n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在

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

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

4、进行先序遍历、中序遍历、后序遍历。这种遍历方法是以线索为根本，利用该软件，用户可以方便的查找树中任意结点的前驱和后继，给用户带来了方便。该软件采用了VC6.0作为软件开发环境，实现对线索二叉树的遍历。操作简单，界面清晰，易于用户接受。关键词：线索；先序遍历；中序遍历；后序遍历目录1课题描述12设计过程22.1任务分析及课题分析22.2流程图22.4算法分析112.5测试结果123总结14参考文献151课题描述本次课程设计的题目是线索二叉树的实现，该二叉树是以线索链表的存储方式来存储的，该结点有五个域：数据域、左孩子、右孩子、前驱、后继，其中指向其前驱和后继

5、的指针叫做线索，这三种遍历（先序遍历、中序遍历、后序遍历）是根据线索来遍历二叉树的，对二叉树以某种次序的遍历使其成为线索二叉树的过程叫做线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。-15--15-2设计过程2.1任务分析及课题分析此任务设计了一个对线索二叉树进行先序遍历、中序遍历、后序遍历这三种遍历，先序遍历是按（先根再左后右），中序遍历（先左再中后右），后序遍历（先左再右后中），这种遍历方法是以线索为根本，该二叉树是以二

6、叉链表为存储结构，在遍历的过程实质是修改空指针的过程，把空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到。2.2流程图图2.1线索二叉树的实现总流程图-15-图2.2先序遍历线索二叉树流程图-15-图2.3中序遍历线索二叉树流程图-15-图2.4后序遍历线索二叉树流程图-15-图2.5后序遍历线索二叉树流程图-15-2.3程序实现代码#include#include#includetypedefenumPointerTag{link,thread};//lin

7、k==0:指针，thread==1：线索//typedefstructBiThrNode{chardata;BiThrNode*rchild,*lchild;PointerTagltag,rtag;}BiThrNode,*BiThrTree;BiThrTreeCreateTree()//先序创建二叉树//{BiThrTreeT;charch;T=(BiThrNode*)malloc(sizeof(BiThrNode));ch=getchar();if(ch=='#')T=NULL;else{T=(BiThrTree)malloc(sizeof(BiThrN

8、ode));if(T){T->data=ch;T->ltag=li