Java数据结构之线索化二叉树的实现

线索化二叉树的概述

线索化二叉树（Threaded Binary Tree）是一种优化的二叉树结构。它的优点是可以在O(n)的时间复杂度内，进行中序遍历。而在普通二叉树中进行中序遍历需要的时间复杂度是O(nlogn)。线索化二叉树的原理是利用空闲的指针域，来记录中序遍历中前驱与后继结点的位置。线索化二叉树中会出现两种类型的结点，一种是有左右孩子的结点，另一种是没有左右孩子的结点。前者被称为常规结点，后者被称为线索结点（Threaded Node）。线索化二叉树可分为前序线索化二叉树、中序线索化二叉树和后序线索化二叉树。

线索化二叉树的实现

下面是线索化二叉树的Java代码实现。

定义线索化二叉树结点类

public class ThreadedNode {
    private int value; // 结点的数据
    private ThreadedNode left; // 左子结点
    private ThreadedNode right; // 右子结点
    private int leftType; // 左子结点类型：0表示左子结点，1表示指向前驱结点
    private int rightType; // 右子结点类型：0表示右子结点，1表示指向后继结点

    // 构造方法
    public ThreadedNode(int value) {
        this.value = value;
    }

    // get和set方法
    // ...
}

线索化二叉树实现类

public class ThreadedBinaryTree {
    private ThreadedNode root; // 根结点
    private ThreadedNode preNode; // 记录前驱结点的指针域

    // 构造方法
    public ThreadedBinaryTree(ThreadedNode root) {
        this.root = root;
    }

    /**
     * 中序遍历线索化二叉树
     */
    public void traverse() {
        ThreadedNode currNode = root;
        while (currNode != null) {
            // 找到最左侧的结点
            while (currNode.getLeftType() == 0) {
                currNode = currNode.getLeft();
            }
            // 访问当前结点
            System.out.print(currNode.getValue() + " ");
            // 记录前驱结点，因为到达线索结点时会用到
            ThreadedNode temp = currNode;
            // 如果当前结点的右子结点是后继结点，则遍历后继结点
            while (currNode.getRightType() == 1) {
                currNode = currNode.getRight();
                System.out.print(currNode.getValue() + " ");
            }
            // 往上跳到下一个要访问的结点
            currNode = currNode.getRight();
            // 如果当前结点是线索结点，则将该结点的right指向后继结点
            if (temp.getRight() == null) {
                temp.setRight(currNode);
                temp.setRightType(1);
            }
            // 记录前驱结点
            preNode = temp;
        }
        System.out.println();
    }

    /**
     * 线索化二叉树的中序线索化方法
     *
     * @param node 当前要处理的结点
     */
    public void threadedNodes(ThreadedNode node) {
        if (node == null) {
            return;
        }
        // 中序线索化左子树
        threadedNodes(node.getLeft());
        // 中序线索化当前结点
        if (node.getLeft() == null) {
            node.setLeft(preNode);
            node.setLeftType(1);
        }
        if (preNode != null && preNode.getRight() == null) {
            preNode.setRight(node);
            preNode.setRightType(1);
        }
        // 记录前驱结点
        preNode = node;
        // 中序线索化右子树
        threadedNodes(node.getRight());
    }
}

中序线索化二叉树的示例

下面是一个简单的示例，展示如何创建一颗中序线索化二叉树。

// 创建线索化二叉树的各个结点
ThreadedNode node1 = new ThreadedNode(1); 
ThreadedNode node2 = new ThreadedNode(2); 
ThreadedNode node3 = new ThreadedNode(3); 
ThreadedNode node4 = new ThreadedNode(4); 
ThreadedNode node5 = new ThreadedNode(5); 
ThreadedNode node6 = new ThreadedNode(6); 
ThreadedNode node7 = new ThreadedNode(7); 
// 构建线索化二叉树：1-2-4-5-3-6-7
ThreadedBinaryTree binaryTree = new ThreadedBinaryTree(node1);
node1.setLeft(node2);
node1.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
node3.setRight(node7);
// 线索化二叉树
binaryTree.threadedNodes(node1);
// 遍历线索化二叉树
binaryTree.traverse();

执行结果：

4 2 5 1 6 3 7

遍历线索化二叉树的前序和后序实现

针对前序和后序线索化二叉树的实现，可以按照上述代码实现，只需要改变根据前驱和后继结点输出结果的顺序即可。这里不再赘述。