线索二叉树图文详解
线索二叉树（或引线二叉树，Threaded BinaryTree）是添加了直接指向节点的前驱和后继指针的二叉树。我们知道在二叉树中每个节点都有两个指针，分别指向左子树和右子树。如果某个节点只有一个子节点，那么它有一个指针是指向空的，如果某个节点是叶子节点，那么他的两个指针都指向空。这些空的指针能不能被利用起来呢？当然是可以的。
如果一个节点的左指针为空，就让他左指针指向他的前驱节点，如果一个节点的右指针为空，就让他右指针指向他的后继节点。这样构造的二叉树就是线索二叉树。为了区分一个节点的左指针究竟是指向左子节点还是前驱节点，我们需要使用一个变量来区分，同理右指针也一样，节点类如下。
public class BiTreeNode{
public int val;// 节点值
// isPre 为false时，left指向左子节点。
// isPost 为false时，right指向右子节点。
// isPre 为true时，left指向前驱节点。
// isPost 为true时，right指向后继节点。
public boolean isPre, isPost;
// 二叉树的左右子节点
public BiTreeNode left, right;
public BiTreeNode parent;// 后续遍历的时候会用到，前序和中序遍历用不到。
public BiTreeNode() {
}
public BiTreeNode(int val) {
this.val = val;
}
}注意这里的说的前驱节点和后继节点在不同的遍历方式中值是不同的。比如前序遍历的结果是 [a，b，c，d]，那么 b 的前驱节点就是 a ，后继节点是 c 。比如后续遍历的结果是 [a，b，c，d]，c 的前驱节点就是 b ，后继节点是 d 。
线索化
对二叉树以某种遍历顺序进行扫描并为每个节点添加线索的过程称为二叉树的线索化，进行线索化的目的是为了加快查找二叉树中某节点的前驱和后继的速度。 那么在有 N 个节点的二叉树中需要利用 N+1 个空指针添加线索。这是因为在 N 个节点的二叉树中，每个节点有 2 个指针，所以一共有 2N 个指针，除了根节点以外每一个节点都有一个指针从它的父节点指向它，所以一共使用了 N-1 个指针。所以剩下 2N-(N-1) 个空指针（来自维基百科）。
无论是前序遍历，中序遍历还是后序遍历，如果一个节点没有左子节点就让他的左指针指向他的前驱节点，如果一个节点没有后继节点，就让他的右指针指向他的后继节点。我们来看下二叉树的前中后三种线索化的步骤。
二叉树前序线索化
二叉树的前序线索化如上图所示，这里要注意遍历的时候需要使用一个变量 pre 记录每一个节点的前驱节点，
如果当前节点的左指针为空，就让当前节点的左指针指向前驱节点 pre 。
如果当前节点的右指针为空，需要让当前节点的右指针指向他的后继节点，但是这个时候后继节点还没有遍历到。所以这个时候我们一般不操作当前节点，而是操作前一个节点，因为当前节点是前一个节点的后继节点。如果前一个节点 pre 的右指针为空，就让 pre 的右指针指向当前节点。
代码如下所示。
// 前驱节点
private BiTreeNode pre;
// 二叉树的前序线索化算法
private void preThread(BiTreeNode root) {
if (root == null)
return;
// 左子节点为空，让left指向前驱节点
if (root.left == null) {
root.left = pre;
root.isPre = true;//left标记为指向前驱节点。
}
// 处理的是前一个节点的右子节点。
if (pre != null && pre.right == null) {
pre.right = root;// pre的右指针指向当前节点
pre.isPost = true;
}
pre = root;// 更新pre节点
if (!root.isPre)
preThread(root.left);// 递归左子树
if (!root.isPost)
preThread(root.right);// 递归右子树
}
二叉树中序线索化
二叉树的前序，中序以及后续线索化代码非常相似，只不过线索化的位置不太一样，来看下。
// 二叉树的中序线索化算法
private void inThread(BiTreeNode root) {
if (root == null)
return;
if (!root.isPre)
inThread(root.left); // 递归左子树
// 左子节点为空，处理的是当前节点。
if (root.left == null) {
root.left = pre;// 左指针指向前驱节点
root.isPre = true;
}
// 处理的是上一个节点的右子节点。
if (pre != null && pre.right == null) {
pre.right = root;// pre的右指针指向后继节点
pre.isPost = true;
}
pre = root;// 更新pre节点
if (!root.isPost)
inThread(root.right); // 递归右子树
}
二叉树后序线索化
后线索化之后在遍历的时候不太方便，遍历的时候还需要知道每个节点的父节点，所以在线索化的时候要记录下。
线索二叉树的后序遍历可以看做是从下往上遍历，如果根节点没有右子节点，相当于根节点是最后一个被遍历的，我们查找后继节点的时候都是操作前一个节点，所以根节点的后继节点没有被赋值，所以在操作完之后还需要单独判断下。
private void postThread(BiTreeNode root) {
postThreadHelper(root);
// 如果根节点没有右子节点，需要把根节点的 isPost 变成 true 。
if (root.right == null)
root.isPost = true;
}
private void postThreadHelper(BiTreeNode root) {
if (root == null)
return;
// 如果有父节点，记录当前节点的父节点。
if (root.left != null && !root.isPre)
root.left.parent = root;
if (root.right != null && !root.isPost)
root.right.parent = root;
if (!root.isPre)
postThreadHelper(root.left); // 递归左子树
if (!root.isPost)
postThreadHelper(root.right); // 递归右子树
// 左子节点为空，处理的是当前节点。
if (root.left == null) {
root.left = pre;// 左指针指向前驱节点
root.isPre = true;
}
// 处理的是上一个节点的右子节点。
if (pre != null && pre.right == null) {
pre.right = root;
pre.isPost = true;
}
pre = root;// 更新pre节点
}
线索二叉树前序遍历
在线索二叉树的前序遍历中先打印当前节点，然后是左子节点，最后是右子节点。根节点就是第一个被访问的节点，所以从根节点开始打印。如果当前节点有左子节点，把右指针断开。如果当前节点没有左子节点，把左指针（指向前驱节点）断开。注意这里的断开并不是真正的断开，只是我们假象的。如下图所示，就变成了一个链表，这题就变成了对链表的打印，这个就比较简单了。
步骤如下：
如果当前节点有左子节点下一步到到当前节点的左子节点。
如果当前节点没有左子节点，下一步到当前节点的右子节点。注意这里的右子节点并不一定是真正的右子节点，也有可能是我们线索化的时候串起来的。所以这里不需要判断究竟是右子节点还是后继节点。
代码如下：
private void threadPreTraverse(BiTreeNode root) {
BiTreeNode cur = root;
while (cur != null) {
System.out.println(cur.val);// 打印当前节点
// 如果没有左子节点，下一步到右子节点，否则下一步继续到左子节点。
cur = cur.isPre ? cur.right : cur.left;
}
}
线索二叉树中序遍历
线索二叉树中序遍历的顺序是左子节点，当前节点，右子节点。在打印当前节点的时候必须把当前节点的左子树都打印完才能打印当前节点。所以在打印当前节点之前必须先找到当前节点一直往左的节点。
步骤如下：
一直找到最左边的节点，然后打印该节点。
如果该节点有右子节点，继续按照上面的步骤操作右子节点。
如果该节点没有右子节点，就一直遍历后继节点，直到没有后继节点为止。
代码如下：
private void threadInTraverse(BiTreeNode root) {
BiTreeNode cur = root;
while (cur != null) {
// 一直往左找到最左边的子节点。
while (!cur.isPre)
cur = cur.left;
System.out.println(cur.val);
// 如果没有右子节点，一直遍历后继节点，否则找右子节点。
while (cur.isPost) {
cur = cur.right;// 到 cur 的后继节点。
System.out.println(cur.val);
}
cur = cur.right;
}
}
线索二叉树后序遍历
线索二叉树后序遍历的顺序是左子节点，右子节点，当前节点。他是先打印子节点，最后在打印当前节点。可以看做是二叉树从下往上打印，我们知道在二叉树中可以很容易找到一个节点的子节点，但很难找到一个节点的父节点，所以在前面二叉树后序遍历线索化的时候我们记录了每一个节点的父节点。
步骤如下：
找到当前节点最左边的节点，看他有没有右子节点，如果没有右子节点，直接打印该节点，下一步到该节点的后继节点。
如果有右子节点需要打印完右子树之后才能打印该节点，所以需要判断右子树有没有被打印完，如果右子树没被打印完，到右子树中继续按照上面的步骤执行。如果右子树打印完了，就打印该节点，表示该节点为根节点的子树也都被打印完了，下一步到该节点的父节点继续打印。
代码如下：
private void threadPostTraverse(BiTreeNode root) {
BiTreeNode cur = root;
// 找到最左边的节点
while (cur != null && !cur.isPre)
cur = cur.left;
BiTreeNode pre = null;// 后序遍历中前一个节点
while (cur != null) {
if (cur.isPost) {
// 如果没有右子节点，就打印当前节点。
System.out.println(cur.val);
pre = cur;
cur = cur.right;// 下一步到后继节点
} else {
// 如果有右子节点，判断右子树有没有打印完。
if (cur.right == pre) {
// 当前节点的子树都打印完了，打印当前节点。
System.out.println(cur.val);
pre = cur;// 更新 pre 节点。
// 后续遍历可以看做是从下往上打印，右子节点都打印完了，下一步该到父节点了
cur = cur.parent;
} else {// 当前节点的右子树还没打印，到右子树中打印。
cur = cur.right;
// 还是找到当前节点最左边的节点。
while (cur != null && !cur.isPre)
cur = cur.left;
}
}
}
}