浅析线索二叉树

线索二叉树是指在二叉树的结点上加上线索的二叉树。这里的线索指的是对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针。本文我们就将以这些指针为线索来为大家解析线索二叉树。

一个二叉树通过如下的方法“穿起来”：所有原本为空的右孩子指针改为指向该节点在中序序列中的后继，所有原本为空的左孩子指针改为指向该节点的中序序列的前驱。

上图这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。

链接规则：

1.结点左子树为空，利用左孩子指针指向它的前驱结点

2.结点右子树为空，利用右孩子指针指向它的后继结点

3.注意：所有前驱和后继只能按照一种遍历逻辑（例如：中序）

通过考察各种二叉链表，不管儿叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，n各结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n+1个。

根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。

实际上也就是当二叉树的左右孩子结点为NUll的时候,指向的地址是浪费的,为了减少浪费我们可以通过将其指向前驱或者后续来利用这些无用的空间,提升查找速度,值得注意的是实际使用中我们要根据选择的二叉树遍历规则来进行对应的指向(前序、中序、后序)要保持一直.一般来说我们使用中序遍历进行二叉树线索化。

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的指针，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。

二叉树本身其实就是一种特殊的树形结构的数据结构，而线索二叉树又是特殊的二叉树。所以，线索二叉树本身的特殊性是值得我们探究的。在本站的数据结构和算法教程中我们也将接触到更多有意思的数据结构，让我们在数据结构世界里初窥门径。