您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

線索二叉樹詳解：中序線索化構建與非遞歸遍歷完整 Java 實現

編輯：Java 綜合教學

什麼是線索二叉樹？

二叉鏈表中 N 個節點共 2N 個指針域，其中 N+1 個為空（葉節點 2 個、度 1 節點 1 個）。線索二叉樹利用這些空指針：

左指針為空 → 指向中序前驅（前驅線索）
右指針為空 → 指向中序後繼（後繼線索）

需增加兩個標誌域 ltag、rtag：0 表指向孩子，1 表指向前驅/後繼（線索）。

節點定義

private static class Node {
    int data;
    Node lchild, rchild;
    int ltag = 0, rtag = 0; // 0=孩子, 1=線索
}

一、構建完全二叉樹（輸入序列法）

輸入完全二叉樹層序序列，0 表示空節點，遞歸按下標 2*i、2*i+1 構建。

public Node build(int index) {
    if (index > n || nodes[index-1] == 0) return null;
    Node node = new Node();
    node.data = nodes[index-1];
    node.lchild = build(2 * index);
    node.rchild = build(2 * index + 1);
    return node;
}

二、中序線索化核心算法

中序遍歷過程中維護 pre 指向「剛訪問完的節點」。

private Node pre = null;

public void inThreaded() {
    inThreaded(root);
    // 處理最後一個節點：無後繼
    if (pre != null) {
        pre.rchild = null;
        pre.rtag = 1;
    }
}

private void inThreaded(Node node) {
    if (node == null) return;
    inThreaded(node.lchild);          // 1. 左子樹線索化

    // 2. 處理當前節點的前驅線索
    if (node.lchild == null) {
        node.lchild = pre;
        node.ltag = 1;
    }

    // 3. 處理前驅節點的後繼線索
    if (pre != null && pre.rchild == null) {
        pre.rchild = node;
        pre.rtag = 1;
    }

    pre = node;                       // 4. 更新 pre
    inThreaded(node.rchild);          // 5. 右子樹線索化
}

三、線索樹非遞歸遍歷（正序/逆序）

正序：找最左下 → 循環找後繼

public void inOrder(Node node) {
    Node cur = firstNode(node);
    while (cur != null) {
        System.out.print(cur.data + " ");
        cur = nextNode(cur);
    }
}

private Node firstNode(Node node) {   // 中序第一個節點 = 最左下
    while (node.ltag == 0) node = node.lchild;
    return node;
}

private Node nextNode(Node node) {    // 後繼
    if (node.rtag == 0) return firstNode(node.rchild); // 有右子樹，找右子樹最左下
    return node.rchild;                                // 直接返回後繼線索
}

逆序：找最右下 → 循環找前驅

public void inOrderReverse(Node node) {
    Node cur = lastNode(node);
    while (cur != null) {
        System.out.print(cur.data + " ");
        cur = preNode(cur);
    }
}

private Node lastNode(Node node) {    // 中序最後節點 = 最右下
    while (node.rtag == 0) node = node.rchild;
    return node;
}

private Node preNode(Node node) {     // 前驅
    if (node.ltag == 0) return lastNode(node.lchild); // 有左子樹，找左子樹最右下
    return node.lchild;                                // 直接返回前驅線索
}

四、測試驗證

public static void main(String[] args) {
    ThreadTree tree = new ThreadTree(); // 輸入: 1,2,3,0,4,0,5
    System.out.print("遞歸中序: "); tree.inOrderRecur(tree.root);
    tree.inThreaded();
    System.out.print("\n線索正序: "); tree.inOrder(tree.root);
    System.out.print("\n線索逆序: "); tree.inOrderReverse(tree.root);
}

輸出：

遞歸中序: 2 4 1 5 3
線索正序: 2 4 1 5 3
線索逆序: 3 5 1 4 2

五、複雜度與應用場景

操作	時間複雜度	空間複雜度	備註
線索化構建	O(N)	O(H) 遞歸棧	一次中序遍歷
正序/逆序遍歷	O(N)	O(1)	無棧、無遞歸，極其節省記憶體
查找前驅/後繼	O(1) 平均	O(1)	利用線索直接跳轉