【数据结构】线索二叉树（适用场景+图文推导过程+C语言代码实现）

导读：

普通二叉树（如下图）：

• 空间浪费：存在大量“∧”，该空间未利用。
• 时间效率：查找一次结点的前驱、后继就需要遍历一次，时间效率低。

        在实际问题中，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

一、线索二叉树

1.定义

        线索二叉树：指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。

2.图文推导

        如下图，把这棵二叉树进行中序遍历后，将所有的空指针域中的rchild，改为指向它的后继结点。于是我们就可以通过指针知道H的后继是D（图I的后继是B（图中②），J的后继是E（图中③），E的后继是A（图中④），F的后继是 C（图中⑤），G的后继因为不存在而指向NULL（图中⑥）。此时共有6个空指针域被利用。

        再如，我们将这棵二叉树的所有空指针域中的lchild，改为指向当前结点的前驱。因此H的前驱是NULL（图中①），I的前驱是D（图中②），J的前驱是B（图中 ③），F的前驱是A（图中④），G的前驱是C（图中⑤）。一共5个空指针域被利用， 正好和上面的后继加起来是11个。

        通过下图（空心箭头实线为前驱，虚线黑箭头为后继），可以看出，其实线索二叉树，等于是把一棵二叉树转变成了一个双向链表，这样对我们的插入删除结点、查找某个结点都带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。

改进：        

        我们不知道某一结点的lchild是指向它的左孩子还是指向前驱？rchild是指向右孩子还是指向后继？在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继上是需要一个区分标志。

        每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是存放0或1数字的布尔型变量，其占用的内存空间要小于像lchild和rchild的指针变量。结点结构如表所示。

其中：

        ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。

        rtag为0时指向该结点的右孩子，为1时指向该结点的后继。 

二、代码段

1.结构定义代码

/* 二叉树的二叉线索存储结构定义 */
/* Link==0表示指向左右孩子指针 */
/* Thread==1表示指向前驱或后继的线索 */
typedef enum { Link, Thread } PointerTag;
/* 二叉线索存储结点结构 */
typedef struct BiThrNode
{
	/* 结点数据 */
	TElemType data;
	/* 左右孩子指针 */
	struct BiThrNode* lchild, * rchild;
	PointerTag LTag;
	/* 左右标志 */
	PointerTag RTag;
} BiThrNode, * BiThrTree;

 2.中序遍历线索化的递归函数代码如下：

BiThrTree pre; /* 全局变量，始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{
	if (p)
	{
		/* 递归左子树线索化 */
		InThreading(p->lchild);
		/* 没有左孩子 */
		if (!p->lchild)
		{
			/* 前驱线索 */
			p->LTag = Thread;
			/* 左孩子指针指向前驱 */
			p->lchild = pre;
		}
		/* 前驱没有右孩子 */
		if (!pre->rchild)
		{
			/* 后继线索 */
			pre->RTag = Thread;
			/* 前驱右孩子指针指向后继（当前结点p） */
			pre->rchild = p;
		}
		/* 保持pre指向p的前驱 */
		pre = p;
		/* 递归右子树线索化 */
		InThreading(p->rchild);
	}
}

3.一般遍历

        在二叉树线索链表上添加一个头结点（和双向链表结构一样），其lchild域的指针指向二叉树的根结点（图中的①），其rchild域的指针指向中序遍历时访问的最后一个结点（图中的②）。反之，令二叉树的中序序列中的第一个结点中，lchild域指针和最后一个结点的rchild域指针均指向头结点（图中的③和④）。

        这样定义的好处就是我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

 遍历的代码如下：

/* T指向头结点，头结点左链lchild指向根结点，
头结点右链rchild指向中序遍历的 */
/* 最后一个结点。中序遍历二叉线索链表表示的二
叉树T */
Status InOrderTraverse_Thr(BiThrTree T)
{
	BiThrTree p;
	/* p指向根结点 */
	p = T->lchild;
	/* 空树或遍历结束时，p==T */
	while (p != T)
	{
		/* 当LTag==0时循环到中序序列第一个结点 */
		while (p->LTag == Link)
			p = p->lchild;
		/* 显示结点数据，可以更改为其他对结点操作 */
		printf("%c", p->data);
		while (p->RTag == Thread && p->rchild != T)
		{
			p = p->rchild;
			printf("%c", p->data);
		}
		/* p进至其右子树根 */
		p = p->rchild;
	}
	return OK;
}

 三、完整测试代码

  线索二叉树完整测试代码如下：

#include "string.h"
#include "stdio.h"    
#include "stdlib.h"   
 
#include "math.h"  
#include "time.h"
 
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
 
#define MAXSIZE 100 /* 存储空间初始分配量 */
 
typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef char TElemType;
typedef enum {Link,Thread} PointerTag;	/* Link=0表示指向左右孩子指针, */
										/* Thread=1表示指向前驱或后继的线索 */
typedef  struct BiThrNode	/* 二叉线索存储结点结构 */
{
	TElemType data;	/* 结点数据 */
	struct BiThrNode *lchild, *rchild;	/* 左右孩子指针 */
	PointerTag LTag;
	PointerTag RTag;		/* 左右标志 */
} BiThrNode, *BiThrTree;
 
TElemType Nil='#'; /* 字符型以空格符为空 */
 
Status visit(TElemType e)
{
	printf("%c ",e);
	return OK;
}
 
/* 按前序输入二叉线索树中结点的值,构造二叉线索树T */
/* 0(整型)/空格(字符型)表示空结点 */
Status CreateBiThrTree(BiThrTree *T)
{ 
	TElemType h;
	scanf("%c",&h);
 
	if(h==Nil)
		*T=NULL;
	else
	{
		*T=(BiThrTree)malloc(sizeof(BiThrNode));
		if(!*T)
			exit(OVERFLOW);
		(*T)->data=h; /* 生成根结点(前序) */
		CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
		if((*T)->lchild) /* 有左孩子 */
			(*T)->LTag=Link;
		CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
		if((*T)->rchild) /* 有右孩子 */
			(*T)->RTag=Link;
	}
	return OK;
}
 
BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{ 
	if(p)
	{
		InThreading(p->lchild); /* 递归左子树线索化 */
		if(!p->lchild) /* 没有左孩子 */
		{
			p->LTag=Thread; /* 前驱线索 */
			p->lchild=pre; /* 左孩子指针指向前驱 */
		}
		if(!pre->rchild) /* 前驱没有右孩子 */
		{
			pre->RTag=Thread; /* 后继线索 */
			pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
		}
		pre=p; /* 保持pre指向p的前驱 */
		InThreading(p->rchild); /* 递归右子树线索化 */
	}
}
 
/* 中序遍历二叉树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); /* 中序遍历进行中序线索化 */
		pre->rchild=*Thrt;
		pre->RTag=Thread; /* 最后一个结点线索化 */
		(*Thrt)->rchild=pre;
	}
	return OK;
}
 
/* 中序遍历二叉线索树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;
}
 
int main()
{
	BiThrTree H,T;
	printf("请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')\n");
 	CreateBiThrTree(&T); /* 按前序产生二叉树 */
	InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
	printf("中序遍历(输出)二叉线索树:\n");
	InOrderTraverse_Thr(H); /* 中序遍历(输出)二叉线索树 */
	printf("\n");
	
	return 0;
}