文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
计算机科学与技术系
课程设计报告
2008 ～2009 学年第 2 学期
课学学专指
业导
班教生
姓
程 名 号 级 师
数据结构 线索二叉树的运算
课程设计名称
屠菁、张贯红
2009 年 5 月
题目：（线索二叉树运算）实现线索二叉树的建立、插入、删除、恢复线索的实现。
一、 问题分析和任务定义
(1).任务定义：
此程序需要完成如下要求：建立线索二叉树，并实现线索二叉树的插入、删除和恢复
线索的实现。
实现本程序需要解决以下几个问题：
1、 如何建立线索二叉树。
2、 如何实现线索二叉树的插入。 3、 如何实现线索二叉树的删除。
4、 如何实现线索二叉树恢复线索的实现。
此题目是线索二叉树的一系列操作问题。首先就要明白线索二叉树是什么，利用二叉链表的空指针域将空的左孩子指针域改为指向其前驱，空的右孩子指针域改为指向其后继，这种改变指向的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
在这个问题中，要解决的任务是：实现线索二叉树的建立、插入、删除、恢复线索的实现。n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为\线索\）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。在此次课程设计中，采用的是中序线索二叉树。 (2).问题分析：
1文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
既然题目要求要分别实现建立、删除、和恢复线索化三种功能，建立和删除一定是相互独立的模块，可分别建立两个函数来实现功能。第三个功能是恢复线索，就要考虑这个线索恢复是怎样的恢复过程，是怎样恢复的。恢复线索是对二叉树当进行了插入和删除操作过程后，因为过程中有结点的变动，而进行的在操作结束以后对整个二叉树的恢复线索，还是在实现插入和删除的过程中就对操作的结点实现局部的恢复线索。从设计的目标来说应该是要在删除和插入的过程中实现对线索的恢复。而在线索二叉树中插入一个结点或删除一个结点，一般情况下，这些操作有可能破坏原来已有的线索，因此，在修改指针时，还需要对线索做相应的修改。因此一般来说，这个过程花费的代价几乎与重新进行线索化相同。
二、概要设计和数据结构选择
首先建立二叉树，然后对二叉树进行线索化。
线索链表的结点结构
线索链表中的结点结构为：
图(1) 线索链表中的结点结构
中序线索二叉树的图示
图(2) 中序线索二叉树
建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。
关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。
操作：（1）令队头指针front指向其孩子结点当前输入的建立链接的父结点，队尾指针rear指向当前输入的结点，初始：front=1,rear=0;
（2）若rear为偶数，则该结点为父结点的左孩子；若rear为奇数，则该结点的右孩子；若父结点和孩子结点为虚结点，则无需链接。
（3）若父结点与其两个孩子结点的链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。
二叉树的中序索化算法与中序历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中前趋结点间线索。该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。
程序流程图:
图(3) 程序流程图
三、详细设计和编码
(1) 建树算法：
1、分析：建立一个二叉链表，需要按照某种顺序依次输入二叉树中的结点，且该输入顺序必须隐含结点间的逻辑结构的信息。这个建立的方法，按完全二叉树的层次顺序，依次输入结点信息建立二叉链表的过程。以@表示空结点，以#表示输入结束的标志 。
2、算法思想：依次输入结点信息，若其不是虚结点，则建立一个新结点。若新结点是第一个结点，则令其为根结点，否则将新结点作为孩子链接到它的父亲结点上。
3、实现：在函数中设置一队列，该队列是一个指针类型的数组，保存已输入的结点的地址。使队头指针front指向当前与孩子建立链接的父亲结点，队尾指针rear指向当前输入的结点。若rear为偶数，则该结点为父结点的左孩子，若rear为奇数，则为父结点的右孩
2文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
子。若父结点或孩子结点为虚结点，则无需链接。若父结点与其两个孩子结点链接完毕，则使front指向下一个等待链接的父结点。
4、主要过程：
Bithptr *Q[maxsize]; //建队为指针类型
Bithptr *CreatTree(){
front=1;rear=0; //置空队 if(ch!='@') //不是虚结点，则建立结点 s=(Bithptr *)malloc(sizeof(Bithptr)); s->data=ch; s->lchild=NULL; s->rchild=NULL; s->rtag=0; s->ltag=0;
if(s!=NULL&&Q[front]!=NULL) //孩子和双亲结点都不是虚结点
if(rear%2==0)
else Q[front]->rchild=s;
if(rear%2==1)front++; //结点*Q[front]的两个孩子处理完，front+1
Q[front]->lchild=s;
(2) 线索化算法：
1、分析：线索过程必须要按照一定的顺序来进行，在本程序中因为树的遍历过程使用的是中序遍历，所以为了方便，线索化的过程也是使用中序线索化。
2、方法：按某种遍历顺序将二叉树线索化，只需要在遍历的过程中将二叉树中每个结点的空的左右孩子指针域分别修改为指向其前驱和后继。若其左子树为空，则将其左孩子域线索化，使其左孩子指针lchild指向其后继，并且ltag置1。
3、实现：要实现线索化，就要知道结点*pre是结点*p的前驱，而*p是*pre的后继。这样，当遍历到结点*p时，可以进行，若*p有空指针域，则将相应的标志置1；若*p的左线索标志已经建立（p->ltag==1），则可使其前驱线索化，令p->lchild=pre；若*pre的左线索标志已经建立（pre->rtag==1），则可使其后继线索化，令pre->rchild=p;
4、主要过程：
void PreThread(Bithptr *root) {
PreThread(p->lchild); //左子树线索化 if(pre&&pre->rtag==1)pre->rchild=p; //前驱结点后继线索化 if(p->lchild==NULL)
p->ltag=1; p->lchild=pre;
if(p->rchild==NULL) //后继结点前驱线索化
p->rtag=1; pre=p;
PreThread(p->rchild);
}
}
(3) 插入结点函数
1、方法：在树中插入一个结点，就必须要以固定的规则来进行插入。在本程序中对树的输出使用了中序输出的方法，所以插入的时候使用的规则就是以中序输出为顺序，先查找
3文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
线索二叉树的运算
