1、目目 录录 1、数据结构课程设计任务书、数据结构课程设计任务书 . 1 1.1、题目、题目 . 1 1.2、要求、要求 . 1 2、总体设计、总体设计 . 1 2.1、功能模块设计、功能模块设计 . 1 2.2、所有功能模块的流程图、所有功能模块的流程图 . 2 3、详细设计、详细设计 . 2 3.1、程序中所采用的数据结构及存储结构的说明、程序中所采用的数据结构及存储结构的说明. 3 3.2、算法的设计思想、算法的设计思想 . 5 4、调试与测试：、调试与测试： . 5 4.1、调试方法与步骤：、调试方法与步骤： . 5 4.2、测试结果的分析与讨论：、测试结果的分析与讨论： . 6 4.3
2、、测试过程中遇到的主要问题及采取的解决措施：、测试过程中遇到的主要问题及采取的解决措施：. 8 5、时间复杂度的分析：、时间复杂度的分析： . 9 6、源程序清单和执行结果、源程序清单和执行结果 . 9 7、C 程序设计总结程序设计总结 .21 8、致谢、致谢 .21 9、参考文献、参考文献 .21 第第 页页 1、数据结构数据结构课程课程设计任务书设计任务书 1.1、题目题目 线索二叉树 1.2、要求、要求 （1）建立中序线索二叉树，并且遍历； （2）求中序线索二叉树上已知结点中序的前驱和后继； （3）插入结点到指定位置，删除指定结点； （4）求中序线索二叉树上已知结点在先序下的后继和后序下
3、的前驱； 2、总体设计总体设计 2.1、功能模块设计功能模块设计 根据课程设计题目的功能要求，各个功能模块的组成框图如下： 线索二叉树 Create 模块 Delect 模块 Insert 模块 Quiet 模块 在 线 索 树 中 查 找 要 删 除 的 结 点 删 除 查 到 的 结 点 并 中 序 输 出 结 果 用 户 选 择 前 插 后 插 操 作 在 指 定 结 点 前 插 入 输 入 的 结 点 在 指 定 结 点 后 插 入 输 入 的 结 点 退 出 系 统 线 索 树 中 查 询 某 结 点 线 索 树 中 插 入 某 结 点 线 索 树 中 删 除 某 结 点 第第 页页
4、 2.2、所有所有功能模块的功能模块的流程图流程图 3、详细设计详细设计 3.13.1实现线索二叉树的建立、 插入、 删除、 恢复线索的实现.n 个结点的二叉链表中含有 n+1 个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继 结点的指针（这种附加的指针称为“线索“） 。这种加上了线索的二叉链表称为线索链表，相 应的二叉树称为线索二叉树。 3.2 3.2 二叉树的建立、插入、删除、线索化： 开始 定义二叉树 T=CreatTree( ) 1=i 输入 i!=0 输入选择菜单 输入 i i=1 preThred(T) i=2 Insert(T) i=3 DeleteNode(T) i=4 Inorder(T) 退出 第第 页页 3.3、程序中所采用的数据结构及存储结构的说明、程序中所采用的数据结构及存储结构的说明 3.3.1 线索二叉树的结点的结构如下： a b c d e g w f (3)在 b 点处插入结点 w a c
