线索二叉树
对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
优势
(1)利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。
(2)任意一个结点都能直接找到它的前驱和后继结点。
不足
(1)结点的插入和删除麻烦，且速度也较慢。
(2)线索子树不能共用。
存储结构
352.001.jpeg
建立规则
（1）如果ptr->lchild为空，则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱；
（2）如果ptr->rchild为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继；
实现
1.数据结构
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Status;
typedef char CElemType;
/* 字符型以空格符为空 */
CElemType Nil='#';
#pragma mark--二叉树构造
int indexs = 1;
typedef char String[24]; /* 0号单元存放串的长度 */
String str;
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
Status visit(CElemType e)
{
printf("%c ",e);
return OK;
}
/*
Link==0表示指向左右孩子指针,
Thread==1表示指向前驱或后继的线索
*/
typedef enum {
Link,
Thread
}PointerTag;
typedef struct BiThrNode {
CElemType data;
//左右孩子指针
struct BiThrNode *lchild,*rchild;
//左右标记
PointerTag LTag,RTag;
}BiThrNode,*BiThrTree;
2.初始化
构建二叉树，可以选择任意一种构建方式，这里演示前序遍历构建。注：（这里不做线索化）
Status CreateBiThrTree(BiThrTree *T) {
CElemType h;
h = str[indexs++];
if (h == Nil) {
*T = NULL;
} else {
*T = (BiThrTree)malloc(sizeof(BiThrNode));
if (!*T) {
exit(OVERFLOW);
}
(*T)->data = h;
//递归构造左子树
CreateBiThrTree(&(*T)->lchild);
//存在左孩子->将标记LTag设置为Link
if ((*T)->lchild) {
(*T)->LTag = Link;
}
CreateBiThrTree(&(*T)->rchild);
if ((*T)->rchild) (*T)->RTag = Link;
}
return OK;
}
3.中序遍历线索化
按照中序遍历规则，添加线索，这里的添加线索和遍历要选同一种遍历规则，才能保证正确性
/* 全局变量,始终指向刚刚访问过的结点 */
BiThrTree pre;
/* 中序遍历进行中序线索化*/
void InThreading(BiThrTree p) {
//递归终止条件：p == NULL;
if (p) {
InThreading(p->lchild);//递归左子树线索化
if (!p->lchild) { //无左孩子
p->LTag = Thread;//则的前驱为线索
p->lchild = pre;//左孩子指针指向前驱
} else {
p->LTag = Link;//为子节点
}
if (!pre->rchild) {//前驱没有右孩子
pre->RTag = Thread;//则的后继为线索
pre->rchild = p;//前驱右孩子指针指向后继(当前结点p)
} else {
pre->RTag = Link;
}
pre = p;//保持pre指向p,下次执行，pre就是前驱
InThreading(p->rchild);//递归右子树线索化
}
}
4.创建头结点建立线索
352.002.jpeg
这样做的好处你也能发现，可以快速找到最后一个节点，而不用递归寻找。
/* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
Status InOrderThreading(BiThrTree *Thrt , BiThrTree T){
*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if (! *Thrt) {
exit(OVERFLOW);
}
//建立头结点;
(*Thrt)->LTag = Link;
(*Thrt)->RTag = Thread;
//右指针回指向
(*Thrt)->rchild = (*Thrt);
/* 若二叉树空,则左指针回指 */
if (!T) {
(*Thrt)->lchild=*Thrt;
}else{
(*Thrt)->lchild=T;
pre=(*Thrt);
//中序遍历进行中序线索化
InThreading(T);
//最后一个结点rchil 孩子
pre->rchild = *Thrt;
//最后一个结点线索化
pre->RTag = Thread;
(*Thrt)->rchild = pre;
}
return OK;
}
4.遍历
这部分遍历也可以看出，少了很多傻瓜式的递归实现，这也验证了线索二叉树的优势：（利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。）
可能while(p->RTag==Thread&&p->rchild!=T)你会比较有疑问，其实很好理解，因为线索是中序遍历生成的，那么当p的标记为线索时，p的lchild自然也是下一个要遍历的节点；直到不为线索时，p就指向右子树
/*中序遍历二叉线索树T*/
Status InOrderTraverse_Thr(BiThrTree T){
BiThrTree p;
p=T->lchild; /* p指向根结点 */
while(p!=T)
{ /* 空树或遍历结束时,p==T */
while(p->LTag==Link)
p=p->lchild;
if(!visit(p->data)) /* 访问其左子树为空的结点 */
return ERROR;
while(p->RTag==Thread&&p->rchild!=T)
{
p=p->rchild;
visit(p->data); /* 访问后继结点 */
}
p=p->rchild;
}
return OK;
}
5.验证
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, 线索化二叉树!\n");
BiThrTree H,T;
//StrAssign(str,"ABDH#K###E##CFI###G#J##");
StrAssign(str,"ABDH##I##EJ###CF##G##");
CreateBiThrTree(&T); /* 按前序产生二叉树 */
InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
InOrderTraverse_Thr(H);
printf("\n\n");
return 0;
}
网友评论