【数据结构之线索二叉树】线索二叉树的原理及缔造

一颗普通二叉树

乍一看，会不会有一种违和感?整个结构一共有 7 个结点，总共 14 个指针域，其中却有 8 个指针域都是空的。对于一颗有 n 个结点的二叉树而言，总共会有 n+1 个空指针域，这个规律使用所有的二叉树。

这么多的空指针域是不是显得很浪费?我们学习数据结构和算法的重点就是在想法设法地提高时间效率和空间利用率。这么多的指针域就这么白白浪费了，太败家了!

所以我们要想法子好好利用它们，利用它们来帮助我们更好地使用二叉树这个数据结构。

那么如何利用呢?

前面已经强调过很多次了，遍历二叉树的实质是将二叉树中非线性结构的结点转化为线性的序列，然后才能方便我们遍历。

比如上图的中序遍历序列为：DBGEACF。

对于一个线性序列(线性表)来说，它有直接前驱和直接后继的概念(在【什么是线性表?】中介绍过)。比如在中序遍历序列中，B 的直接前驱为 D，直接后继为 G。

我们之所以能知道 B 的直接前驱和直接后继，是因为我们按照中序遍历的算法，把二叉树的中序遍历序列写出来了，然后根据这个顺序序列说谁的前驱是谁、后继是谁。

直接前驱和直接后继是不能完全直接通过二叉树得到的，因为二叉树中只有双亲和孩子结点之间的直接关系，即二叉树的结点指针域中只存储了其孩子结点的地址。

现在的需求是，我想能直接从二叉树上得到某结点在中序遍历方式下的直接前驱和直接后继。

这时候就需要用到线索二叉树了。

2. 什么是线索二叉树?

当然，我们肯定需要借助结点的指针域来保存直接前驱和直接后继的地址。

其实，在上图的普通二叉树中(以中序遍历得到的序列)，部分结点(指针域不为空的结点)是可以找到其直接前驱或后继的，比如结点 E 的左孩子 G 就是结点 E 的直接前驱;结点 A 的右孩子 C 就是结点 A 的直接后继。

但部分结点(指针域为空)是行不通的，比如结点 G 的直接后继是 E，直接前驱是 B，但在二叉树中却不能得出这样的结论。怎么办呢?我们注意到，结点 G 的两个指针域都为 NULL，并未被利用，那么我们使用这两个指针，分别指向其前驱和后继不就好了吗?.

（编辑：漯河站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!