信息科学与技术学院 《数据结构》课程设计报告 题目名称： 线索二叉树的计算 学生姓名： * * * 学 号: ********** 专业班级： 计算机科学与技术 指导教师： * * 2014 年 1 月 8 - 1 - 1、设计的目的与要求 此程序需要完成如下要求：建立线索二叉树，并实现线索二叉树的插入、删除和恢复线索的实现。 实现本程序需要解决以下几个问题： 1 、 如何建立线索二叉树。 2 、 如何实现线索二叉树的插入。 3 、 如何实现线索二叉树的删除。 4 、 如何实现线索二叉树恢复线索的实现。 此题目是线索二叉树的一系列操作问题。首先就要明白线索二叉树是什么，利用二叉链表的空指 针域将空的左孩子指针域改为指向其前驱，空的右孩子指针域改为指向其后继，这种改变指向的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。 在这个问题中，要解决的任务是：实现线索二叉树的建立、插入、删除、恢复线索的实现。N 个 结 点的二叉链表中含有 n+1 个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下 的前趋和后继结点的指针（这种附加的指针称为"线索"）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。在此次课程设计中，采用的是中序线索二叉树。 - 2 - 目 录 摘要…………………………………………………………………………………………4 一、引言……………………………………………………………………………………5 二、设计任务与目的 …………………………………………………………………… 5 三、设计方案与实施………………………………………………………………………5 1、总体设计………………………………………………………………………… 5 2、详细设计………………………………………………………………………… 7 3、程序清单………………………………………………………………………… 13 4、程序调试与体会……………………………………………………………………24 5、运行结果（截图）………………………………………………………………… 24 四、结论……………………………………………………………………………………27 五、致谢…………………………………………………………...
