1、 数学与计算机学院 课程设计说明书 课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 题 目: 线索二叉树的基本操作 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 2013 年 12 月 18 日 完 成 时 间: 2013 年 12 月 28 日 课程设计成绩： 学习 态度及平 时成绩 （20） 技术 水平与实 际能力 （20） 完 成情 况 (20) 创新 （5） 说明书 （计算书、 图 纸、分析报告）撰写质量 （35） 总 分 （100） 指导教师签名： 年 月 日 目 录 1 需求分析 1 1.1 任务与分析 1 1.2 测试数据 2 2 概要设计 3 2.
2、1 模块划分. 3 2.2 模块中的层次图 3 3 详细设计 4 3.1 结构体设计 4 3.2 创建二叉树 4 3.3 二叉树线索化 5 3.4 二叉树中插入结点 6 3.5 删除结点函数 8 3.6 查找前驱后继函数 11 4 调试分析 12 5 用户使用说明 12 6 测试结果 12 6.1 新建二叉树 12 6.2 中序遍历 13 6.3 查找前驱 13 6.4 查找后继 14 6.5 删除结点 14 6.6 插入左孩子 15 6.7 插入右孩子 15 6.8 退出 16 结 论 17 致 谢 18 参考文献 19 摘摘 要要 首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分
3、 析，并给出测试数据。其次是概要设计，说明模块的划分以及模块间的层 次关系，然后是详细设计，描述实现概要设计中定义的基本功操作和所有 数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明， 以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后 是测试的数据和结果的分析，最后是对本次课程设计的结论。 关键词：关键词：线索化,中序遍历,插入，删除，查找 1 引 言 数据结构是计算机专业重要的专业基础课程与核心课程之一， 在计算机领域 应用广泛，计算机离不开数据结构。数据结构课程设计为了能使我们掌握所学习 的知识并有应用到实际的设计中的能力， 对于掌握这门课程的学习方法有极大的
4、 意义。本课程设计的题目为“线索二叉树的基本操作” ，完成将二叉树转化成线 索二叉树， 采用中序线索二叉树的操作。 本课程设计采用的编程环境为Microsoft Visual Studio 2008。 1 需求分析 当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右 儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一 般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。 如果在每 个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。 我们可以证明：在 n个结点的二叉链表中含有 n+1 个空指针。因为含 n个结 点的二叉链表中含有 2n个指
5、针，除了根结点，每个结点都有一个从父结点指向 该结点的指针，因此一共使用了 n-1 个指针，所以在 n个结点的二叉链表中含有 n+1 个空指针。 因此可以利用这些空指针， 存放指向结点在某种遍历次序下的前驱和后继结 点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相 应的二叉树称为线索二叉树(Threaded Binary Tree)。根据线索性质的不同，线索 二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。 1.1 任务与分析 任务： 建立一棵二叉树（用户自行输入二叉树，用“#”表示空格，按回车键结束） ， 将其线索化，并实现以下功能： 1)遍历二叉树（本
6、程序使用中序遍历方法） 2)在二叉树中插入一个结点 2 3)删除二叉树的某个结点 4)查找某个结点的前驱 5)查找某个结点的后继 分析： 该任务是关于线索二叉树的运算，其中的基本运算应基于二叉树，但又有所 不同，首先应了解的问题有： 1)线索二叉树是如何建立的，是通过二叉树来实现线索化，还是直接进行线 索化的输入。若由二叉树建立而来，该二叉树应如何输入，对于具体的二叉树应 该使初使用者明白使用的格式。 2)该程序重点内容是有关于二叉树的插入、删除和查找前驱后继，在进行具 体的操作时，规则是什么，依照什么原则。 3)对于插入、删除、查找前驱后继等，其结果是否符合预订的目标，须由自 己判定。 1.2 测试数据 测试数据：ABD#G#CE#F# 图1-1 测试数据 3 2 概要设计 2.1 模块划分 二叉树的建立函数：Creat(ThrNode *bt) 中序遍历函数：void InOrder() 中序线索化函数：
