# 二元搜尋樹(Binary Search Tree)
對於二元搜尋樹的任何一個非葉子節點，要求左子節點的值比當前節點的值小，右子節點的值比當前節點的值大。如果有相同的值，可以將該節點放在左子節點或右子節點。
比如 `[7, 3, 10, 12, 5, 1, 9]` 對應的二元搜尋樹為：
當在此二元搜尋樹中插入 2 時則變為
## 二元搜尋樹的創建和中序遍歷
```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)
### 刪除葉子節點
**思路**
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`
```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
```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();
}
}
}
```
Sign in with Wallet
Connect another wallet