1. 线索化二叉树
   

   ① n个结点的二叉树有n+1个空指针域，上图有6个结点，所以它的空指针域有7个。我们可以利用二叉树中的空指针域，存放指向当前结点在某种遍历次序下的前驱和后继结点的指针，这种附加的指针称为“线索”。

   ② 这种加上了线索的二叉树称为线索二叉树。根据遍历次序的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

   ③ 前驱、后继结点是相对于遍历次序来说的，遍历次序在当前结点前一位的结点称为前驱结点，后一位称为后继结点。
   

package DataStructure;public class ThreadBinaryTreeDemo {public static void main(String[] args) {ThreadHero root = new ThreadHero(1, "tom");ThreadHero hero1 = new ThreadHero(3, "tom");ThreadHero hero2 = new ThreadHero(6, "tom");ThreadHero hero3 = new ThreadHero(8, "tom");ThreadHero hero4 = new ThreadHero(10, "tom");ThreadHero hero5 = new ThreadHero(14, "tom");root.left = hero1;root.right = hero2;hero1.left = hero3;hero1.right = hero4;hero2.left = hero5;ThreadBinaryTree threadBinaryTree = new ThreadBinaryTree(root);// 中序线索化二叉树threadBinaryTree.threadedNodes();// 遍历中序线索化后的二叉树threadBinaryTree.showThreadBinaryTree();}
}class ThreadBinaryTree {public ThreadHero root;public ThreadBinaryTree() {}public ThreadBinaryTree(ThreadHero root) {this.root = root;}public void threadedNodes() {threadedNodes(root);}// 记录当前结点的前驱结点ThreadHero preNode = null;// 将结点中序线索化public void threadedNodes(ThreadHero node) {if (node == null) {return;}// 向左递归，找到中序遍历的第一个结点threadedNodes(node.left);// 若该结点的左指针为空，则将其指向其前驱结点// 并且将左指针类型设置为1if (node.left == null) {node.left = preNode;node.setLeftType(1);}// 若该结点的前驱结点不为空，且前驱结点的右指针为空// 那么将前驱结点的右指针指向当前结点，并将其右指针类型设置为1if (preNode != null && preNode.right == null) {preNode.right = node;preNode.setRightType(1);}// 将当前结点转换为前驱结点，进行下一步操作。preNode = node;// 向右递归threadedNodes(node.right);}// 遍历中序线索化后的二叉树public void showThreadBinaryTree() {ThreadHero heroNode = root;while (heroNode != null) {// 向左循环，找到有前驱结点的结点，找到的第一个结点为中序遍历的第一个结点while (heroNode.getLeftType() == 0) {heroNode = heroNode.left;}// 输出该结点System.out.println(heroNode);// 若该结点有后继结点，继续输出while (heroNode.getRightType() == 1) {heroNode = heroNode.right;System.out.println(heroNode);}// 若已经没有后继结点，将当前结点转换为其右节点。heroNode = heroNode.right;}}
}class ThreadHero {public int id;public String name;public ThreadHero left;public ThreadHero right;public ThreadHero() {}public ThreadHero(int id, String name) {this.id = id;this.name = name;}// 定义左指针的属性，0为指向左子树，1为指向前驱结点private int leftType;// 定义右指针的属性，0为指向右子树，1为指向后继结点private int rightType;@Overridepublic String toString() {return "ThreadHero{" +"id=" + id +", name='" + name + '\'' +'}';}public int getRightType() {return rightType;}public void setRightType(int rightType) {this.rightType = rightType;}public int getLeftType() {return leftType;}public void setLeftType(int leftType) {this.leftType = leftType;}
}