---
# System prepended metadata

title: 二元搜尋樹(Binary Search Tree)

---

# 二元搜尋樹(Binary Search Tree)

對於二元搜尋樹的任何一個非葉子節點，要求左子節點的值比當前節點的值小，右子節點的值比當前節點的值大。如果有相同的值，可以將該節點放在左子節點或右子節點。

比如 `[7, 3, 10, 12, 5, 1, 9]` 對應的二元搜尋樹為：

![](https://i.imgur.com/JhF5ZLO.png)

當在此二元搜尋樹中插入 2 時則變為

![](https://i.imgur.com/TYWEE00.png)

## 二元搜尋樹的創建和中序遍歷

```java=
package Tree;

public class BinarySearchTreeDemo {
    public static void main(String[] args) {
        int arr[] = {7, 3, 10, 12, 5, 1, 9};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        // 循環添加節點到二元搜尋樹
        for(int i = 0; i < arr.length; i++) {
            binarySearchTree.add(new Node(arr[i]));
        }
        // 中序遍歷二元搜尋樹
        System.out.println("===中序遍歷二元搜尋樹===");
        binarySearchTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12
    }
    
}
// 創建二元搜尋樹
class BinarySearchTree {
    private Node root;
    // 添加節點的方法
    public void add(Node node) {
        if(root == null) {
            root = node; // root為空則直接指向node
        } else {
            root.add(node);
        }
    }

    // 中序遍歷
    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        } else {
            System.out.println("二元搜尋樹為空!");
        }
    }

 }
// 創建Node節點
class Node {
    int value;
    Node left; // 左子樹
    Node right; // 右子樹
    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node [value = " + value + " ]";
    }

    // 用遞迴的形式添加節點的方法
    public void add(Node node) {
        if(node == null) return;
        // 判斷傳入的節點的值, 和當前根節點的值的關係
        if(node.value < this.value) {
            // 如果當前節點左子節點為空
            if(this.left == null) {
                this.left = node;
            } else {
                // 遞迴的向左子樹添加
                this.left.add(node);
            }
        } else { // 添加的節點大於等於當前節點
            if(this.right == null) {
                this.right = node;
            } else {
                // 遞迴的向右子樹添加
                this.right.add(node);
            }
        }
    }

    // 中序遍歷
    public void infixOrder() {
        if(this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right != null) {
            this.right.infixOrder();
        }
    }

}
```

output
```java=
===中序遍歷二元搜尋樹===
Node [value = 1 ] 
Node [value = 3 ] 
Node [value = 5 ] 
Node [value = 7 ] 
Node [value = 9 ] 
Node [value = 10 ]
Node [value = 12 ]
```

## 二元搜尋樹的刪除

需要考慮的情況：
1. 刪除葉子節點(ex: 2, 5, 9, 12)
2. 刪除只有一棵子樹的節點(ex: 1)
3. 刪除有兩棵子樹的節點(ex: 7, 3, 10)

![](https://i.imgur.com/TYWEE00.png)

### 刪除葉子節點

**思路**
1. 需要先去找到要刪除的節點 targetNode
2. 找到 targetNode 的父節點 parent (考慮是否存在父節點)
3. 確定 targetNode 是 parent的左子節點還是右子節點
4. 根據前面的情況來對應刪除
左子節點 `parent.left = null` , 右子節點 `parent.right = null`

```java=
// 搜尋要刪除的節點
/**
 * 
 * @param value 希望刪除的節點的值
 * @return 如果找到返回該節點, 否則返回null
 */
public Node search(int value) {
    if(value == this.value) { // 找到該節點
        return this;
    } else if(value < this.value) { // 如果搜尋的值小於當前節點, 向左子樹遞迴搜尋
        // 如果左子節點為空
        if(this.left == null) return null;
        return this.left.search(value);
    } else {
        // 如果右子節點為空
        if(this.right == null) return null;
        return this.right.search(value);
    }
}

// 搜尋要刪除節點的父節點
/**
 * 
 * @param value 要找的節點的值
 * @return 返回的是要刪除的節點的父節點, 如果沒有則返回null
 */
public Node searchParent(int value) {
    // 如果當前節點就是要刪除節點的父節點, 就返回
    if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
        return this;
    } else {
        // 如果搜尋的值小於當前節點的值, 並且當前節點的左子節點不為空
        if(value < this.value && this.left != null) {
            return this.left.searchParent(value); // 向左子樹遞迴搜尋
        } else if(value >= this.value && this.right != null) {
            return this.right.searchParent(value); // 向右子樹遞迴搜尋
        } else {
            return null; // 沒有找到父節點
        }

    }
}
```

封裝到 binarySearchTree
```java=
// 搜尋要刪除的節點
public Node search(int value) {
    if(root == null) return null;
    else return root.search(value);
}
// 搜尋父節點
public Node searchParent(int value) {
    if(root == null) return null;
    else return root.searchParent(value);
}
// 刪除節點
public void delNode(int value) {
    if(root == null) return;
    else {
        // 先找到要刪除的節點 targetNode
        Node targetNode = search(value);
        // 沒找到要刪除的節點
        if(targetNode == null) return;
        // 如果當前二元搜尋樹只有一個節點
        if(root.left == null && root.right == null) {
            root = null;
            return;
        }
        // 去找到targetNode的父節點
        Node parent = searchParent(value);
        // 如果要刪除的節點是葉子節點
        if(targetNode.left == null && targetNode.right == null) {
            // 判斷 targetNode 是父節點的左子節點還是右子節點
            if(parent.left != null && parent.left.value == value) {
                parent.left = null;
            } else if(parent.right != null && parent.right.value == value) {
                parent.right = null;
            }
        }
    }
}
```

#### 完整程式碼
```java=
package Tree;

public class BinarySearchTreeDemo {
    public static void main(String[] args) {
        int arr[] = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        // 循環添加節點到二元搜尋樹
        for(int i = 0; i < arr.length; i++) {
            binarySearchTree.add(new Node(arr[i]));
        }
        // 中序遍歷二元搜尋樹
        System.out.println("===中序遍歷二元搜尋樹===");
        binarySearchTree.infixOrder(); // 1, 2, 3, 5, 7, 9, 10, 12

        System.out.println("===刪除節點 2 ===");
        binarySearchTree.delNode(2);
        binarySearchTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12
    }
    
}
// 創建二元搜尋樹
class BinarySearchTree {
    private Node root;

    // 搜尋要刪除的節點
    public Node search(int value) {
        if(root == null) return null;
        else return root.search(value);
    }
    // 搜尋父節點
    public Node searchParent(int value) {
        if(root == null) return null;
        else return root.searchParent(value);
    }
    // 刪除節點
    public void delNode(int value) {
        if(root == null) return;
        else {
            // 先找到要刪除的節點 targetNode
            Node targetNode = search(value);
            // 沒找到要刪除的節點
            if(targetNode == null) return;
            // 如果當前二元搜尋樹只有一個節點
            if(root.left == null && root.right == null) {
                root = null;
                return;
            }
            // 去找到targetNode的父節點
            Node parent = searchParent(value);
            // 如果要刪除的節點是葉子節點
            if(targetNode.left == null && targetNode.right == null) {
                // 判斷 targetNode 是父節點的左子節點還是右子節點
                if(parent.left != null && parent.left.value == value) {
                    parent.left = null;
                } else if(parent.right != null && parent.right.value == value) {
                    parent.right = null;
                }
            }
        }
    }

    // 添加節點的方法
    public void add(Node node) {
        if(root == null) {
            root = node; // root為空則直接指向node
        } else {
            root.add(node);
        }
    }

    // 中序遍歷
    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        } else {
            System.out.println("二元搜尋樹為空!");
        }
    }

 }
// 創建Node節點
class Node {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }

    // 搜尋要刪除的節點
    /**
     * 
     * @param value 希望刪除的節點的值
     * @return 如果找到返回該節點, 否則返回null
     */
    public Node search(int value) {
        if(value == this.value) { // 找到該節點
            return this;
        } else if(value < this.value) { // 如果搜尋的值小於當前節點, 向左子樹遞迴搜尋
            // 如果左子節點為空
            if(this.left == null) return null;
            return this.left.search(value);
        } else {
            // 如果右子節點為空
            if(this.right == null) return null;
            return this.right.search(value);
        }
    }

    // 搜尋要刪除節點的父節點
    /**
     * 
     * @param value 要找的節點的值
     * @return 返回的是要刪除的節點的父節點, 如果沒有則返回null
     */
    public Node searchParent(int value) {
        // 如果當前節點就是要刪除節點的父節點, 就返回
        if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            // 如果搜尋的值小於當前節點的值, 並且當前節點的左子節點不為空
            if(value < this.value && this.left != null) {
                return this.left.searchParent(value); // 向左子樹遞迴搜尋
            } else if(value >= this.value && this.right != null) {
                return this.right.searchParent(value); // 向右子樹遞迴搜尋
            } else {
                return null; // 沒有找到父節點
            }

        }
    }

    @Override
    public String toString() {
        return "Node [value = " + value + " ]";
    }

    // 用遞迴的形式添加節點的方法
    public void add(Node node) {
        if(node == null) return;
        // 判斷傳入的節點的值, 和當前根節點的值的關係
        if(node.value < this.value) {
            // 如果當前節點左子節點為空
            if(this.left == null) {
                this.left = node;
            } else {
                // 遞迴的向左子樹添加
                this.left.add(node);
            }
        } else { // 添加的節點大於等於當前節點
            if(this.right == null) {
                this.right = node;
            } else {
                // 遞迴的向右子樹添加
                this.right.add(node);
            }
        }
    }

    // 中序遍歷
    public void infixOrder() {
        if(this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right != null) {
            this.right.infixOrder();
        }
    }

}
```

output
```java=
===中序遍歷二元搜尋樹===
Node [value = 1 ]
Node [value = 2 ]
Node [value = 3 ]
Node [value = 5 ]
Node [value = 7 ]
Node [value = 9 ]
Node [value = 10 ]
Node [value = 12 ]
===刪除節點 2 ===
Node [value = 1 ]
Node [value = 3 ]
Node [value = 5 ]
Node [value = 7 ]
Node [value = 9 ]
Node [value = 10 ]
Node [value = 12 ]
```

### 刪除只有一棵子樹的節點
**思路**
1. 需要先去找到要刪除的節點 targetNode
2. 找到 targetNode 的父節點 parent (考慮是否存在父節點)
3. 確定 targetNode 的子節點是左子節點還是右子節點
4. targetNode 是 parent 的左子節點還是右子節點
5. 如果 targetNode 是 parent 的左子節點
5.1 targetNode 的子節點是左子節點 `parent.left = targetNode.left`
5.2 targetNode 的子節點是右子節點 `parent.left = targetNode.right`
5. 如果 targetNode 是 parent 的右子節點
5.1 targetNode 的子節點是左子節點 `parent.right = targetNode.left`
5.2 targetNode 的子節點是右子節點 `parent.right = targetNode.right`

![](https://i.imgur.com/TYWEE00.png)

```java=
public void delNode(int value) {
    if(root == null) return;
    else {
        // 先找到要刪除的節點 targetNode
        Node targetNode = search(value);
        // 沒找到要刪除的節點
        if(targetNode == null) return;
        // 如果當前二元搜尋樹只有一個節點
        if(root.left == null && root.right == null) {
            root = null;
            return;
        }
        // 去找到targetNode的父節點
        Node parent = searchParent(value);
        // 如果要刪除的節點是葉子節點
        if(targetNode.left == null && targetNode.right == null) {
            // 判斷 targetNode 是父節點的左子節點還是右子節點
            if(parent.left != null && parent.left.value == value) {
                parent.left = null;
            } else if(parent.right != null && parent.right.value == value) {
                parent.right = null;
            }
        } else if (targetNode.left != null && targetNode.right != null) { // 刪除有兩棵子樹的節點
        
        } else { // 刪除只有一棵子樹的節點
            // 如果要刪除的節點有左子節點
            if(targetNode.left != null) {
                if(parent != null) {
                    // 如果 targetNode 是 parent 的左子節點
                    if(parent.left.value == value) {
                        parent.left = targetNode.left;
                    } else {
                        parent.right = targetNode.left;
                    }
                } else {
                    root = targetNode.left;
                }
            } else { // 要刪除的節點有右子節點
                if(parent != null) {
                    // 如果 targetNode 是 parent 的右子節點
                    if(parent.left.value == value) {
                        parent.left = targetNode.right;
                    } else {
                        parent.right = targetNode.right;
                    }
                } else {
                    root = targetNode.right;
                }
            }
        }
    }
}
```

main
```java=
public static void main(String[] args) {
    int arr[] = {7, 3, 10, 12, 5, 1, 9, 2};
    BinarySearchTree binarySearchTree = new BinarySearchTree();
    // 循環添加節點到二元搜尋樹
    for(int i = 0; i < arr.length; i++) {
        binarySearchTree.add(new Node(arr[i]));
    }
    // 中序遍歷二元搜尋樹
    System.out.println("===中序遍歷二元搜尋樹===");
    binarySearchTree.infixOrder(); // 1, 2, 3, 5, 7, 9, 10, 12

    System.out.println("===刪除節點 1 ===");
    binarySearchTree.delNode(1);
    binarySearchTree.infixOrder(); // 2, 3, 5, 7, 9, 10, 12
}
```

output
```java=
===中序遍歷二元搜尋樹===
Node [value = 1 ]
Node [value = 2 ]
Node [value = 3 ]
Node [value = 5 ]
Node [value = 7 ]
Node [value = 9 ]
Node [value = 10 ]
Node [value = 12 ]
===刪除節點 1 ===
Node [value = 2 ]
Node [value = 3 ]
Node [value = 5 ]
Node [value = 7 ]
Node [value = 9 ]
Node [value = 10 ]
Node [value = 12 ]
```

### 刪除有兩棵子樹的節點
**思路**
1. 需要先去找到要刪除的節點 targetNode
2. 找到 targetNode 的父節點 parent (考慮是否存在父節點)
3. 從 targetNode 的右子樹找到最小的節點 (或者左子樹最大的節點)
4. 用一個臨時變數，將最小節點的值保存 temp
5. 刪除該最小節點
6. targetNode.value = temp

![](https://i.imgur.com/TYWEE00.png)

```java=
// 1. 返回以node 為根節點的二元搜尋樹的最小節點的值
// 2. 刪除 node 為根節點的二元搜尋樹的最小節點
/**
 * 
 * @param node 傳入的節點(當作二元搜尋樹的根結點)
 * @return 返回的 以node 為根節點的二元搜尋樹的最小節點的值
 */
public int delRightTreeMin(Node node) {
    Node target = node;
    // 循環的搜尋左節點, 就會找到最小值
    while(target.left != null) {
        target = target.left;
    }
    // 這時target 指向了最小節點
    // 刪除最小節點
    delNode(target.value);
    return target.value;
}

public void delNode(int value) {
    if(root == null) return;
    else {
        // 先找到要刪除的節點 targetNode
        Node targetNode = search(value);
        // 沒找到要刪除的節點
        if(targetNode == null) return;
        // 如果當前二元搜尋樹只有一個節點
        if(root.left == null && root.right == null) {
            root = null;
            return;
        }
        // 去找到targetNode的父節點
        Node parent = searchParent(value);
        // 如果要刪除的節點是葉子節點
        if(targetNode.left == null && targetNode.right == null) {
            // 判斷 targetNode 是父節點的左子節點還是右子節點
            if(parent.left != null && parent.left.value == value) {
                parent.left = null;
            } else if(parent.right != null && parent.right.value == value) {
                parent.right = null;
            }
        } else if (targetNode.left != null && targetNode.right != null) { // 刪除有兩棵子樹的節點
            int minVal = delRightTreeMin(targetNode.right);
            targetNode.value = minVal;
        } else { // 刪除只有一棵子樹的節點
            // 如果要刪除的節點有左子節點
            if(targetNode.left != null) {
                if(parent != null) {
                    // 如果 targetNode 是 parent 的左子節點
                    if(parent.left.value == value) {
                        parent.left = targetNode.left;
                    } else {
                        parent.right = targetNode.left;
                    }
                } else {
                    root = targetNode.left;
                }
            } else { // 要刪除的節點有右子節點
                if(parent != null) {
                    // 如果 targetNode 是 parent 的右子節點
                    if(parent.left.value == value) {
                        parent.left = targetNode.right;
                    } else {
                        parent.right = targetNode.right;
                    }
                } else {
                    root = targetNode.right;
                }
            }
        }
    }
}
```

刪除節點 `7`

```java=
public static void main(String[] args) {
    int arr[] = {7, 3, 10, 12, 5, 1, 9, 2};
    BinarySearchTree binarySearchTree = new BinarySearchTree();
    // 循環添加節點到二元搜尋樹
    for(int i = 0; i < arr.length; i++) {
        binarySearchTree.add(new Node(arr[i]));
    }
    // 中序遍歷二元搜尋樹
    System.out.println("===中序遍歷二元搜尋樹===");
    binarySearchTree.infixOrder(); // 1, 2, 3, 5, 7, 9, 10, 12

    System.out.println("===刪除節點 7 ===");
    binarySearchTree.delNode(7);
    binarySearchTree.infixOrder(); // 1, 2, 3, 5, 9, 10, 12
}
```

output
```java=
===中序遍歷二元搜尋樹===
Node [value = 1 ]
Node [value = 2 ]
Node [value = 3 ]
Node [value = 5 ]
Node [value = 7 ]
Node [value = 9 ]
Node [value = 10 ]
Node [value = 12 ]
===刪除節點 7 ===
Node [value = 1 ]
Node [value = 2 ]
Node [value = 3 ]
Node [value = 5 ]
Node [value = 9 ]
Node [value = 10 ]
Node [value = 12 ]
```

刪除節點 `3`
```java=
System.out.println("===刪除節點 3 ===");
binarySearchTree.delNode(3);
binarySearchTree.infixOrder(); // 1, 2, 5, 7, 9, 10, 12
```

output
```java=
===中序遍歷二元搜尋樹===
Node [value = 1 ]
Node [value = 2 ]
Node [value = 3 ]
Node [value = 5 ]
Node [value = 7 ]
Node [value = 9 ]
Node [value = 10 ]
Node [value = 12 ]
===刪除節點 3 ===
Node [value = 1 ]
Node [value = 2 ]
Node [value = 5 ]
Node [value = 7 ]
Node [value = 9 ]
Node [value = 10 ]
Node [value = 12 ]
```

### 完整程式碼
```java=
package Tree;

public class BinarySearchTreeDemo {
    public static void main(String[] args) {
        int arr[] = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        // 循環添加節點到二元搜尋樹
        for(int i = 0; i < arr.length; i++) {
            binarySearchTree.add(new Node(arr[i]));
        }
        // 中序遍歷二元搜尋樹
        System.out.println("===中序遍歷二元搜尋樹===");
        binarySearchTree.infixOrder(); // 1, 2, 3, 5, 7, 9, 10, 12

        System.out.println("===刪除節點 3 ===");
        binarySearchTree.delNode(3);
        binarySearchTree.infixOrder(); // 1, 2, 5, 7, 9, 10, 12
    }
    
}
// 創建二元搜尋樹
class BinarySearchTree {
    private Node root;

    // 搜尋要刪除的節點
    public Node search(int value) {
        if(root == null) return null;
        else return root.search(value);
    }
    // 搜尋父節點
    public Node searchParent(int value) {
        if(root == null) return null;
        else return root.searchParent(value);
    }

    // 1. 返回以node 為根節點的二元搜尋樹的最小節點的值
    // 2. 刪除 node 為根節點的二元搜尋樹的最小節點
    /**
     * 
     * @param node 傳入的節點(當作二元搜尋樹的根結點)
     * @return 返回的 以node 為根節點的二元搜尋樹的最小節點的值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        // 循環的搜尋左節點, 就會找到最小值
        while(target.left != null) {
            target = target.left;
        }
        // 這時target 指向了最小節點
        // 刪除最小節點
        delNode(target.value);
        return target.value;
    }

    // 刪除節點
    public void delNode(int value) {
        if(root == null) return;
        else {
            // 先找到要刪除的節點 targetNode
            Node targetNode = search(value);
            // 沒找到要刪除的節點
            if(targetNode == null) return;
            // 如果當前二元搜尋樹只有一個節點
            if(root.left == null && root.right == null) {
                root = null;
                return;
            }
            // 去找到targetNode的父節點
            Node parent = searchParent(value);
            // 如果要刪除的節點是葉子節點
            if(targetNode.left == null && targetNode.right == null) {
                // 判斷 targetNode 是父節點的左子節點還是右子節點
                if(parent.left != null && parent.left.value == value) {
                    parent.left = null;
                } else if(parent.right != null && parent.right.value == value) {
                    parent.right = null;
                }
            } else if (targetNode.left != null && targetNode.right != null) { // 刪除有兩棵子樹的節點
                int minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;
            } else { // 刪除只有一棵子樹的節點
                // 如果要刪除的節點有左子節點
                if(targetNode.left != null) {
                    if(parent != null) {
                        // 如果 targetNode 是 parent 的左子節點
                        if(parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else { // 要刪除的節點有右子節點
                    if(parent != null) {
                        // 如果 targetNode 是 parent 的右子節點
                        if(parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else {
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }

    // 添加節點的方法
    public void add(Node node) {
        if(root == null) {
            root = node; // root為空則直接指向node
        } else {
            root.add(node);
        }
    }

    // 中序遍歷
    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        } else {
            System.out.println("二元搜尋樹為空!");
        }
    }

 }
// 創建Node節點
class Node {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }

    // 搜尋要刪除的節點
    /**
     * 
     * @param value 希望刪除的節點的值
     * @return 如果找到返回該節點, 否則返回null
     */
    public Node search(int value) {
        if(value == this.value) { // 找到該節點
            return this;
        } else if(value < this.value) { // 如果搜尋的值小於當前節點, 向左子樹遞迴搜尋
            // 如果左子節點為空
            if(this.left == null) return null;
            return this.left.search(value);
        } else {
            // 如果右子節點為空
            if(this.right == null) return null;
            return this.right.search(value);
        }
    }

    // 搜尋要刪除節點的父節點
    /**
     * 
     * @param value 要找的節點的值
     * @return 返回的是要刪除的節點的父節點, 如果沒有則返回null
     */
    public Node searchParent(int value) {
        // 如果當前節點就是要刪除節點的父節點, 就返回
        if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            // 如果搜尋的值小於當前節點的值, 並且當前節點的左子節點不為空
            if(value < this.value && this.left != null) {
                return this.left.searchParent(value); // 向左子樹遞迴搜尋
            } else if(value >= this.value && this.right != null) {
                return this.right.searchParent(value); // 向右子樹遞迴搜尋
            } else {
                return null; // 沒有找到父節點
            }

        }
    }

    @Override
    public String toString() {
        return "Node [value = " + value + " ]";
    }

    // 用遞迴的形式添加節點的方法
    public void add(Node node) {
        if(node == null) return;
        // 判斷傳入的節點的值, 和當前根節點的值的關係
        if(node.value < this.value) {
            // 如果當前節點左子節點為空
            if(this.left == null) {
                this.left = node;
            } else {
                // 遞迴的向左子樹添加
                this.left.add(node);
            }
        } else { // 添加的節點大於等於當前節點
            if(this.right == null) {
                this.right = node;
            } else {
                // 遞迴的向右子樹添加
                this.right.add(node);
            }
        }
    }

    // 中序遍歷
    public void infixOrder() {
        if(this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right != null) {
            this.right.infixOrder();
        }
    }

}
```