数据结构的C++实现之线索二叉树

数据结构的C++实现之线索二叉树2013-08-16 csdn Simba888888我们知道满二叉树只是一种特殊的二叉树，大部分二叉树的结点都是不完全存在左右孩子的，即很多指针域没有被充分地利用。另一方面我们在对一棵二叉树做某种次序遍历的时候，得到一串字符序列，遍历过后，我们可以知道结点之间的前驱后继关系，也就是说，我们可以很清楚地知道任意一个结点，它的前驱和后继是哪一个。可是这是建立在已经遍历过的基础之上的。在二叉链表上，我们只能知道每个结点指向其左右孩子结点的地址，而不知道某个结点的前驱是谁，后继是谁。要想知道，必须遍历一次。以后每次需要知道时，都必须遍历一次。为什么不考虑在创建时就记住这些前驱和后继呢？那将是多大的时间上的节省。

综合刚才两个角度的分析后，我们可以考虑利用那些空地址，存放指向结点在某次遍历次序下的前驱和后继结点的地址。我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。

如图6-10-2，我们把这棵二叉树进行中序遍历后，将所有的空指针域中的rchild，改为指向它的后继结点。

如图6-10-3，我们把这棵二叉树进行中序遍历后，将所有的空指针域中的lchild，改为指向它的前驱结点。

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