普通的二叉树有左右孩子两个指针域，但是有些节点的这两个域是空的，这样就造成了空间的浪费。我们可以把左孩子指针域指向遍历时此节点的上一个节点，右孩子指针域指向遍历时此节点的下一个节点。 如这图c，d，e，f都有空闲的指针域可以利用。 图中的中序遍历结果为4，2，5，1，6，3 打个比方此时线索化后e节点的左孩子指针域就可以放前驱b，右孩子指针域可以放后继a
但是如果指针域可以放前驱后继，也可以放树本身连接的孩子节点，那我们怎么才能知道什么时候放的是遍历顺序前后的节点呢？因此需要设置flag变量来标识。
节点： flag为0说明指向的是孩子，为1说明指向的是前驱或后继。
class Node{ private int no; private String name; private Node left; private Node right; //0代表子树，1代表前后继 private int leftFlag; private int rightFlag; //指向前驱节点 static private Node pre; }线索化： 具体的线索化可以根据不同的顺序来写，这里采用中序遍历。大体上和写遍历树的代码相同，但是这里要一个前驱节点pre。
首先线索化左子树当线索化当前节点的时候，如果左孩子为空，说明可以放前驱节点了，并且把leftFlag设为1。如果前驱节点不为空并且右孩子为空，则可以把前驱节点的右孩子指针指向后继节点，即当前节点，再把rightFlag设为1。当然前驱还要设置成当前节点才能继续下一个节点的线索化。线索化当前节点后还要继续线索化右子树。 public static void threadedNodes(Node node){ if (node == null) return; //线索化左子树 threadedNodes(node.left); //线索化当前节点 if (node.left == null){ node.left = pre; node.setLeftFlag(1); } if (pre != null && pre.right == null){ pre.right = node; pre.setRightFlag(1); } //前驱节点变成当前节点 pre = node; //线索化右子树 threadedNodes(node.right); }线索化遍历：
/** * 中序遍历线索化 */ public void threadedInfix(){ //辅助节点初始化指向根节点 Node node = root; while (node != null){ //如果节点的左flag为0说明是左指针并没被线索化，则一直往左追 while (node.leftFlag == 0){ node = node.left; } //此时左指针被线索化，先打印出此节点 System.out.println(node); //如果右指针指向的是后继，则一边往右追一边打印，因为右指针本来就是指向中序输出的下一个节点 while (node.rightFlag == 1){ node = node.right; System.out.println(node); } //如果右指针没被线索化，则把node的右节点赋给node，继续下一次循环 node = node.right; } }输出结果：
Node{no=4, name='d} Node{no=2, name='b} Node{no=5, name='e} Node{no=1, name='a} Node{no=6, name='f} Node{no=3, name='c}中序查找： 按照同样的思路可以写出中序查找
/** * 中序查找 * @param no * @return */ public Node infixSearch(int no){ Node resNode = null; if (this.left != null) resNode = this.left.infixSearch(no); if (resNode != null) return resNode; else if (this.no == no) return this; if (this.right != null) resNode = this.right.infixSearch(no); return resNode; }