数据结构_012_线索二叉树
二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。
对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的指针，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。
根据二叉树遍历序列的不同，每个结点的前驱和后继也不同。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
引自百度百科
线索二叉树
在含有 个结点的二叉树中，所有结点总共有 个空指针。
很好理解，因为除开根节点外，其他 个结点都会有来自它父结点的一个分支指向它，二叉树总指针树是 ，所以总共有 个空指针。
充分利用结点的空指针记录结点的前驱和后继，引入线索二叉树正是为了加快查找结点前驱和后继的速度。
>>左右指针的含义<<
如果结点有左子结点，那么结点的左指针就指向左子结点，否则指向该结点的前驱。
如果结点有右子结点，那么结点的右指针就指向右子结点，否则指向该结点的后继。
构造线索二叉树
二叉树的线索化必须指明是什么遍历顺序的线索化，可分为前序线索二叉树，中序线索二叉树，后序线索二叉树。
构造线索二叉树，可以使用一个辅助变量pre指针指向当前结点p的按照遍历顺序的上一个结点。也就是说，pre是p的前驱，p是pre的后继。在遍历的过程中，判断p的左指针是否为空，是则将其指向pre。判断pre的右指针是否是空，是则将pre其指向p。
以中序二叉树为例
>>中序构造线索二叉树<<
结点对象：
/**
* 线索化结点
*/
private static class ThreadedNode<E>{
/**
* 结点元素域
*/
private E element;
/**
* 左子树指针
*/
private ThreadedNode<E> left;
/**
* 右子树指针
*/
private ThreadedNode<E> right;
/**
* 0表示指向的是左子结点 默认0
* 1表示指向前驱结点
*/
private int leftTag;
/**
* 0表示指向是右子结点 默认0
* 1表示指向后继结点
*/
private int rightTag;
// 省略 get set
}
线索化二叉树对象属性：
public class ThreadedBinaryTree<E> {
/**
* 根结点
*/
private ThreadedNode<E> root;
/**
* 线索化二叉树辅助指针,指向当前结点的前驱
*/
private ThreadedNode<E> pre;
}
初始化一个二叉树：
/**
* 笨比方法 手动创建一个二叉树，直观图如下
*
* 曹操
* / \
* 曹丕 曹植
* / \ \
* 曹睿 曹协 曹志
* \
* 曹芳
*/
中序线索化该二叉树：
/**
* 中序线索化二叉树
*/
public void inThread() {
if (root == null) {
return;
}
pre = null;
inThread(root);
if (pre != null) {
// 处理最后一个结点 因为最后一个结点的状态未设置就退出了
pre.setRightTag(1); // 设置为1是因为最后一个结点的右指针肯定指向null的
pre.setRight(null);
}
}
private void inThread(ThreadedNode<E> node) {
if (node == null) {
return;
}
if (node.getLeft() != null) {
inThread(node.getLeft());
}
if (node.getLeft() == null) {
// 当前结点的左指针为空，使该指针指向前驱，即pre
node.setLeft(pre);
node.setLeftTag(1); // 修改指针类型
}
if (pre != null && pre.getRight() == null) {
// 当前结点的前驱结点的右指针为空，使该指针指向其后驱，即node
pre.setRight(node);
pre.setRightTag(1); // 修改指针类型
}
pre = node; // 保持pre指向p的前驱
// System.out.println(node);
if (node.getRight() != null) {
inThread(node.getRight());
}
}
线索化之后：
遍历中序线索二叉树
当二叉树线索化之后，就不能使用之前的方法来遍历二叉树了，需要使用新的手段来遍历。
递归遍历
只需要将进入递归的条件改一下即可。
之前判断是否进入递归是判断当前结点的左右结点司法为空，为空才会去递归。先在需要判断当前结点的左右指针的标志即可，假如标志指针是指向后继结点的，那么就去递归。
/**
* 中序遍历二叉树 递归
* @param node
*/
public void inOrder01(ThreadedNode<E> node) {
if (node == null) {
return;
}
if (node.getLeftTag() != 1) {
inOrder01(node.getLeft());
}
System.out.println(node);
if (node.getRightTag() != 1) {
inOrder01(node.getRight());
}
}
循环遍历1
/**
* 中序遍历线索二叉树 非递归
* 思路：
* 1.首先找到最左边的结点，此结点是中序遍历的第一个结点
* 2.打印结点
* 3.因为线索化二叉树的指针可能会指向后继结点，
* 所以沿着右索引查找当前结点的后继结点并打印，直到rightTag == 0
* 4.遍历当前结点的右子树
* 循环往复
*/
public void inOrder02() {
ThreadedNode<E> node = root; // 获取根结点
while (node != null) {
// 首先找到最左边的结点
while (node.getLeftTag() == 0) {
node = node.getLeft();
}
// 打印结点
System.out.println(node);
// 判断当前结点的右指针是否指向后继结点
while (node.getRightTag() == 1 && node.getRight() != null) {
// 循环条件，右指针指向的结点是当前结点的后继结点，直接打印
node = node.getRight(); // 访问后继结点
System.out.println(node);
}
// 遍历右子树
node = node.getRight();
}
}
循环遍历2
其实思路和上面的那种一样，只不过是换了个形式。
思路：
我们可以把二叉树的中序的序列看成是一个链表，每次都去查找后继结点，按照链表的方式遍历。
1、首先找到中序遍历的第一个结点。方法是：中序遍历的第一个结点是从根节点一直往左找，最左的结点就是了。
2、然后就是找某个结点的后继，方法是：
假如右指针是线索，则其指向的结点是后继结点，直接打印。
假如右指针是指向右子结点，则其右子树的最左侧结点就是后驱结点。
/**
* 中序遍历线索二叉树 非递归
*/
public void inOrder03() {
ThreadedNode<E> node = root;
for(node = firstNode(node); node != null; node = nextNode(node)) {
System.out.println(node);
}
}
/**
* 找到某个结点 中序遍历的 第一个访问的结点
* @param node
* @return
*/
private ThreadedNode<E> firstNode(ThreadedNode<E> node) {
if (node == null) {
return null;
}
// 直到找到结点的左指针标记为1的，说明就是最左结点了(但是不一定是叶子结点)
while (node.getLeftTag() == 0) {
node = node.getLeft();
}
return node;
}
/**
* 找到某个结点的下一个结点
* 假如当前结点的rightTag标志为 1 说明其指向后继结点 直接返回
* 假如当前结点的rightTag标志为 0 说明其指向右子结点 返回右子结点的最左结点
*
* @param node
* @return
*/
private ThreadedNode<E> nextNode(ThreadedNode<E> node) {
if (node == null) {
return null;
}
if (node.getRightTag() == 1) {
return node.getRight();
} else {
// 访问右结点的 后继 右子树最左下的结点
return firstNode(node.getRight());
}
}
反向遍历中序线索二叉树
反向遍历中序线索二叉树，思路和正序是相反的。
思路：
1、先找到中序遍历的最后一个结点，从根结点开始往右找，最右侧的结点就是中序序列的最后一个结点了。
2、找当前结点的前驱：
假如左指针是线索，则其指向结点为前驱结点，直接返回。
假如左指针指向的左子结点，则其左子树的最右侧结点为其前驱结点。
/**
* 反向中序遍历 线索二叉树
*/
public void inOrderReverse() {
ThreadedNode<E> node = root;
for(node = lastNode(node); node != null; node = preNode(node)) {
System.out.println(node);
}
}
/**
* 找到中序最后一个结点
* 中序遍历的 最后一个结点 是 最右边的结点 不一定是叶子结点
*/
private ThreadedNode<E> lastNode(ThreadedNode<E> node) {
if (node == null) {
return null;
}
while (node.getRightTag() == 0) {
node = node.getRight();
}
return node;
}
/**
* 找到中序遍历 的上一个节点
* 假如当前结点的leftTag标志为 1 说明其指向前驱结点 直接返回
* 假如当前结点的leftTag标志为 0 说明其指向左子结点 返回左子结点的最右结点
*/
private ThreadedNode<E> preNode(ThreadedNode<E> node) {
if (node == null) {
return null;
}
if (node.getLeftTag() == 1) {
return node.getLeft();
} else {
return lastNode(node.getLeft());
}
}
先序和后序索引二叉树
这两种二叉树的创建和中序索引二叉树的创建代码基本一样，只是线索化部分的代码的位置不一样。
先序线索二叉树找后继：
假如某个结点有左子结点，那么左子结点就是其后继。
假如某个结点没有左子结点但是有右子结点，那么右子结点就是其后继。
假如某个结点是叶子结点，那么右指针指向的结点就是其后继。
后续线索二叉树找后继：
重点是要利用父结点，可以使用存三个指针的二叉树，多一个指向父节点的指针。
假如是根结点，后继为null，因为是最后一个结点。
假如某个结点是其父结点的右子结点，或者是其父结点的左子结点且其父结点没有右子树，则其后继是其父结点。
假如某个结点是其父结点的左子结点，且父结点有右子结点，则其后继是父结点的右子树上后序遍历的第一个结点。
小结
对于频繁查找前驱和后继的计算，线索二叉树优于普通二叉树。
但是对于插入和删除操作，线索二叉树比普通二叉树开销大，因为除插入和删除操作外，还要修改相应的线索。