# 線索二元樹(Threaded Binary Tree)
一個二元樹通過線索連起來。所有原本為空的右(孩子)指針改為指向該節點在中序序列中的後繼，所有原本為空的左(孩子)指針改為指向該節點的中序序列的前驅。
假設該二元樹中序遍歷為 `A B C D E F G H I`，根據上述說明試著解讀為何這些節點的線索是這樣連的。
A 節點的左指針為空，因此指向其中序的前驅節點為 B，右指針要指向後繼，但它是第一個遍歷所以為空；C 節點的左指針指向前驅 B，右指針指向後繼 D...以此類推。
:::warning
- 線索二元樹能線性地遍歷二元樹，從而比遞迴的中序遍歷更快，並且建立線索並不影響時間複雜度。
- 使用線索二元樹也能夠方便的找到一個節點的父節點，這比多宣告一個父親節點指針來找 或者用 棧 效率更高。
- 這在棧空間有限、無法使用存儲父節點的棧時很有作用(對於通過深度優先搜索DFS來搜尋父節點而言)。
:::
因此，當使用線索二元樹時，Node節點的left和right屬性有以下情況需要考慮：
1. left 指向的是左子樹，也可能是指向前驅節點。
2. right 指向的是右子樹，也可能是指向後繼節點。
## 簡易實現
試著找出 10 的前驅和後繼節點為何？
首先我們需要在節點類中宣告兩個變數，用於將左指針右指針分類，並加上get和set方法。
```java=
// 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 節點用於指向當前節點的前驅節點
```java=
private TreeNode prev = null;
```
線索化的方法
```java=
// 重載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 的前驅和後繼節點。
```java=
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
```java=
10號節點的前驅節點為: TreeNode [no = 3, name = Jack ]
10號節點的後繼節點為: TreeNode [no = 1, name = Tom ]
```
## 線索二元樹的遍歷
在前面二元樹的部分有提到過遍歷，但是因為線索化後各個節點指向有變化，因此原來的遍歷方式不能使用，需要使用新的方式遍歷線索化二元樹。各個節點可以通過**線性方式**遍歷，無需使用遞迴方式，提高了遍歷的效率。遍歷的次序應當和中序遍歷保持一致。
### 中序遍歷
在樹類中寫一個遍歷方法
```java=
// 遍歷線索化二元樹的方法
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
```java=
System.out.println("===使用線索化方式遍歷線索化二元樹===");
threadedBinaryTree.threadedList(); //8, 3, 10, 1, 14, 6
```
output
```java=
===使用線索化方式遍歷線索化二元樹===
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 ]
```
### 前序遍歷
前序線索化
```java=
//對二元樹進行前序線索化的方法
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());
}
}
```
前序遍歷
```java=
// 前序遍歷線索化二元樹
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();
}
}
```
試著遍歷看看是否正確
```java=
System.out.println("===前序===");
threadedBinaryTree.preThreadedNodes();
threadedBinaryTree.preThreadedList(); //前:1, 3, 8, 10, 6, 14
```
output
```java=
===前序===
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](https://github.com/AquariusMay/Data-Structures-and-Algorithms-in-Java/blob/master/BinaryTree/ThreadedBinaryTreeDemo.java)
Sign in with Wallet
Connect another wallet