二叉树本身是一种非线性结构，然而当你对二叉树进行遍历时，你会发现遍历结果是一个线性序列。这个序列中的节点存在前驱后继关系。因此，如何将这种前驱后继信息赋予给原本的二叉树呢？这就是二叉树的线索化过程。所以可以通过丰富原有的二叉树构建一棵可以知道结点的前驱后继的新的二叉树，我们叫它线索二叉树。
1 public class ThreadNode<E> { 2 3 public E data; 4 public ThreadNode<E> lnode; 5 public ThreadNode<E> rnode; 6 7 enum tag {CHILD, THREAD}; 8 public tag ltag; 9 public tag rtag; 10 11 public ThreadNode(E data){ 12 this.data = data; 13 ltag = tag.CHILD; 14 rtag = tag.CHILD; 15 } 16 17 public ThreadNode(){} 18 }
为了充分利用二叉树的空指针域，我们可以将结点线索依附在这些空指针中。这样一来，在我们访问根节点的左右节点时，我们必须要区分什么时候是线索，什么时候子女指针。因此为每个节点设置两个标志位。
在遍历二叉树的时候顺便进行线索化。线索化就是没遇到一个节点存在空指针域就要立即填上它的前驱（左指针空）或者后继（右指针空）。
1 /** 2 * 利用中序非递归遍历对二叉树进行线索化 3 * @author sheepcore 4 */ 5 public void createInThread(){ 6 if(root == null) 7 return; 8 ThreadNode<E> pre = null; 9 ThreadNode<E> cur = root; 10 MyStack<ThreadNode<E>> stack = new MyStack<>(); 11 while (cur != null || !stack.isEmpty()) { 12 while (cur != null){ 13 stack.push(cur); 14 cur = cur.lnode; 15 } 16 if(!stack.isEmpty()){ 17 cur = stack.pop(); 18 if(cur.lnode == null) { //当前节点的前驱作为线索 19 cur.lnode = pre; 20 cur.ltag = ThreadNode.tag.THREAD; 21 } 22 if(pre != null && pre.rnode == null){ 23 pre.rnode = cur; //当前节点的前驱的后继节点是当前节点 24 pre.rtag = ThreadNode.tag.THREAD; 25 } 26 pre = cur; 27 if(cur.rnode != null){ 28 cur = cur.rnode; 29 } 30 else 31 cur = null; 32 33 } //if 34 } //while 35 }
以中序线索二叉树的遍历为例。getFirst(root) 和 getNext(root) 分别是获取中序遍历中以 root 为根的第一个访问的节点和 root 的后继节点。这两个辅助函数在最后面的完整代码有实现。
1 public void inOrder(ThreadNode<E> root){ 2 ThreadNode<E> cur; 3 for (cur = getFirst(root); cur != null; cur = getNext(cur)) { 4 visit(cur); 5 } 6 }
1 public class ThreadTree <E> { 2 3 private ThreadNode<E> root; 4 5 /** 6 * using for construct a binary tree with its element as an integer 7 */ 8 public ArrayList<Integer> list; 9 10 public ThreadNode<E> getRoot() { return root; } 11 12 public ThreadTree(){ 13 list = new ArrayList<>(); 14 } 15 16 /** 17 * build a binary tree in a preorder way recursively 18 * @return root 19 * @author sheepcore 20 */ 21 public ThreadNode<E> generate() { 22 if(list.isEmpty()) 23 return null; 24 int data = list.get(0); 25 list.remove(0); 26 ThreadNode<E> node; 27 28 if(data != -1) { 29 node = (ThreadNode<E>) new ThreadNode<Integer>(data); 30 node.lnode = generate(); //generate left subtree 31 node.rnode = generate(); //generate right subtree 32 return node; 33 } 34 else 35 return null; 36 } 37 38 /** 39 * build a binary tree in preorder 40 * @param treeSequence "1 2 -1 -1 3 -1 -1 " 41 */ 42 public void preOderBuild(String treeSequence) { 43 String[] nodes = treeSequence.split("\\s+"); 44 for (int i = 0; i < nodes.length; i++) { 45 list.add(Integer.parseInt(nodes[i])); 46 } 47 root = generate(); 48 } 49 50 /** 51 * 利用中序非递归遍历对二叉树进行线索化 52 * @author sheepcore 53 */ 54 public void createInThread(){ 55 if(root == null) 56 return; 57 ThreadNode<E> pre = null; 58 ThreadNode<E> cur = root; 59 MyStack<ThreadNode<E>> stack = new MyStack<>(); 60 while (cur != null || !stack.isEmpty()) { 61 while (cur != null){ 62 stack.push(cur); 63 cur = cur.lnode; 64 } 65 if(!stack.isEmpty()){ 66 cur = stack.pop(); 67 if(cur.lnode == null) { //当前节点的前驱作为线索 68 cur.lnode = pre; 69 cur.ltag = ThreadNode.tag.THREAD; 70 } 71 if(pre != null && pre.rnode == null){ 72 pre.rnode = cur; //当前节点的前驱的后继节点是当前节点 73 pre.rtag = ThreadNode.tag.THREAD; 74 } 75 pre = cur; 76 if(cur.rnode != null){ 77 cur = cur.rnode; 78 } 79 else 80 cur = null; 81 82 } //if 83 } //while 84 } 85 86 87 public ThreadNode<E> getFirst(ThreadNode<E> root){ 88 ThreadNode<E> cur = root; 89 while (cur != null && cur.ltag == ThreadNode.tag.CHILD){ 90 cur = cur.lnode; 91 } 92 return cur; 93 } 94 95 public ThreadNode<E> getLast(ThreadNode<E> root){ 96 ThreadNode<E> cur = root; 97 while (cur != null && cur.rtag == ThreadNode.tag.CHILD){ 98 cur = cur.rnode; 99 } 100 return cur; 101 } 102 103 public ThreadNode<E> getNext(ThreadNode<E> root){ 104 ThreadNode<E> cur = root; 105 if(cur.rtag == ThreadNode.tag.THREAD) 106 return cur.rnode; 107 else 108 return getFirst(cur.rnode); 109 110 } 111 112 public ThreadNode<E> getPrior(ThreadNode<E> root){ 113 ThreadNode<E> cur = root; 114 if(cur.ltag == ThreadNode.tag.THREAD) 115 return cur.lnode; 116 else 117 return getLast(cur.lnode); 118 119 } 120 121 public void visit(ThreadNode<E> root){ 122 if(root != null && root.data != null){ 123 System.out.print(root.data); 124 System.out.print("\t"); 125 } 126 } 127 128 /** 129 * inorder traversal 130 * @param root 131 * @author sheepcore 132 */ 133 public void inOrder(ThreadNode<E> root){ 134 ThreadNode<E> cur; 135 for (cur = getFirst(root); cur != null; cur = getNext(cur)) { 136 visit(cur); 137 } 138 } 139 140 public static void main(String[] args) { 141 142 String str = "0 1 -1 3 -1 -1 2 4 -1 -1 -1"; 143 ThreadTree<Integer> threadTree = new ThreadTree<>(); 144 threadTree.preOderBuild(str); 145 threadTree.createInThread(); 146 threadTree.inOrder(threadTree.getRoot()); 147 } 148 }
数据结构之二叉树篇卷四 -- 二叉树线索化（With Java)
原文：https://www.cnblogs.com/sheepcore/p/11604949.html
