Java數據結構之線索化二叉樹怎么實現

Java數據結構之線索化二叉樹怎么實現

線索化二叉樹（Threaded Binary Tree）是一種特殊的二叉樹，它通過利用二叉樹中的空指針域來存儲指向某種遍歷順序下的前驅或后繼節點的指針，從而實現對二叉樹的高效遍歷。本文將介紹如何在Java中實現線索化二叉樹。

1. 線索化二叉樹的基本概念

在普通的二叉樹中，每個節點有兩個指針域，分別指向左子節點和右子節點。如果某個節點沒有左子節點或右子節點，那么對應的指針域將為空。線索化二叉樹利用這些空指針域來存儲指向某種遍歷順序下的前驅或后繼節點的指針。

線索化二叉樹可以分為前序線索化、中序線索化和后序線索化三種類型，分別對應于前序遍歷、中序遍歷和后序遍歷。

2. 線索化二叉樹的節點定義

首先，我們需要定義一個節點類來表示線索化二叉樹的節點。每個節點包含數據域、左子節點指針、右子節點指針以及兩個標志位，用于指示左指針和右指針是否指向子節點或線索。

class ThreadedNode {
    int data;
    ThreadedNode left;
    ThreadedNode right;
    boolean isLeftThreaded;  // true if left pointer is a thread
    boolean isRightThreaded; // true if right pointer is a thread

    public ThreadedNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.isLeftThreaded = false;
        this.isRightThreaded = false;
    }
}

3. 中序線索化二叉樹的實現

下面我們以中序線索化二叉樹為例，介紹如何實現線索化二叉樹。

3.1 中序線索化

中序線索化的過程是在中序遍歷的過程中，將空指針域替換為指向中序遍歷順序下的前驅或后繼節點的指針。

class ThreadedBinaryTree {
    private ThreadedNode root;
    private ThreadedNode prev; // 用于記錄前一個訪問的節點

    public ThreadedBinaryTree() {
        this.root = null;
        this.prev = null;
    }

    // 中序線索化
    public void inOrderThreading() {
        inOrderThreading(root);
    }

    private void inOrderThreading(ThreadedNode node) {
        if (node == null) {
            return;
        }

        // 線索化左子樹
        inOrderThreading(node.left);

        // 處理當前節點
        if (node.left == null) {
            node.left = prev;
            node.isLeftThreaded = true;
        }

        if (prev != null && prev.right == null) {
            prev.right = node;
            prev.isRightThreaded = true;
        }

        prev = node;

        // 線索化右子樹
        inOrderThreading(node.right);
    }
}

3.2 中序遍歷線索化二叉樹

線索化后的二叉樹可以通過遍歷線索來高效地進行中序遍歷。

public void inOrderTraversal() {
    ThreadedNode current = leftMost(root);

    while (current != null) {
        System.out.print(current.data + " ");

        // 如果右指針是線索，直接跳到后繼節點
        if (current.isRightThreaded) {
            current = current.right;
        } else {
            // 否則，找到右子樹的最左節點
            current = leftMost(current.right);
        }
    }
}

private ThreadedNode leftMost(ThreadedNode node) {
    if (node == null) {
        return null;
    }

    while (node.left != null && !node.isLeftThreaded) {
        node = node.left;
    }

    return node;
}

4. 測試線索化二叉樹

我們可以通過以下代碼測試線索化二叉樹的實現：

public class Main {
    public static void main(String[] args) {
        ThreadedBinaryTree tree = new ThreadedBinaryTree();
        tree.root = new ThreadedNode(1);
        tree.root.left = new ThreadedNode(2);
        tree.root.right = new ThreadedNode(3);
        tree.root.left.left = new ThreadedNode(4);
        tree.root.left.right = new ThreadedNode(5);
        tree.root.right.left = new ThreadedNode(6);
        tree.root.right.right = new ThreadedNode(7);

        tree.inOrderThreading();
        System.out.println("In-order traversal of threaded binary tree:");
        tree.inOrderTraversal();
    }
}

輸出結果應為：

In-order traversal of threaded binary tree:
4 2 5 1 6 3 7 

5. 總結

線索化二叉樹通過利用空指針域來存儲遍歷順序下的前驅或后繼節點的指針，從而實現了對二叉樹的高效遍歷。本文介紹了如何在Java中實現中序線索化二叉樹，并提供了相應的代碼示例。通過線索化二叉樹，我們可以在不借助?；蜻f歸的情況下，高效地遍歷二叉樹。