線索二叉樹能線性地遍歷二叉樹，從而比遞歸的中序遍歷更快。使用線索二叉樹也能夠方便的找到一個節(jié)點的父節(jié)點，這比顯式地使用父親節(jié)點指針或者棧效率更高。這在?？臻g有限，或者無法使用存儲父節(jié)點的棧時很有作用（對于通過深度優(yōu)先搜索來查找父節(jié)點而言)。

那線索僅僅是這樣嗎？當然不，我們都是懶的，能等待解決的問題，為什么會去想新的辦法。我們要解決的是:

為了解決無法直接找到該結點在某種遍歷序列中的前驅和后繼結點的問題
但是同時出現了二叉鏈表找左、右孩子困難的問題，即在構建線索二叉樹之后，鏈表的原來遍歷方式會出問題。

最后看一下什么線索二叉樹的圖解

在我們的線索二叉樹的書上，基本上都有以下這張圖：

線索二叉樹

大家看到上面這張圖還是有點懵的叭，我們一起看一下我下面手畫的圖

怎么去把二叉樹線索化

哦！在著之前獻給大家提一下，二叉樹的遍歷方式，有這樣的幾種

前序遍歷二叉樹的遞歸定義(根左右)
中序遍歷二叉樹的遞歸定義(左根右)
后續(xù)遍歷二叉樹的遞歸意義(左右根)

本博文主要討論的是中序遍歷
它的中序遍歷結果就是ABCDE F GHI

中序遍歷

它的中序線索二叉樹遍歷如下

先畫線索二叉樹

在這里插入圖片描述

虛線箭頭為線索指針，對于所有左指針指向空的節(jié)點：將該節(jié)點的左指針指向該節(jié)點在中序遍歷中的上一節(jié)點；對于所有右指針指向空的節(jié)點，將該節(jié)點的右指針指向該節(jié)點在中序遍歷中的下一結點。最后一個末尾結點除外。
中序圖解線索二叉樹

線索二叉樹

怎么通過線索二叉樹查找某個數的后繼結點

即形成了一個特殊的雙向鏈表，之所以特殊，以F–>E為例，F–>E并不是直接到達，而是通過F–>B–>D–>E間接到達。

我們嘗試用Java去構建一顆線索二叉樹叭

先申明，我從未使用Java構建過樹，二叉樹都沒有，若有錯誤，請指出

數據結點類

package com.testtree;

/**
 * @author pier
 */
public class TreeNode {
    /**數據域**/
    private int data;
    /**左指針**/
    private TreeNode left;
    /** 左孩子是否為線索，采用布爾類型主要是判斷是否未null足以**/
    private boolean leftIsThread;
    /**右指針**/
    private TreeNode right;
    /** 右孩子是否為線索**/
    private boolean rightIsThread;

    /**根據數據域來確定所在的指針對應位置**/
    public TreeNode(int data)
    {
        this.data = data;
        this.left = null;
        this.leftIsThread = false;
        this.right = null;
        this.rightIsThread = false;
    }

    public int getData()
    {
        return data;
    }

    public void setData(int data)
    {
        this.data = data;
    }

    public TreeNode getLeft()
    {
        return left;
    }

    public void setLeft(TreeNode left)
    {
        this.left = left;
    }

    public boolean isLeftIsThread()
    {
        return leftIsThread;
    }

    public void setLeftIsThread(boolean leftIsThread)
    {
        this.leftIsThread = leftIsThread;
    }

    public TreeNode getRight()
    {
        return right;
    }

    public void setRight(TreeNode right)
    {
        this.right = right;
    }

    public boolean isRightIsThread()
    {
        return rightIsThread;
    }

    public void setRightIsThread(boolean rightIsThread)
    {
        this.rightIsThread = rightIsThread;
    }

    @Override
    public boolean equals(Object obj)
    {
        if (obj instanceof TreeNode )
        {
            TreeNode temp = (TreeNode) obj;
            if (temp.getData() == this.data)
            {
                return true;
            }
        }
        return false;
    }

    @Override
    public int hashCode()
    {
        return super.hashCode() + this.data;
    }
}

二叉樹類

package com.testtree;
/*author:pier
2021/10/12
*/

public class BiTree {
    /** 根節(jié)點 **/
    private TreeNode root;
    /** 大小 **/
    private int size;
    /** 線索化的時候保存前驅 **/
    private TreeNode pre = null;

    public BiTree()
    {
        this.root = null;
        this.size = 0;
        this.pre = null;
    }

    public BiTree(int[] data)
    {
        this.pre = null;
        this.size = data.length;
        // 創(chuàng)建二叉樹
        this.root = createTree(data, 1);
    }

    /**
     * 創(chuàng)建二叉樹
     *
     */
    public TreeNode createTree(int[] data, int index)
    {
        if (index > data.length)
        {
            return null;
        }
        TreeNode node = new TreeNode(data[index - 1]);
        TreeNode left = createTree(data, 2 * index);
        TreeNode right = createTree(data, 2 * index + 1);
        node.setLeft(left);
        node.setRight(right);
        return node;
    }
    /**中序遍歷**/
    public void inList(TreeNode root)
    {
        if (root != null)
        {
            inList(root.getLeft());
            System.out.print(root.getData() + ",");
            inList(root.getRight());
        }
    }

    public TreeNode getRoot()
    {
        return root;
    }

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

    public int getSize()
    {
        return size;
    }

    public void setSize(int size)
    {
        this.size = size;
    }
    /**線索化二叉樹**/
    public void inThread(TreeNode root) {
        if ( root != null ) {
            // 線索化左孩子
            inThread(root.getLeft());
            // 左孩子為空
            if ( null == root.getLeft() )
            {
                // 將左孩子設置為線索
                root.setLeftIsThread(true);
                root.setLeft(pre);
            }
            // 右孩子為空
            if ( pre != null && null == pre.getRight() )
            {
                pre.setRightIsThread(true);
                pre.setRight(root);
            }
            pre = root;
            // 線索化右孩子
            inThread(root.getRight());
        }
    }
    /**
     * 中序遍歷線索二叉樹
     *
     */
    public void inThreadList(TreeNode root)
    {
        if (root != null)
        {
            // 如果左孩子不是線索
            while (root != null && !root.isLeftIsThread())
            {
                root = root.getLeft();
            }

            do
            {
                // 如果右孩子是線索
                System.out.print(root.getData() + ",");
                if (root.isRightIsThread())
                {
                    root = root.getRight();
                }
                // 有右孩子
                else
                {
                    root = root.getRight();
                    while (root != null && !root.isLeftIsThread())
                    {
                        root = root.getLeft();
                    }
                }
            } while (root != null);
        }
    }
}

測試類

package com.testtree;

/**
 * @author pier
 */
public class Test {
    public static void main(String[] args) {
    //不要問我為什么設置這么大，結尾看我效果截圖
        int[] arr = new int[10000];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=i+1;
        }
        //創(chuàng)建一顆二叉樹
        BiTree biTree = new BiTree(arr);
        //中序遍歷二叉樹
        System.out.println("中序遍歷結果如下:");
        long start1 = System.currentTimeMillis();
        biTree.inList(biTree.getRoot());
        long end1 = System.currentTimeMillis();
        System.out.println();
        System.out.println("普通遍歷時間為:"+(end1-start1)+"毫秒");
        System.out.println("\n");
        //中序遍歷將二叉樹線索化
        biTree.inThread(biTree.getRoot());
        System.out.println("線索二叉樹中序遍歷如下:");
        long start2 = System.currentTimeMillis();
        biTree.inThreadList(biTree.getRoot());
        long end2 = System.currentTimeMillis();
        System.out.println();
        System.out.println("線索二叉樹的遍歷時間為:"+(end2-start2)+"毫秒");

    }
}

運行結果