【数据结构】—— 线索二叉树

引入

我们现在提倡节约型杜会，一切都应该节约为本。对待我们的程序当然也不例外，能不浪费的时间或空间，都应该考虑节省。我们再观察团下图的二叉树（链式存储结构)，会发现指针域并不是都充分的利用了，有许多的空指针域的存在，这实在不是好现象，应该要想办法利用起来。通常，对于这种情况的常用做法就是使其存储某些数据，方便某种操作！

举个我们之前学习单链表的时候，我们在学习单链表的时候，采用的是带头结点的链式存储结构。通常，头结点的数据域是不存储数据的，但是，我们可以令其存储当前链表的长度。因为单链表的特殊性！当我们需要知道链表的长度时，就需要从头到尾遍历链表，时间复杂度为O(n)，但是，如果我们在头结点的数据域存储当前链表的长度，就可以使上述操作的时间复杂度变成O(1)。

回到二叉树的讨论中，首先我们要来看着这空指针有多少个呢？对于一个有n个结点的二叉树，每个结点有指向左右孩子的两个指针域，所以一共是 2n 个指针域。而 n个结点的二叉树一共有 n -1条分支线数，也就是说，其实是存在 2n - (n -1) = n + 1个空指针域。如上图二叉树的结构示意图所示：共有10个结点，11个空指针域。这些空间不存储任何事物，白白的浪费着内存的资源。那对于二叉树该如何利用这些空间资源！

线索二叉树的定义

回想之前讲述的二叉树的遍历（前、中、后、层序遍历)。我们在做遍历时，比如上图二叉树的结构示意图做中序遍历时，得到了H-D-I-B-J-E-A-F-C-G 这样的字符序列，遍历过后，我们可以知道，结点I的前驱结点是D，后继结点是B，结点F的前驱结点是A，后继结点是C。也就是说，我们可以很清楚的知道任意一个结点，它的前驱和后继是哪一个。可是这是建立在已经遍历过的基础之上的。在二叉链表上，我们只能知道每个结点指向其左右孩子结点的地址，而不知道某个结点的前驱是谁，后继是谁。要想知道，必须遍历一次。以后每次需要知道时，都必须先遍历一次。为什么不考虑在创建时就记住这些前驱和后继呢，那将是多大的时间上的节省。

综合刚才两个角度的分析后，我们可以考虑利用那些空地址，存放指向结点在某种遍历次序下的前驱和后继结点的地址。就好像 GPS 导航仪一样，我们开车的时候，哪怕我们对具体目的地的位置一无所知，但它每次都可以告诉我从当前位置的下一步应该走向哪里。这就是我们现在要研究的问题。

我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树('Threaded Binary Tree) 。

我们把这棵二叉树进行中序遍历后：1、将这棵二叉树的所有空指针域中的lchild，改为指向当前结点的前驱。因此H的前驱是NULL(图中)，I的前驱结点是D(图中)，J的前驱结点是B(图中③)，F的前驱结点是A(图中④)，G的前驱结点是C(图中⑤)。一共5个空指针域被利用。2、将所有的空指针域中的rchild，改为指向它的后继结点。于是我们就可以通过指针知道H的后继结点是D，I的后继结点是 B，J的后继结点是E，E的后继结点是A，F的后继结点是C，G的后继结点因为不存在而指向 NULL。此时共有6个空指针域被利用。总共加起来11个空指针域全部利用！

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

线索二叉树的结构实现

结点结构实现

现在我们已经知道了线索二叉树的概念和实现的思路，但问题并没有彻底解决。我们如何知道某一结点的lchild 是指向它的左孩子还是指向前驱结点？rchild 是指向右孩子还是指向后继结点？比如E结点的lchild是指向它的左孩子，该结点的rchild 却是指向它的后继结点A。显然我们在决定lchild 是指向左孩子还是前驱结点，rchild 是指向右孩子还是后继上是需要一个区分标志的。因此，我们在每个结点再增设两个标志域lTag和rTag。（注意；lTag和rTag的类型，没有明确的限制！按照自己的编程习惯来。通常使用0、1这种布尔值类型。）

关于线索二叉树的结点定义如下：(C/C++混编)

using TBTree_Type = int;
typedef struct TBNode
{
	TBTree_Type val;
	struct TBNode* lChild;
	struct TBNode* rChild;
	PointerTag lTag;
	PointerTag rTag;
	
}TBNode;

成员变量解释：

lTag为0时指向该结点的左孩子，为1时指向该结点的前驱结点。
rTag为0时指向该结点的右孩子，为1时指向该结点的后继结点。

其中关于PointerTag的类型，其实是对枚举类型的封装而已！

typedef enum
{ 
	Link,  //Link = 0
	Thread //Thread = 1
} PointerTag;

因此对于图6-10-1的二叉链表图可以修改为下图所示的样子

线索化

现在，关于线索二叉树的结点结构已经给出！那么假设现在给你一颗二叉树的根结点，那么你要怎么将其变成线索二叉树？我们之前已经提过，其实线索二叉树，等于是把一棵二叉树转变成了一个双向链表，而我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继结点的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程结点中修改空指针的过程。

现在以中序遍历线索化为例！总体的实现思路如下：结点空指针域前驱的填入，需要知道刚刚访问的结点，后继的填入，需要知道下一个访问的结点，所以可以用一个 pre 指针专门用于记录刚刚访问的结点（也就是现在访问的结点的上一个结点)。总体实现思路如下：

如果当前结点的左孩子为空，那么就将当前结点的左孩子指向prev，同时修改当前结点左孩子的标记，那么当前结点的前驱节点就存储完成
后继结点的存储会比较复杂一点，需要判断prev的右孩子是否为空，如果为空，那么就将prev的右孩子指向当前结点，同时修改prev右孩子的标记

代码实现如下：

int inorder_thread(TBNode* root, TBNode*& prev)
{
	if (root == nullptr)
		return;
	inorder_thread(root->lChild, prev);
	if (root->lChild == nullptr)
	{
		root->lTag = Thread;
		root->lChild = prev;
	}
	if (prev != nullptr && prev->rChild == nullptr)
	{
		prev->rTag = Thread;
		prev->rChild = root;
	}
	prev = root;
	inorder_thread(root->rChild, prev);
}

形参解释：

root：二叉树的根结点
prev：指向刚刚访问过的结点（也就是现在访问的结点的上一个结点）

【注意】：关于prev指向谁，如果不理解一定要去画图理解！

如果有学过C++的话，这份代码没有什么难度！没学过的话，我重点提一下形参的TBNode*& prev，‘&’代表引用，就是给变量起别名。不理解也没关系！直接用二级指针TBNode** prev替代、或者使用全局变量。

我们还是来演示一段代码的执行逻辑。从二叉树的根结点开始，此时prev指向空指针（NULL)，因为，当前一个结点都还没有访问；接下来直接递归根结点的左子树（中序遍历的次序)，找到中序遍历的第一个结点‘H’，此时的root指向结点为‘H’的结点，prev还是为NULL，判断root的左孩子是否为空，如果为空，那么就将root的左孩子指向prev（root->lChild = prev)，再将左孩子的结点的标记lTag变成1（root->lTag = Thread)，只是当前结点的前驱结点就存储完成了，

由于当前prev为空指针域，因为中序遍历的第一个访问的结点为'H‘，没有比它更早访问的了。接下来将prev指向root，因外要去遍历当前结点root的右子树，因为root的右子树为空，直接回到结点'D'，这时，prev的右孩子为空，那么就将prev的右孩子指向当前结点root （prev->rChild = root)，同时修改prev的右孩子的标记（prev->rTag = Thread)，再将prev指向当前结点root，因为下一步要去遍历root的右子树了。

不画了！剩下的步骤一样，只要注意prev的改动即可。

遍历操作

有了线索二叉树后，我们对它进行遍历时发现，其实就等于是操作一个双向链表结构。
和双向链表结构一样，在二叉树线索链表上添加一个头结点，如下图所示，并令其 lchild 域的指针指向二叉树的根结点(图中的①)，其rchild 域的指针指向中序遍历时访问的最后一个结点(图中的②)。反之，令二叉树的中序序列中的第一个结点中，Ichild 域指针和最后一个结点的rchild 域指针均指向头结点(图中的③和④)。这样定义的好处就是我们既可以从第一个结点起顺后继结点进行遍历，也可以从最后一个结点起顺前驱结点进行遍历。

代码实现如下：

void thread_inorder(TBNode* head)
{
	TBNode* root = head->lChild;//根结点
	while (root != head)
	{
		while (root->lTag == Link)//查找遍历的第一个结点
		{
			root = root->lChild;
		}
		while (root->rTag == Thread && root->rChild != head)
		{
			printf("%c ", root->val);
			root = root->rChild;
		}
		root = root->rChild; //root进入它的右子树
	}
}

从这段代码也可以看出，它等于是一个双向链表的扫描，所以时间复杂度为 O(n)。由于它充分利用了空指针域的空间(这等于节省了空间)，又保证了创建时的一次遍历就可以终生受用前驱后继的信息(这意味着节省了时间)。所以在实际问题中，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。（说实话，我几乎就没有用过线索二叉树！话又说回来，你可以不用，但是不能不会。可以作为一种拓展知识吧。）