线索二叉树(中序、先序和后序及遍历)

链式存储

线索二叉树是二叉树的一类，在看线索二叉树之前我们先看一下二叉树的链式存储。

一个二叉树的存储例子(后面用到的二叉树都是这棵)：

代码是这样的：

public class BinaryTreeNode<T>{
	private T data;							//数据域
	private BinaryTreeNode<T> leftChild;	//左指针域
	private BinaryTreeNode<T> rightChild;	//右指针域
}

上图中的“#”号空指针，会浪费一部分空间。对于二叉树的一个节点，查找其左右子女是方便的，其前驱和后继只有在遍历中得到。为了容易找到前驱和后继就会利用这部分空间保存按照某一遍历遍历出来的前驱或后继节点。

线索二叉树

我们在做遍历的时候，比如对上图中的树做中序遍历时，得到DBGEAFC字符序列,遍历过后，我们就可以知道节点E的前驱是G后继是A，节点F的前驱是A后继是C。也就是说遍历过后，我们可以很清楚的知道任意一个节点的的前驱和后继。

• 中序线索二叉树：按中序遍历。
• 先序线索二叉树：按先序遍历。
• 后序线索二叉树：按后序遍历。

这是建立在遍历过的基础上，在二叉链表上，我们只能知道每个节点指向其左右孩子节点的地址，而不知道每个节点的前驱和后继，要想知道，必须遍历一次，以后每次需要知道时，都必须先遍历一次，那得多浪费时间。我们可以考虑在创建时就记住这些前驱和后继。这个时候我们就可以考虑利用那些空地址，存放指向节点在某种遍历次序下的前驱和后继节点的地址。这种指向前驱和后继的指针称为线索，所以叫线索二叉树。总结一下：

• 若当前节点左指针域非空时，保留原指针不变；若左指针域为空时，添加该节点在相应遍历序列中前驱节点地址。
• 若当前结点右指针域非空时，保留原指针不变；若右指针域为空时，添加该节点在相应遍历序列中后继节点地址。

这里要注意一下，我们怎么判断左/右指针域指向的是原指针还是前驱/后继节点?两个布尔变量。flase表示原指针(左/右子树)，true表示前驱/后继节点。

public class CluesBinaryTreeNode<T>{
	private T data;								//数据域
	private CluesBinaryTreeNode<T> leftChild;	//左指针域
	private CluesBinaryTreeNode<T> rightChild;	//右指针域
	private boolean leftIsPriorLink;			//是否是前驱节点
	private boolean rightIsNextLink;			//是否是后继节点
}

中序线索二叉树

一个中序线索二叉树的例子(遍历是DBGEAFC)：

中序线索化实现

线索化：中序线索二叉树，就按照中序遍历，遍历的过程中在当前节点的左或右空指针域中添加前驱或后继节点。为了保留遍历过程中访问节点的前驱与后继关系，需要设置一个前一节点变量priorNode始终指向刚访问过的节点。

• 如果当前节点cur.leftChild == null(左子节点为空)，则cur.leftIsPriorLink = true;cur.leftChild = priorNode;(左指针域指向前驱节点，修改leftIsPriorLink为线索模式即true)。
• 如果前一节点priorNode.rightChild == null(右子结点为空)，则priorNode.rightIsNextLink = true;priorNode.rightChild = cur;(右指针域指向后继节点，修改rightIsNextLink为线索模式即true)。

    public void inorderClues(TreeNode<T> tree){
        if (tree == null){
            return;
        }

        inorderClues(tree.leftChild);           //左节点

        if (tree.leftChild == null){            //根节点
            tree.leftIsPriorLink = true;
            tree.leftChild = priorNode;
        }
        if (priorNode != null && priorNode.rightChild == null){
            priorNode.rightIsNextLink = true;
            priorNode.rightChild = tree;
        }

        priorNode = tree;
        inorderClues(tree.rightChild);          //右节点
    }

注：priorNode是类的成员变量，完整代码在后面。

实现的代码过程

省略了一些无关紧要的代码

中序线索二叉树的遍历

分两步，①获取中序遍历的首节点。②获取中序线索化二叉树中当前节点的后继节点。只要完成这两步就可以遍历中序线索化二叉树。

• 获取中序遍历的首节点：从根节点开始沿着左指针不断向左下搜索，直到找到最左的节点。最左的节点指该节点左指针为空。
• 获取中序线索化二叉树中当前节点的后继节点：有两种情况
  ①当前节点存在右子树：则从该右子树根节点开始不断向左下搜索，找到找到最左的节点。该节点即当前节点的后继。
  ②当前节点不存在右子树：则其后继节点即为其右指针域中后继线索所指节点。
  下面是步骤图，可以边看代码边看此图：
  

遍历代码

public void inorderTraversal(TreeNode<T> tree){
        if (tree == null){return;}

        TreeNode<T> node = tree.leftChild;

        if (node == null){ return;}

        while (node.leftChild != null && !node.leftIsPriorLink){        //循环到最左节点
            node = node.leftChild;
        }

        while (node != null){
            System.out.print(node.data);
            if (node.rightChild != null && !node.rightIsNextLink){      //当前节点存在右子树
                node = node.rightChild;
                while (node.leftChild != null && !node.leftIsPriorLink){    //循环到最左节点
                    node = node.leftChild;
                }
            }else{
                node = node.rightChild;                                 //后继线索所指节点
            }
        }
    }

中序线索二叉树可运行代码

public class CluesBinaryTreeNode<T>{

    private TreeNode priorNode;

    private class TreeNode<T>{
        private T data;								//数据域
        private TreeNode<T> leftChild;				//左指针域
        private TreeNode<T> rightChild;				//右指针域
        private boolean leftIsPriorLink;			//是否是前驱节点
        private boolean rightIsNextLink;			//是否是后继节点

        public TreeNode(){}
        public TreeNode(T data){this.data=data;}

    }

    /**
     * 递归，中序创建线索二叉树
     * @param tree 树根
     */
    public void inorderClues(TreeNode<T> tree){
        if (tree == null){
            return;
        }

        inorderClues(tree.leftChild);           //左节点

        if (tree.leftChild == null){            //根节点
            tree.leftIsPriorLink = true;
            tree.leftChild = priorNode;
        }
        if (priorNode != null && priorNode.rightChild == null){
            priorNode.rightIsNextLink = true;
            priorNode.rightChild = tree;
        }

        priorNode = tree;
        inorderClues(tree.rightChild);          //右节点
    }

    /**
     * 中序线索化二叉树的遍历
     * @param tree
     */
    public void inorderTraversal(TreeNode<T> tree){
        if (tree == null){return;}

        TreeNode<T> node = tree.leftChild;

        if (node == null){ return;}

        while (node.leftChild != null && !node.leftIsPriorLink){        //循环到最左节点
            node = node.leftChild;
        }

        while (node != null){
            System.out.print(node.data);
            if (node.rightChild != null && !node.rightIsNextLink){      //当前节点存在右子树
                node = node.rightChild;
                while (node.leftChild != null && !node.leftIsPriorLink){    //循环到最左节点
                    node = node.leftChild;
                }
            }else{
                node = node.rightChild;                                 //后继线索所指节点
            }
        }
    }

    public static void main(String[] args) {
       CluesBinaryTreeNode<String> cluesTree = new CluesBinaryTreeNode<String>();
        CluesBinaryTreeNode.TreeNode rootNode = cluesTree.new TreeNode<>();

        rootNode.data = "A";
        
        rootNode.leftChild=cluesTree.new TreeNode<>("B");
        rootNode.rightChild=cluesTree.new TreeNode<>("C");
        
        rootNode.leftChild.leftChild=cluesTree.new TreeNode<>("D");
        rootNode.rightChild.leftChild=cluesTree.new TreeNode<>("F");
        rootNode.leftChild.rightChild=cluesTree.new TreeNode<>("E");
        
        rootNode.leftChild.rightChild.leftChild=cluesTree.new TreeNode<>("G");

       	cluesTree.inorderClues(rootNode);                           //中序线索化二叉树
        cluesTree.inorderTraversal(rootNode);                       //遍历中序线索化二叉树
    }
}

运行结果(这棵二叉树就是上面图中的二叉树)：

先序线索二叉树

一个先序线索二叉树的例子(遍历是ABDEGCF)：

先序线索化实现

线索化：和中序线索化实现一样(把中序遍历改为先序遍历)。
因为遍历的顺序不一样，所以需要注意的先序和中序有个地方不一样，先序我们要判断是否是左子树/右子树在进行递归，不然会出现死递归。

• 判断是否是左子树(即不能是前驱节点)：先序的遍历顺序是"根左右"，在对"左"节点进行遍历的时候当"左"节点没有左子树时，“左"节点的前驱节点就设置为"根"节点，此时在遍历”左“节点的"左"节点，就又会遍历"根节点”，就会形成死循环。如上图中的D.leftChild是前驱节点不是左子树，如果不判断就会在像B和D节点这种节点上死循环根左根左根左…，BDBDBD…。
• 判断是否是右子树(即不能是后驱节点)：在previousClues(E)中遍历E.leftChild(G节点)节点时即previousClues(G)，此时priorNode=E不为空有priorNode.rightChild=G(E.rightChild=G)，priorNode=G。然后回到previousClues(E)方法中如果不判断就会进入previousClues(G)中，此时priorNode=G不为空有priorNode.rightChild=G(G.rightChild=G)。就会形成死循环GGGGG…。

 public void previousClues(TreeNode<T> tree){
        if (tree == null){
            return;
        }
        if (tree.leftChild == null){            //根节点
            tree.leftIsPriorLink = true;
            tree.leftChild = priorNode;
        }
        if (priorNode != null && priorNode.rightChild == null){
            priorNode.rightIsNextLink = true;
            priorNode.rightChild = tree;
        }
        priorNode = tree;

        if (!tree.leftIsPriorLink){             //判断是否有左子树
            previousClues(tree.leftChild);
        }
        if (!tree.rightIsNextLink){             //判断是否有右子树
            previousClues(tree.rightChild);
        }
    }

先序线索二叉树的遍历

先序线索二叉树的遍历就简单了，让我们看一下下面这个先序线索二叉树的遍历。ABDEGCF。从根节点一直遍历到最左节点(根节点没有左节点的话，根节点就是"最左节点")，最左节点的右节点(右子树或后继节点)就是下一个要遍历的节点，一直重复这个步骤，先序线索二叉树的遍历就完成了。

遍历代码

 public void previousTraversal(TreeNode<T> tree){
        while (tree != null){
            System.out.print(tree.data);
            if (tree.leftChild != null && !tree.leftIsPriorLink){   //左子树
                tree = tree.leftChild;
            }else {
                tree = tree.rightChild;                             //右子树或者后继节点
            }
        }
    }

先序线索二叉树可运行代码

/**
 * 先序线索二叉树
 * @param <T>
 */
public class CluesBinaryTreeNode<T>{

    private TreeNode priorNode;

    private class TreeNode<T>{
        private T data;								//数据域
        private TreeNode<T> leftChild;				//左指针域
        private TreeNode<T> rightChild;				//右指针域
        private boolean leftIsPriorLink;			//是否是前驱节点
        private boolean rightIsNextLink;			//是否是后继节点

        public TreeNode(){}
        public TreeNode(T data){this.data=data;}

    }

    /**
     * 递归，先序创建线索二叉树
     * @param tree 树根
     */
    public void previousClues(TreeNode<T> tree){
        if (tree == null){
            return;
        }
        if (tree.leftChild == null){            //根节点
            tree.leftIsPriorLink = true;
            tree.leftChild = priorNode;
        }
        if (priorNode != null && priorNode.rightChild == null){
            priorNode.rightIsNextLink = true;
            priorNode.rightChild = tree;
        }
        priorNode = tree;

        if (!tree.leftIsPriorLink){             //判断是否有左子树
            previousClues(tree.leftChild);
        }
        if (!tree.rightIsNextLink){             //判断是否有右子树
            previousClues(tree.rightChild);
        }
    }

    /**
     * 先序线索化二叉树的遍历
     * @param tree
     */
    public void previousTraversal(TreeNode<T> tree){
        while (tree != null){
            System.out.print(tree.data);
            if (tree.leftChild != null && !tree.leftIsPriorLink){   //左子树
                tree = tree.leftChild;
            }else {
                tree = tree.rightChild;                             //右子树或者后继节点
            }
        }
    }

    public static void main(String[] args) {
        CluesBinaryTreeNode<String> cluesTree = new CluesBinaryTreeNode<String>();
        CluesBinaryTreeNode.TreeNode rootNode = cluesTree.new TreeNode<>();

        rootNode.data = "A";

        rootNode.leftChild=cluesTree.new TreeNode<>("B");
        rootNode.rightChild=cluesTree.new TreeNode<>("C");

        rootNode.leftChild.leftChild=cluesTree.new TreeNode<>("D");
        rootNode.rightChild.leftChild=cluesTree.new TreeNode<>("F");
        rootNode.leftChild.rightChild=cluesTree.new TreeNode<>("E");

        rootNode.leftChild.rightChild.leftChild=cluesTree.new TreeNode<>("G");

        cluesTree.previousClues(rootNode);                              //中序线索化二叉树
        cluesTree.previousTraversal(rootNode);                       //遍历中序线索化二叉树
    }
}

运行结果(这棵二叉树就是上面图中的二叉树)：

后序线索二叉树

后序的遍历顺序是：左右根，根是最后遍历的，我们遍历孩子节点要回到根节点只能在树节点中多加一个指针指向父结点。

public class CluesBinaryTreeNode<T>{
	private T data;								//数据域
	private CluesBinaryTreeNode<T> leftChild;	//左指针域
	private CluesBinaryTreeNode<T> rightChild;	//右指针域
	private CluesBinaryTreeNode<T> parent;		//父指针域
	private boolean leftIsPriorLink;			//是否是前驱节点
	private boolean rightIsNextLink;			//是否是后继节点
}

一个后序线索二叉树例子(遍历是DGEBFCA，父指针域就不表示出来了)：

后序线索化实现

线索化：和中序线索化实现一样(把中序遍历改为后序遍历)。

public void afterClues(TreeNode<T> tree){
        if (tree == null){
            return;
        }

        afterClues(tree.leftChild);
        afterClues(tree.rightChild);

        if (tree.leftChild == null){            //根节点
            tree.leftIsPriorLink = true;
            tree.leftChild = priorNode;
        }
        if (priorNode != null && priorNode.rightChild == null){
            priorNode.rightIsNextLink = true;
            priorNode.rightChild = tree;
        }
        priorNode = tree;
    }

后序线索二叉树的遍历

• 遍历的起点：根节点左子树最左边的节点。该节点不一定是第一个打印数据的节点，该节点可能存在右子树，存在右子树要遍历右子树。
• 后继：一直遍历该节点的后继节点，没有后继节点就判断是不是根节点(根节点没有右子树时就会出现这种情况)。如果不是根节点，那就找到节点的父亲，一直到找到根节点，继续判断根节点是不是存在右子树。
  下面是步骤图，可以边看代码边看此图：
  

遍历代码

public void afterTraversal(TreeNode<T> tree){
        if (tree == null){
            return;
        }

        TreeNode<T> node = tree;

        TreeNode<T> prevNode = null;

        while (node != null){
            while (node.leftChild != null && !node.leftIsPriorLink){        //循环到最左节点
                node = node.leftChild;
            }

            while (node != null && node.rightIsNextLink){                   //循环后继节点
                System.out.print(node.data);
                prevNode = node;
                node = node.rightChild;
            }

            if (node == tree){
                System.out.println(node.data);
                return;
            }

            while (node != null && node.rightChild == prevNode){    //判断到根节点
                System.out.print(node.data);
                prevNode = node;
                node = node.parent;                     //回到父节点
            }

            if (node !=null && !node.rightIsNextLink){  //
                node = node.rightChild;
            }
        }
    }

后序线索二叉树可运行代码

/**
 * 后序线索二叉树
 * @param <T>
 */
public class CluesBinaryTreeNode<T>{

    private TreeNode priorNode;

    private class TreeNode<T>{
        private T data;								//数据域
        private TreeNode<T> leftChild;				//左指针域
        private TreeNode<T> rightChild;				//右指针域
        private TreeNode<T> parent;     			//父指针域
        private boolean leftIsPriorLink;			//是否是前驱节点
        private boolean rightIsNextLink;			//是否是后继节点

        public TreeNode(){}
        public TreeNode(T data){this.data=data;}

    }

    /**
     * 递归，后序创建线索二叉树
     * @param tree 树根
     */
    public void afterClues(TreeNode<T> tree){
        if (tree == null){
            return;
        }

        afterClues(tree.leftChild);           //左节点
        afterClues(tree.rightChild);          //右节点

        if (tree.leftChild == null){            //根节点
            tree.leftIsPriorLink = true;
            tree.leftChild = priorNode;
        }
        if (priorNode != null && priorNode.rightChild == null){
            priorNode.rightIsNextLink = true;
            priorNode.rightChild = tree;
        }

        priorNode = tree;
    }

    /**
     * 后序线索化二叉树的遍历
     * @param tree
     */
    public void afterTraversal(TreeNode<T> tree){
        if (tree == null){
            return;
        }

        TreeNode<T> node = tree;

        TreeNode<T> prevNode = null;

        while (node != null){
            while (node.leftChild != null && !node.leftIsPriorLink){        //循环到最左节点
                node = node.leftChild;
            }

            while (node != null && node.rightIsNextLink){                   //循环后继节点
                System.out.print(node.data);
                prevNode = node;
                node = node.rightChild;
            }

            if (node == tree){
                System.out.println(node.data);
                return;
            }

            while (node != null && node.rightChild == prevNode){    //判断到根节点
                System.out.print(node.data);
                prevNode = node;
                node = node.parent;                     //回到父节点
            }

            if (node !=null && !node.rightIsNextLink){  //
                node = node.rightChild;
            }
        }
    }

    public static void main(String[] args) {
        CluesBinaryTreeNode<String> cluesTree = new CluesBinaryTreeNode<String>();
        CluesBinaryTreeNode.TreeNode rootNode = cluesTree.new TreeNode<>();

        rootNode.data = "A";

        rootNode.leftChild=cluesTree.new TreeNode<>("B");
        rootNode.leftChild.parent=rootNode;
        rootNode.rightChild=cluesTree.new TreeNode<>("C");
        rootNode.rightChild.parent=rootNode;

        rootNode.leftChild.leftChild=cluesTree.new TreeNode<>("D");
        rootNode.leftChild.leftChild.parent=rootNode.leftChild;

        rootNode.rightChild.leftChild=cluesTree.new TreeNode<>("F");
        rootNode.rightChild.leftChild.parent=rootNode.rightChild;
        rootNode.leftChild.rightChild=cluesTree.new TreeNode<>("E");
        rootNode.leftChild.rightChild.parent=rootNode.leftChild;
//
        rootNode.leftChild.rightChild.leftChild=cluesTree.new TreeNode<>("G");
        rootNode.leftChild.rightChild.leftChild.parent=rootNode.leftChild.rightChild;


        cluesTree.afterClues(rootNode);                              //后序线索化二叉树
        cluesTree.afterTraversal(rootNode);                       //遍历后序线索化二叉树
    }
}

运行结果(这棵二叉树就是上面图中的二叉树)：