6.10.1 线索二叉树原理

对待我们的程序当然也不例外，能不浪费的时间或空间，都应该考虑节省。我们再来观察图6-10-1，会发现指针域并不是都充分的利用了，有许许多多的“∧”，也就是空指针域的存在，这实在不是好现象，应该要想办法利用起来。

首先我们要来看看这空指针有多少个呢？对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个指针域，所以一共是2n个指针域。而n个结点的二叉树一共有n-1条分支线数，也就是说，其实是存在2n-(n-1)=n＋1个空指针域。比如图6-10-1有10个结点，而带有“∧”空指针域为11。这些空间不存储任何事物，白白的浪费着内存的资源。

另一方面，我们在做遍历时，比如对图6-10-1做中序遍历时，得到了HDIBEJAFCG这样的字符序列，遍历过后，我们可以知道，结点I的前驱是D，后继是B，结点F的前驱是A，后继是C。也就是说，我们可以很清楚的知道任意一个结点，它的前驱和后继是哪一个。

可是这是建立在已经遍历过的基础之上的。在二叉链表上，我们只能知道每个结点指向其左右孩子结点的地址，而不知道某个结点的前驱是谁，后继是谁。要想知道，必须遍历一次。以后每次需要知道时，都必须先遍历一次。为什么不考虑在创建时就记住这些前驱和后继呢，那将是多大的时间上的节省。

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

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

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

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

不过好事总是多磨的，问题并没有彻底解决。我们如何知道某一结点的lchild是指向它的左孩子还是指向前驱？rchild是指向右孩子还是指向后继？比如E结点的lchild是指向它的左孩子J，而rchild却是指向它的后继A。显然我们在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继上是需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是存放0或1数字的布尔型变量，其占用的内存空间要小于像lchild和rchild的指针变量。结点结构如表6-10-1所示。

其中：

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

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