线索二叉树的实现.doc

数据结构课程设计 设计说明书 线索二叉树的实现 学生姓名 学号 班级 成绩 指导教师 曹记东 计算机科学与技术系 2010年9月10日 数据结构课程设计评阅书 题目 线索二叉树的实现 学生姓名 学号 指导教师评语及成绩 指导教师签名： 年 月 日 答辩评语及成绩 答辩教师签名： 年 月 日 教研室意见 总成绩： 室主任签名： 年 月 日  课程设计任务书 2010—2011学年第1学期 专业： 计算机科学与技术 学号： 姓名： 课程设计名称： 数据结构课程设计 设 计 题 目： 线索二叉树的实现 完 成 期 限：自 2010 年 8 月 30 日至 2010 年 9 月 10 日共 2 周 设计内容： n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为线索）。这种加上了线索的二叉树称为线索二叉树(Threaded??BinaryTree)。对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。 运用VC++编写一个程序实现前序线索二叉树、中序线索二叉树和后序线索二叉树，其中遍历要求用先左后右的递归或非递归算法来实现。 要求: 阐述设计思想，画出流程图； 任意建立一棵二叉树，采用前序、中序、后序三种方法线索化二叉树； 说明测试方法，写出完整的运行结果； 从时间、空间对算法分析； 较好的界面设计； 编写课程设计报告。 以上要求中第一个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。 指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日 摘 要 单，界面清晰，易于用户接受。 关键词： 目 录 1 课题描述 1 2 设计过程 2 2.1任务分析及课题分析 2 2.2 流程图 2 2.4算法分析 11 2.5 测试结果 12 3 总 结 14 参考文献 15 1 课题描述 本次课程设计的题目是线索二叉树的实现，该二叉树是以线索链表的存储方式来存储的，该结点有五个域：数据域、左孩子、右孩子、前驱、后继，其中指向其前驱和后继的指针叫做线索，这三种遍历（先序遍历、中序遍历、后序遍历）是根据线索来遍历二叉树的，对二叉树以某种次序的遍历使其成为线索二叉树的过程叫做线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。2 设计过程 2.1任务分析及课题分析 此任务设计了一个对线索二叉树进行先序遍历、中序遍历、后序遍历这三种遍历，先序遍历是按（先根再左后右），中序遍历（先左再中后右），后序遍历（先左再右后中），这种遍历方法是以线索为根本，该二叉树是以二叉链表为存储结构，在遍历的过程实质是修改空指针的过程，把空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到。 2.2 流程图 图2.2先序遍历线索二叉树流程图  图2.3中序遍历线索二叉树流程图 图2.4 后序遍历线索二叉树流程图 图2.5 后序遍历线索二叉树流程图 2.3 程序实现代码 #includestdio.h #includestdlib.h #includemalloc.h typedef enum PointerTag{link,thread}; //link==0:指针，thread==1：线索// typedef struct BiThrNode { char data; BiThrNode *rchild, *lchild; PointerTag ltag,rt