对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。
根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
注意：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。
? ? 遍历线索化二叉树：因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。
public class ThreadedBinaryTreeDemo {
? ? public static void main(String[] args) {
? ? ? ? ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
? ? ? ? MyNode a = new MyNode("A");
? ? ? ? MyNode b = new MyNode("B");
? ? ? ? MyNode c = new MyNode("C");
? ? ? ? MyNode e = new MyNode("E");
? ? ? ? MyNode f = new MyNode("F");
? ? ? ? MyNode g = new MyNode("G");
? ? ? ? //手动创建树
? ? ? ? threadedBinaryTree.setRoot(a);
? ? ? ? a.left=b;
? ? ? ? a.right=c;
? ? ? ? b.left=e;
? ? ? ? b.right=f;
? ? ? ? c.left=g;
? ? ? ? System.out.println("未线索化前e节点的前驱节点和后驱");
? ? ? ? System.out.println("F号结点的前驱结点为："+e.left);//3
? ? ? ? System.out.println("F号结点的后继结点为："+e.right);//1
? ? ? ? System.out.println("中序线索化后e节点的前驱节点和后驱");
? ? ? ? threadedBinaryTree.infixThreadedNodes();
? ? ? ? System.out.println("F号结点的前驱结点为："+e.left);//3
? ? ? ? System.out.println("F号结点的后继结点为："+e.right);//1
? ? }
}
//定义能实现线索化的二叉树
class ThreadedBinaryTree {
? ? MyNode root;
? ? MyNode pre=null;//指向当前节点的前驱节点 ?递归过程中pre总是保留前一个节点
? ? //为了实现线索化，需要创建指向当前节点的前驱结点的指针
? ? public void setRoot(MyNode root) {
? ? ? ? this.root = root;
? ? }
? ? public void infixThreadedNodes() {
? ? ? ? this.infixThreadedNodes(root);
? ? }
? ? //编写对二叉树进行中序线索化的方法
? ? public void infixThreadedNodes(MyNode node) {
? ? ? ? if (node == null) {//节点为空 不能线索化
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? ? ? //线索化左子树
? ? ? ? ? ? infixThreadedNodes(node.left);
? ? ? ? ? ? if (node.left==null){
? ? ? ? ? ? ? ? node.left=pre;
? ? ? ? ? ? ? ? node.leftType=1;
? ? ? ? ? ? }
? ? ? ? ? ? //处理后继节点
? ? ? ? ? ? if (pre!=null && pre.right==null){
? ? ? ? ? ? ? ? pre.right=node;
? ? ? ? ? ? ? ? pre.rightType=1;
? ? ? ? ? ? }
? ? ? ? ? ? //每处理一个节点，让当前节点是下一个节点的前驱节点
? ? ? ? ? ? pre=node;
? ? ? ? ? ? //线索化右子树
? ? ? ? ? ? infixThreadedNodes(node.right);
? ? }
}
class ?MyNode{
? ? String name;
? ? MyNode left;
? ? MyNode right;
? ? //说明
? ? //1.如果leftType==0 表示指向的是左子树，为1 表示指向前驱节点
? ? //2.如果rightType==0 表示指向的是右子树，为1 表示指向后继节点
? ? int leftType;
? ? int rightType;
? ? public MyNode(String name) {
? ? ? ? this.name = name;
? ? }
? ? //重写toString方法
? ? @Override
? ? public String toString() {
? ? ? ? return "Node{" +
? ? ? ? ? ? ? ? "name='" + name + '\'' +
? ? ? ? ? ? ? ? '}';
? ? }
}运行结果：
?
