资源描述：
《数据结构课程设计报告之线索二叉树的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、青岛理工大学数据结构课程设计报告题冃：线索二叉树的应用院係）：计算机工程学院学生姓名:周健健班级：软件131学号：201307194起迄日期：7/13-7/24指导教师：房斐斐翟正利、需求分析1•问题描述：此次的数据结构题口是线索二叉树的应用，树是一•种非常重要的数据结构类型，线索二叉树要比二叉树复杂，相对的对线索二叉树操作要比二叉树方便许多。我做的这个线索二叉树的应用包含了二叉树的建立，线索化，中序遍历输出，插入，删除以及每一步操作Z后的横向输出。为实现这些功能,首先建立一个二叉树，然后进行线索化，在进行插入之前，一是必须要明确你要在什么地方插入结点
2、，二是要找到该结点，三是对新插入的结点进行前驱后继的连接，线索化的恢复；删除操作，先要找到你要删除的结点，还要找到要删除结点的父亲结点，删除操作中分了很多种情况，必须对每一种情况进行分析，在横向输出时得注意结点Z间的间距。2.基本功能1、建立二叉树2、线索化已建立好的二叉树3、屮序遍历输岀4、删除结点5、插入结点概要设计1•设计思路：(1)、建立一个二叉树，采用层次遍历利用指针类型的队列做辅助，所以建立的二叉树是完全二叉树的类型，对于空结点用@代替，#表示输入结束。(2)、进行二叉树的线索化，屮序线索方法，与屮序遍历相对应，线索：增加两个标志域，表示有
3、无孩子，以及后继前驱指向的位査。(3)、中序遍历输出二叉树，按课设要求釆用中序遍历，并且釆用的是递归算法。(4)、查找要进行操作的结点及其父亲结点，未接下來的插入删除操作捉供方便，所以必须找到原树中的结点，才能对具进行操作。(5)、插入操作，首先找到该节点，分以下两种情况：当插入节点有左孩了时，插入位置是其左孩子的右链尾；当插入节点无左孩子时，插入的结点是该结点的左孩了。(6)、删除操作,删除操作要考虑12种情况,下面列出:厂L无左右孩子：将树置空2.有左孩子，无右孩子：将删除结点的左孩子做头结点删除的结点是头结点＜3.冇右孩了，无左孩了：将删除结点的
4、右孩了做头结点4.左右孩子都有：删除节点的左孩子是头结点，找到其右链I尾，右链尾的右孩子是删除节点的右孩子1•无左右孩了：将其父亲结点左孩了置空，删除即可删除的结点是父亲结点的左孩子Y2.有左孩子，无右孩子：将删除结点的左孩子做父亲节点的左孩子3.有右孩子，无左孩子：将删除结点的右孩子做父亲结点的左孩子4.左右孩子都有：删除节点的左孩子做父亲结点的左孩子，找到其左孩子的右链尾，右链尾的右孩子是删除结点的右孩子。厂1•无左右孩子：将其父亲结点右孩子置空，删除即可删除的结点是父亲结点的右孩子Y2.有左孩子，无右孩子：将删除结点的左孩子做父亲节点的右孩子3.
5、有右孩子，无左孩子：将删除结点的右孩子做父亲结点的右孩子4.左右孩了都有：删除节点的右孩了做父亲结点的右孩了，找到其L右孩子的左链尾，左链尾的左孩子是删除结点的左孩子。2.数据结构设计抽象数据类型二叉树的定义如下：ADTBithrtree{数据对象：D是具冇相同特性的数据元索的集介。这次课设中都是字符型的。数据关系R：若D二①，则R二①，称Bithrtree为空二叉树。如果DH①，则R={H},H存在如下二元关系:(1)在D屮存在唯一称为根的数据元素T,它在H中无前驱；(2)若D-{root}!二①，则存在D-{root}={DI,Dr},且DIADr
6、=O；(3)若D1H①，则D1屮存在唯一的元素xl,GH,且存在D1上的关系H1UH;若DrH①，则Dr中存在唯一的元素Xr,G11,且存在Dr上的关系HrUH；H={,,Hl,Hr}；(4)(D1,{Hl})是一颗符合本定义的二叉树，称为根的左子树，(Dr,{Hr})是-•颗符合本定义的二叉树，称为根的右子树。基本操作：CreateBiTree(*T,definition);初始条件：defintion给出二义树T的定义。操作结果：按defintion构造二叉树。Search(B
7、ithrtree*p,x)初始条件：二叉树头结点p,查找沅素X。操作结果：找到x,返回。InOrderTraverse(BiThr*T)初始条件：二叉树T已存在。操作结果：中序遍历二叉树，并输出。TnThreading(p)初始条件：二叉树已存在。操作结果：将二叉树线索化。Insert(*p)初始条件：二叉树已存在，p指向二叉树屮某个结点操作结果：在pZ前插入新的结点，并恢复二叉树的线索。Delete(*p)初始条件：二叉树已存在，p指向二叉树屮某个结点操作结果：删除P指向的结点，并恢复线索化。}ADTBinaryTree2.软件结构设计软件结构设计如
8、图2.1所示:图2.1软件结构设计三、详细设计1、伪代码算法(1)主函数：BiThr*T;in
