線索二元樹(Threaded Binary Tree)

一個二元樹通過線索連起來。所有原本為空的右(孩子)指針改為指向該節點在中序序列中的後繼，所有原本為空的左(孩子)指針改為指向該節點的中序序列的前驅。

假設該二元樹中序遍歷為 A B C D E F G H I，根據上述說明試著解讀為何這些節點的線索是這樣連的。

A 節點的左指針為空，因此指向其中序的前驅節點為 B，右指針要指向後繼，但它是第一個遍歷所以為空；C 節點的左指針指向前驅 B，右指針指向後繼 D…以此類推。

• 線索二元樹能線性地遍歷二元樹，從而比遞迴的中序遍歷更快，並且建立線索並不影響時間複雜度。
• 使用線索二元樹也能夠方便的找到一個節點的父節點，這比多宣告一個父親節點指針來找 或者用 棧 效率更高。
• 這在棧空間有限、無法使用存儲父節點的棧時很有作用(對於通過深度優先搜索DFS來搜尋父節點而言)。

因此，當使用線索二元樹時，Node節點的left和right屬性有以下情況需要考慮：

1. left 指向的是左子樹，也可能是指向前驅節點。
2. right 指向的是右子樹，也可能是指向後繼節點。

簡易實現

試著找出 10 的前驅和後繼節點為何？

首先我們需要在節點類中宣告兩個變數，用於將左指針右指針分類，並加上get和set方法。

// 1. 如果 leftType = 0 表示指向左子樹 , leftType = 1 表示指向前驅節點
// 2. 如果 rightType = 0 表示指向右子樹 , rightType = 1 表示指向後繼節點
private int leftType;
private int rightType;

public int getLeftType() {
    return leftType;
}

public void setLeftType(int leftType) {
    this.leftType = leftType;
}

public int getRightType() {
    return rightType;
}

public void setRightType(int rightType) {
    this.rightType = rightType;
}

接著需要在樹類宣告一個 prev 節點用於指向當前節點的前驅節點

private TreeNode prev = null;

線索化的方法

// 重載threadedNodes方法
public void threadedNodes() {
    this.threadedNodes(root);
}
/**
 * 
 * @param node 當前需要線索化的節點
 */
//對二元樹進行中序線索化的方法
public void threadedNodes(TreeNode node) {
    if(node == null) {
        return;
    }

    // 1. 先線索化左子樹
    threadedNodes(node.getLeft());
    // 2. 線索化當前節點
    // 處理當前節點的前驅節點
    if(node.getLeft() == null) {
        // 讓當前節點的左指針指向前驅節點
        node.setLeft(prev);
        // 修改當前節點的左指針類型
        node.setLeftType(1);
    }
    // 處理後繼節點
    if(prev != null && prev.getRight() == null) {
        // 讓前驅節點的右指針指向當前節點
        prev.setRight(node);
        // 修改當前節點的右指針類型
        prev.setRightType(1);
    }
    // 每處理一個節點後, 讓當前節點是下一個節點的前驅節點
    prev = node;
    // 3. 再線索化右子樹
    threadedNodes(node.getRight());
}

把二元樹建立好，然後線索化，輸出 10 的前驅和後繼節點。

public static void main(String[] args) {
    TreeNode root = new TreeNode(1, "Tom");
    TreeNode node2 = new TreeNode(3, "Jack");
    TreeNode node3 = new TreeNode(6, "Smith");
    TreeNode node4 = new TreeNode(8, "Mary");
    TreeNode node5 = new TreeNode(10, "King");
    TreeNode node6 = new TreeNode(14, "Candy");

    // 簡單處理使用手動創建
    root.setLeft(node2);
    root.setRight(node3);
    node2.setLeft(node4);
    node2.setRight(node5);
    node3.setLeft(node6);

    // 測試中序線索化
    ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
    threadedBinaryTree.setRoot(root);
    threadedBinaryTree.threadedNodes();

    // 測試, 以 10 測試
    // 原本 10 的左指針為空 , 線索化後左指針指向前驅節點 3
    TreeNode leftNode = node5.getLeft();
    System.out.println("10號節點的前驅節點為: "+leftNode);
    // 原本 10 的右指針為空 , 線索化後右指針指向後繼節點 1
    TreeNode rightNode = node5.getRight();
    System.out.println("10號節點的後繼節點為: "+rightNode);
}

output

10號節點的前驅節點為: TreeNode [no = 3, name = Jack ]
10號節點的後繼節點為: TreeNode [no = 1, name = Tom ]

線索二元樹的遍歷

在前面二元樹的部分有提到過遍歷，但是因為線索化後各個節點指向有變化，因此原來的遍歷方式不能使用，需要使用新的方式遍歷線索化二元樹。各個節點可以通過線性方式遍歷，無需使用遞迴方式，提高了遍歷的效率。遍歷的次序應當和中序遍歷保持一致。

中序遍歷

在樹類中寫一個遍歷方法

// 遍歷線索化二元樹的方法
public void threadedList() {
    // 定義一個變數, 臨時存儲當前遍歷的節點, 從root開始
    TreeNode node = root;
    while(node != null) {
        // 循環的找到leftType = 1 的節點, 說明該節點是按照線索化處理後的有效節點
        while(node.getLeftType() == 0) {
            node = node.getLeft();
        }
        // 輸出當前節點
        System.out.println(node);
        // 如果當前節點的右指針指向的是後繼節點, 就一直輸出
        while(node.getRightType() == 1) {
            node = node.getRight();
            System.out.println(node);
        }
        // 替換這個遍歷的節點
        node = node.getRight();
    }
}

測試中序遍歷是否正確，為8, 3, 10, 1, 14, 6

System.out.println("===使用線索化方式遍歷線索化二元樹===");
threadedBinaryTree.threadedList(); //8, 3, 10, 1, 14, 6

output

===使用線索化方式遍歷線索化二元樹===
TreeNode [no = 8, name = Mary ]
TreeNode [no = 3, name = Jack ]
TreeNode [no = 10, name = King ]
TreeNode [no = 1, name = Tom ]
TreeNode [no = 14, name = Candy ]
TreeNode [no = 6, name = Smith ]

前序遍歷

前序線索化

//對二元樹進行前序線索化的方法
public void preThreadedNodes(TreeNode node) {
    if(node == null) {
        return;
    }

    if(node.getLeft() == null) {
        // 讓當前節點的左指針指向前驅節點
        node.setLeft(prev);
        // 修改當前節點的左指針類型
        node.setLeftType(1);
    }

    if(prev != null && prev.getRight() == null) {
        // 讓前驅節點的右指針指向當前節點
        prev.setRight(node);
        // 修改當前節點的右指針類型
        prev.setRightType(1);
    }

    prev = node;

    if(node.getLeftType() == 0) {
        preThreadedNodes(node.getLeft());
    }

    if(node.getRightType() == 0) {
        preThreadedNodes(node.getRight());
    }

}

前序遍歷

// 前序遍歷線索化二元樹
public void preThreadedList() {
    TreeNode node = root;
    while(node != null) {

        System.out.println(node);

        while(node.getLeftType() == 0) {
            node = node.getLeft();
            System.out.println(node);
        }

        while(node.getRightType() == 1) {
            node = node.getRight();
            System.out.println(node);
        }

        node = node.getRight();
    }
}

試著遍歷看看是否正確

System.out.println("===前序===");
threadedBinaryTree.preThreadedNodes();
threadedBinaryTree.preThreadedList(); //前:1, 3, 8, 10, 6, 14

output

===前序===
TreeNode [no = 1, name = Tom ]
TreeNode [no = 3, name = Jack ]
TreeNode [no = 8, name = Mary ]
TreeNode [no = 10, name = King ]
TreeNode [no = 6, name = Smith ]
TreeNode [no = 14, name = Candy ]

完整程式碼在 ThreadedBinaryTreeDemo.java