1,概念：

线索二叉树是为了解决普通二叉树中结点存在大量的空闲指针域的情况，而在空闲指针域上添加了指向前驱和后继的线索，因此称为线索二叉树。其和双向链表的原理有些相似，这样增加了二叉树的遍历能力。

线索二叉树由多个结点链接而成，结点具备左右指针域和数据域。当然这里的数据域为了便于展示我们设置了id和name两个属性.同时，在后面的遍历中，我们需要判断一个结点是否进行了左、右线索化，所以这里又设置了两个属性leftType和rightType。

/*** 线索二叉树结点*/
class MyThreadedNode {private int no;private String name;private MyThreadedNode left;private MyThreadedNode right;//约定：//leftType=0表示指向左子树，=1表示指向前驱结点//rightType=0表示指向右子树，=1表示指向后驱结点private int leftType;private int rightType;
}
/*** 线索二叉树*/
public class ThreadedBinaryTree {//根结点private MyThreadedNode root;//记录前一个结点便于线索化，也就是tempprivate MyThreadedNode preNode = null;

2,二叉树线索化的三种方式

思路：线索化的过程也就是找到需要线索化的结点，并把他们的指针域指向各自对应的前驱和后继结点即可。
前序线索化：即按照前序遍历的顺序，将二叉树前序线索化，因为不同的遍历方式，一个结点的前驱和后继是不同的，所以有必要对线索化的方式进行区分。
此处以前序线索化为例：
思路：首先找到需要线索化的结点,然后对其左子树线索化，再右子树线索化；
现有二叉树如下图所示，当我们对其前序遍历时知道:1，3无需线索化，第一个线索的结点是8,然后线索其前驱指向其前一个结点3，然后线索化其后继，其后继应该指向10，我们知道只能从3的后继拿到10，然而在递归弹栈中可以拿到上一结点3。
同样的，中序和后序线索化也类似按照上述的方式。

/*** 前序线索化二叉树* @param node*/public void preThreaded(MyThreadedNode node){if(node==null){return;}//直到找到第一个线索化的结点if(node.getLeft()==null){node.setLeft(preNode);node.setLeftType(1);}if(preNode!=null && preNode.getRight()==null ){preNode.setRight(node);preNode.setRightType(1);}//更新前一结点preNode = node;//如果左子树没有线索化，那么线索化左子树if(node.getLeftType()==0){preThreaded(node.getLeft());}//如果右子树没有线索化，那么线索化右子树if(node.getRightType()==0){preThreaded(node.getRight());}}/*** 中序线索化二叉树:* @param node 二叉树的根节点*/public void threaded(MyThreadedNode node){//结点为空if(node==null){return;}//线索化左子树threaded(node.getLeft());//先处理前驱，再处理后继，后继是在下一次的线索中处理的//找到线索结点时，将其前驱结点指向前一结点if(node.getLeft()==null){node.setLeft(preNode);//首次置空node.setLeftType(1);//标记为线索结点，已左线索化}//前驱结点不为空，且前驱结点为线索结点时，后继指向当前结点if(preNode!=null && preNode.getRight()==null ){preNode.setRight(node);preNode.setRightType(1);}//更新preNodepreNode = node;//线索化右子树threaded(node.getRight());}
/*** 后序线索化二叉树* @param node*/public void postThreaded(MyThreadedNode node){if(node==null){return;}postThreaded(node.getLeft());postThreaded(node.getRight());if(node.getLeft()==null){node.setLeft(preNode);node.setLeftType(1);}if(preNode!=null && preNode.getRight()==null){preNode.setRight(node);preNode.setRightType(1);}preNode = node;}

当二叉树线索化之后，我们开始对其进行遍历。
前序遍历的方式：非线索结点直接打印，并更新当前结点到下一结点，直到遇到线索结点时，打印并更新当前结点为其后继。重复此步骤，直到结点为空，即14的后继。
类似的中序遍历同上。

/*** 前序遍历*/public void threadedListPre(){MyThreadedNode node = root;while(node!=null){//先打印没有线索化的结点while(node.getLeftType()==0){System.out.println(node);node = node.getLeft();}//退出时打印当前线索结点System.out.println(node);//向后寻找node = node.getRight();}}/*** 按照中序线索化的形式遍历*/public void threadedList(){MyThreadedNode node = root;while (node!=null){//直到找到线索化的结点，叶子结点while (node.getLeftType()==0){node = node.getLeft();}System.out.println(node);//当前结点存在后继结点便打印while(node.getRightType()==1){node = node.getRight();System.out.println(node);}node=node.getRight();}}

这里要提一下后序遍历。后续遍历相对复杂，这边建议参考下面这个博文：https://www.cnblogs.com/lishanlei/p/10707830.html
这里先直接贴代码：

/*** 后续线索化遍历*/public void threadedListPost(){MyThreadedNode node = root;//找到第一个线索化的结点while(node!=null && node.getLeftType()==0){node = node.getLeft();}while(node!=null){//后继已经线索化的直接打印if(node.getRightType()==1){System.out.println(node);preNode = node;node = node.getRight();}else{//未被线索化结点，其实是一个子树的根节点，此时要区分：//如果当前结点后继是上一结点,即右子树回调的直接打印if(node.getRight()==preNode){System.out.println(node);//注意如果这个子树的根节点为树的根节点，遍历结束if(node==root){return;}preNode = node;//且当前结点置换为父节点，否则继续右线索会导致死循环node = node.getParent();}else {//左子树回调的则不会有死循环的风险，直接左线索遍历node = node.getRight();while(node!=null && node.getLeftType()==0){node = node.getLeft();}}}}}

注意此时我们需要新建一个指针记录父节点：

private MyThreadedNode parent;

然后在新建二叉树时，构建父子结点关系。