线索二叉树的应用2003.doc

课程设计说明书 （数据结构课程设计） 专 业: 网络工程 课程名称: 数据结构课程设计 班级: 网络B11-1 设计题目: 线索二叉树的应用 设计时间: 2013-2-25 至 2013-3-8 评 语:_________________________________ _________________________________________ _________________________________________ _________________________________________ _________________________________________ 评阅成绩:＿＿ ＿＿评阅教师:＿＿ 一、问题描述与需求分析 1、问题描述 本实验的问题是建立一个线索二叉树，并实现线索二叉树的插入、删除、恢复线索等功能。 2、功能需求分析 本程序要实现的功能是： 1. 线索二叉树的建立。 2.线索二叉树的插入。 3.线索二叉树的删除。 4.线索二叉树的恢复。 想要完成上面的功能，我们首先是要知道上面是线索二叉树。我们可以从数据结构的书上找到答案，利用二叉链表的空指针域将空的左孩子指针域改为指向其前驱，空的右孩子指针域改为指向其后继。这种改变指向的指针称为线索，加上了线索的二叉链表称为线索链表。 N个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点的在某种遍历次序下的前驱和后继结点的指针，这种加上了线索的二叉链表称为线索链表。相应的二叉树称为线线索二叉树。根据线索二叉树性质的不同，线索二叉树可以分为前序线索二叉树，中序线索二叉树和后续线索二叉树三种，此次课程设计中使用的是中序线索二叉树。 二、概要设计 1、总体设计思路 首先就是要建立一个二叉树，然后再对二叉树进行线索化。 线索链表中的结点结构为： 其中： 线索二叉树及其存储结构如 在线索树上进行遍历，只需先找到序列中的第一个结点，然后依次找结点后继为空时而止。 以上图为例子说明在线索树中查找结点的后继。树中所有叶子的结点是线索，则右链域直接指示结点的后继，如结点b的后继为结点*。树中所有非终端结点的右链均为指针，则无法由此得到后继的信息。然而根据中序遍历的规律可知，结点的后继应是遍历其右子树时访问的第一个结点，即右子树最左下的结点。列入在找结点*的后继时，首先沿右指针找到其右子树的根结点“—”，然后顺其左指针往下直至其左标志为1的结点，即为结点* 的后继，在图中是结点c。反之，在中序结点中找结点前驱的规律是：若其左标志为“1”，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树最右下的结点）为其前驱。 开始 开始 定义二叉树 定义二叉树 建立二叉树 建立二叉树 选择菜单 选择菜单 输入i(1--5) 输入i(1--5) N N N N I=3 I=2 I=1 I=5 I=4 I=3 I=2 I=1 I=5 I=4 输出线索二叉树二叉树的线索化中序输出二叉树Y Y Y Y Y 输出线索二叉树 二叉树的线索化 中序输出二叉树 删除结点并线索haunted插入结点并线索化 删除结点并线索haunted 插入结点并线索化 结束 结束 程序流程图 2、 模块简介 本程序有五个模块功能。每个模块功能均实现特定的功能。 二叉树的建立： 中序输入二叉树，为程序提供数据，输入的时候空域用@表示。 进行二叉树的线索化： 按中序遍历顺序将二叉树线索化，只需要在遍历的过程中将二叉树的每个结点的空的左右孩子的指针域分别修改为指向其前驱和后继，若其左子树为空，则将其左孩子域线索化，使其左孩子指针lchild指向其后继，并且ltag置1. 3插入操作：