本文共 1695 字，大约阅读时间需要 5 分钟。

一、线索二叉树的概念

在二叉树的链式存储结构中，增加指向前趋和后续结点的信息，称为线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序进行遍历使其成为线索二叉树的过程称为线索化。

线索二叉树的每个结点包含五个域：data、left、right、leftIsThread和rightIsThread。左孩子域left指向左孩子结点，若无左孩子则指向前趋结点；右孩子域right指向右孩子结点，若无右孩子则指向后续结点。为了区分左孩子和右孩子的不同，需借助leftIsThread和rightIsThread两个标志域来标注。

二、线索化二叉树

在二叉树中，线索化的核心是通过递归方式为每个结点设置前趋和后续信息。具体步骤如下：

线索化的实现依赖于头结点的存在。头结点的data域为空，left域指向根结点，leftIsThread为0，rightIsThread为1。

三、遍历线索化二叉树

中序遍历线索化二叉树的算法思想如下：

以下是实现代码：

public class BinThrTree {
    char data;
    boolean leftIsThread;
    BinThrTree left;
    boolean rightIsThread;
    BinThrTree right;
    public BinThrTree(char data) {
        this.data = data;
        leftIsThread = false;
        left = null;
        rightIsThread = false;
        right = null;
    }
    public static void inThread(BinThrTree root) {
        if (root != null) {
            inThread(root.left);
            if (root.left == null) {
                root.leftIsThread = true;
                root.left = pre;
            }
            if (pre != null && pre.right == null) {
                pre.rightIsThread = true;
                pre.right = root;
            }
            pre = root;
            inThread(root.right);
        }
    }
    public static void main(String[] args) {
        BinThrTree root = new BinThrTree('A');
        root.left = new BinThrTree('B');
        root.right = new BinThrTree('C');
        BinThrTree b = root.right;
        b.left = new BinThrTree('E');
        b.right = new BinThrTree('F');
        inThread(root);
    }
}

通过上述代码，可以实现二叉树的中序线索化，输出结果如下：

A < - B < - C < - E < - F