算法速成（十二）树操作之线索二叉树

算法速成（十二）树操作之线索二叉树2014-04-28 csdn博客特种兵—AK47先前说了树的基本操作，我们采用的是二叉链表来保存树形结构，当然二叉有二叉的困扰之处，比如我想找到当前结点

的“前驱”和“后继”，那么我们就必须要遍历一下树，然后才能定位到该“节点”的“前驱”和“后继”，每次定位都是O（n），这

不是我们想看到的，那么有什么办法来解决呢？

（1）在节点域中增加二个指针域，分别保存“前驱”和“后继”，那么就是四叉链表了，哈哈，还是有点浪费空间啊。

（2）看下面的这个二叉树，我们知道每个结点有2个指针域，4个节点就有8个指针域，其实真正保存节点的指针

仅有3个，还有5个是空闲的，那么为什么我们不用那些空闲的指针域呢，达到资源的合理充分的利用。

一：线索二叉树

1 概念

刚才所说的在空闲的指针域里面存放“前驱 ”和“后继”就是所谓的线索。

<1> 左线索：在空闲的左指针域中存放该“结点”的“前驱”被认为是左线索。

<2> 右线索：在空闲的右指针域中存放该“结点“的”后继“被认为是右线索。

当“二叉链表”被套上这种线索，就被认为是线索链表，当“二叉树”被套上这种线索就被认为是线索二叉树，当然线索根据

二叉树的遍历形式不同被分为“先序线索”，“中序线索”，“后序线索”。

2 结构图

说了这么多，我们还是上图说话，就拿下面的二叉树，我们构建一个中序线索二叉树，需要多动动脑子哟。

<1> 首先要找到“中序遍历”中的首结点D，因为“D结点”是首节点，所以不存在 “前驱”，左指针自然是空，

”D节点”的右指针存放的是“后继”，那么根据“中序遍历” 的规则应该是B，所以D的右指针存放着B节点。

<2> 接着就是“B节点”，他的左指针不为空，所以就不管了，但是他的“右指针”空闲，根据规则“B结点“的右

指针存放的是"A结点“。

<3> 然后就是“A节点”，他已经被塞的满满的，所以就没有 “线索”可言了。

<4> 最后就是“C节点”，根据规则，他的“左指针”存放着就是“A节点“，”C节点“是最后一个节点，右指针自然就是空的，你懂的。