一、线索化二叉树的原理

在前面介绍二叉树的文章中提到，二叉树可以使用两种存储结构：顺序存储和链式存储，在使用链式存储时，会存在大量的空指针域，n个节点的二叉链表中含有n+1[ 2n-(n-1)=n+1 ]个空指针域，为了可以充分利用这些空指针域，引申出了线索化二叉树，将这些空指针域利用起来，提高检索效率。

上图中，紫色区域就是没有指向的空指针域，从存储空间的角度来看，这些空指针域浪费了内存资源。

从另外的角度思考，如果需要知道C节点的前驱节点和后继节点，每次都都需要进行一次遍历，是否可以提前存储C节点的前驱节点和后继节点从而省去遍历的操作从而提高效率呢？

综合以上分析，可以通过充分利用二叉链表中的空指针域，存入节点在某种遍历方式下的前驱和后继节点的指针。

这种指向前驱和后继的指针成为线索，加上线索的二叉链成为线索链表，而对应的二叉树就称为线索化二叉树（Threaded Binary Tree）

二、构建线索化二叉树

• 先对二叉树进行中序遍历（不了解二叉树遍历的可以参考数据结构：二叉树），将所有节点右指针为空的指针域指针它的后继节点，如下图：

通过中序遍历到D节点，得到了D节点right指针为空，并且D节点后继节点为B，于是将D的right节点指向B节点（如上图中的①操作），而B节点right指针也为空，于是将right指针指向A节点（如上图中的②操作），以此类推，到F节点的后继节点为Null，则F的right指针指向Null。

• 接下来将这颗二叉树所有左指针为空的指针指向它的前驱节点，如下图：

如上图，D节点的left指针域指向Null（第⑤部操作），E节点的前驱节点是A，将E的left指针指向A节点，以此类推，F节点的left节点指向C节点。

• 通过上述两步操作完成了整个二叉树的线索化。

通过线索化后，可以看出（蓝色箭头表示前驱，粉色箭头表示后继）线索化二叉树相当于是把二叉树转换成一个特殊的双向链表，这样对新增、删除以及查找节点都带来了方便，提高了效率，转换为链表后的图示如下：

线索化需要对节点的结构进行修改，修改之后的数据结构如下：

class Node
{
    private int num;
    private Object data;	//数据域
    private Node left;		//左指针域
    private Node right;		//右指针域

    /** * leftType == 0表示指向的是左子树,如果是1表示指向前驱节点 */
    private int leftType;
    
    /** * rightType == 0表示指向的是右子树,如果是1表示指向后继节点 */
    private int rightType;
}

三、代码实现线索二叉树

• 节点结构

class Node
{
    private int num;
    private Object data;
    private Node left;
    private Node right;

    /** * leftType == 0表示指向的是左子树,如果是1表示指向前驱节点 */
    private int leftType;

    /** * rightType == 0表示指向的是右子树,如果是1表示指向后继节点 */
    private int rightType;

    public Node(int num, Object data)
    {
        this.num = num;
        this.data = data;
    }

    /** * 前序遍历 */
    public void preOrder()
    {
        //先输出父节点信息
        System.out.println(this);
        //判断此节点的左节点是否为空
        //如果左节点不为空并且指针类型不是前驱类型
        if (this.left != null && this.leftType != 1)
        {
            //向左前序遍历
            this.left.preOrder();
        }
        //判断此节点的右节点是否为空
        //如果右节点不为空并且指针类型不是后继类型
        if (this.right != null && this.rightType != 1)
        {
            //向右前序遍历
            this.right.preOrder();
        }
    }

    /** * 中序遍历线索化二叉树 */
    public void infixOrder()
    {
        //判断此节点的左节点是否为空
        if (this.left != null && this.leftType != 1)
        {
            //向左中序遍历
            this.left.infixOrder();
        }
        //输出父节点信息
        System.out.println(this);
        //判断此节点的右节点是否为空
        if (this.right != null && this.rightType != 1)
        {
            //向右中序遍历
            this.right.infixOrder();
        }
    }

    /** * 后序遍历 */
    public void postOrder()
    {
        //判断此节点的左节点是否为空
        if (this.left != null && this.leftType != 1)
        {
            //向左后序遍历
            this.left.postOrder();
        }
        //判断此节点的右节点是否为空
        if (this.right != null && this.rightType != 1)
        {
            //向右后序遍历
            this.right.postOrder();
        }
        //输出父节点信息
        System.out.println(this);
    }
	
    //get set方法省略
    
    @Override
    public String toString()
    {
        return "Node{" +
                "num=" + num +
                ", data=" + data +
                '}';
    }
}

• 线索化二叉树结构

/** * 定义ThreadedBinaryTree 实现了线索化功能的二叉树 */
class ThreadedBinaryTree
{
    /** * 根节点 */
    private Node root;

    /** * 为了实现线索化,需要创建要指向当前节点的前驱节点的指针 * 在递归进行线索化时,pre总是保留前一个节点 */
    private Node pre = null;

    public void setRoot(Node root)
    {
        this.root = root;
    }

    public void createBinaryTree(ArrayList<Node> list)
    {
        this.createBinaryTree(list,0);
    }

    /** * 创建二叉树 * @param list 节点列表 * @param index 用于创建的索引 * @return */
    private Node createBinaryTree(ArrayList<Node> list, int index)
    {
        Node node = null;

        if (isEmpty())
        {
            setRoot(list.get(0));
        }

        if (index < list.size())
        {
            node = list.get(index);
            node.setLeft(createBinaryTree(list, (2*index+1)));
            node.setRight(createBinaryTree(list, (2*index+2)));
        }
        return node;
    }

    public boolean isEmpty()
    {
        return root == null;
    }

    public void preThreadNodes()
    {
        this.preThreadNodes(root);
    }

    public void infixThreadNodes()
    {
        this.infixThreadNodes(root);
    }

    public void postThreadNodes()
    {
        this.postThreadNodes(root);
    }

    /** * 前序线索化二叉树 * @param node 当前需要线索化的节点 */
    private void preThreadNodes(Node node)
    {
        //递归回溯条件
        if (node == null)
        {
            return;
        }

        //遍历到叶子节点(前驱指针未利用)
        if (node.getLeft() == null)
        {
            node.setLeft(pre);
            node.setLeftType(1);
        }

        //pre.getLeft() != node 一定不可少
        //否则在第一次回溯后到父节点后,如果不加上此判断会让pre节点后驱指针指向该父节点
        //此时pre的前驱后继节点均指向该父节点,必然会发生死循环无法结束递归
        if (pre != null && pre.getRight() == null && pre.getLeft() != node)
        {
            pre.setRight(node);
            pre.setRightType(1);
        }

        pre = node;

        if (node.getLeftType() == 0)
        {
            preThreadNodes(node.getLeft());
        }

        preThreadNodes(node.getRight());
    }

    /** * 中序线索化二叉树 * @param node 当前需要线索化的节点 */
    private void infixThreadNodes(Node node)
    {
        if (node == null)
        {
            return;
        }
        //1.递归线索化左子树
        infixThreadNodes(node.getLeft());

        //2.线索化当前节点
        //处理当前节点的前驱节点
        if (node.getLeft() == null)
        {
            //让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点的左指针的类型
            node.setLeftType(1);
        }
        //处理后继节点
        if (pre != null && pre.getRight() == null)
        {
            //让前驱节点的右指针指向当前节点
            pre.setRight(node);
            //修改前驱节点的右指针类型
            pre.setRightType(1);
        }

        //每处理一个节点之后让当前节点是下一个节点的前驱节点
        pre = node;

        //3.递归线索化右子树
        infixThreadNodes(node.getRight());
    }

    /** * 后序线索化二叉树 * @param node 当前需要线索化的节点 */
    private void postThreadNodes(Node node)
    {
        if (node == null)
        {
            return;
        }

        postThreadNodes(node.getLeft());
        postThreadNodes(node.getRight());

        if (node.getLeft() == null)
        {
            node.setLeft(pre);
            node.setLeftType(1);
        }

        if ( pre!= null && pre.getRight() == null )
        {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
    }


    /** * 非递归方式中序遍历线索化二叉树的方法 */
    public void threadedInfixList()
    {
        Node node = root;
        while (node != null)
        {
            //循环地找到leftType == 1的节点
            while (node.getLeftType() == 0)
            {
                node = node.getLeft();
            }

            System.out.println(node);

            while (node.getRightType() == 1)
            {
                node = node.getRight();
                System.out.println(node);
            }

            node = node.getRight();
        }
    }

    public void threadedTreePreList()
    {
        if (root != null)
        {
            root.preOrder();
        }else
        {
            System.out.println("二叉树为空,无法遍历");
        }
    }

    public void threadedTreeInfixList()
    {
        if (root != null)
        {
            root.infixOrder();
        }else
        {
            System.out.println("二叉树为空,无法遍历");
        }
    }

    public void threadedTreePostList()
    {
        if (root != null)
        {
            root.postOrder();
        }else
        {
            System.out.println("二叉树为空,无法遍历");
        }
    }
}

以上。

如有不足或者错误欢迎评论指正。

整理不易，留个三连再走吧！