二元樹的常見應用之一是「二元搜尋樹」（Binary Search Tree），它是資料經過排序的二元樹。其特色是左子樹所有節點的值均小於自己，而右子樹所有節點的值均大於自己。適合用於排序與搜尋的場合。同時也是練習新增、刪除節點的好題材。本文會使用 Java 程式語言建立出二元搜尋樹，接著在樹中查找指定的資料，並了解刪除節點的方式。
一、二元搜尋樹的建立方式
建立二元搜尋樹的方式是輸入一組資料，先將第一筆做為根節點，再將後續資料從根節點開始比較大小。經由與其他節點比較後，便可找到適當的放置位置。以下是建立過程的示意圖。
範例資料為：4、2、1、6、3、7、5，首先將4做為根節點。接著處理2，由於小於4，所以往左邊前進並新增節點。再來處理1，由於小於4，所以往左邊前進。但該位置已經有節點，於是繼續跟2比較，並新增節點在它的左邊。依此類推，直到全部資料都處理完畢。
二、二元搜尋樹的實作
本節會實作出二元搜尋樹。首先要先準備樹節點的類別，它包含儲存的資料及指向左、右節點的指標。
public class TreeNode<E> {
private E value;
private TreeNode<E> leftNode;
private TreeNode<E> rightNode;
public TreeNode(E value) {
this.value = value;
}
public E getValue() {
return value;
}
public TreeNode<E> getLeftNode() {
return leftNode;
}
public void setLeftNode(TreeNode<E> leftNode) {
this.leftNode = leftNode;
}
public TreeNode<E> getRightNode() {
return rightNode;
}
public void setRightNode(TreeNode<E> rightNode) {
this.rightNode = rightNode;
}
@Override
public String toString() {
return value.toString();
}
}
接著再宣告一個叫 BinarySearchTree 的類別。建立出物件後，需呼叫 init 方法，傳入整數陣列進行初始化，將資料放置到各個節點。而 find 方法則是搜尋某筆資料後回傳，並印出在節點間行進的方向。
public class BinarySearchTree {
private TreeNode<Integer> rootNode;
public void init(int[] values) {
// TODO
}
public Integer find(int target) {
// TODO
return null;
}
}
首先實作初始化二元搜尋樹的程式，也就是 init 方法。
public void init(int[] values) {
if (values.length == 0) {
return;
}
TreeNode<Integer> visitedNode;
this.rootNode = new TreeNode<>(values[0]);
for (int i = 1; i < values.length; i++) {
visitedNode = this.rootNode;
TreeNode<Integer> newNode = new TreeNode<>(values[i]);
while (true) {
if (values[i] < visitedNode.getValue()) {
if (visitedNode.getLeftNode() == null) {
visitedNode.setLeftNode(newNode);
break;
}
visitedNode = visitedNode.getLeftNode();
} else {
if (visitedNode.getRightNode() == null) {
visitedNode.setRightNode(newNode);
break;
}
visitedNode = visitedNode.getRightNode();
}
}
}
}
一開始先把陣列的第一個元素做為根節點，而其餘元素則從根節點出發，與已放置的節點進行比較。過程中使用 visitedNode 變數來紀錄目前走到的節點。若被放置的資料小於該節點，就往左邊行進並繼續比較。若左邊沒有節點，則放置新節點，依此類推。
接著是搜尋特定目標的方法，也就是 find 方法。
public Integer find(int target) {
if (this.rootNode == null) {
return null;
}
StringBuilder sb = new StringBuilder()
.append("Searching path of ")
.append(target)
.append(": Root");
TreeNode<Integer> visitedNode = this.rootNode;
while (visitedNode.getValue() != target) {
if (target < visitedNode.getValue()) {
visitedNode = visitedNode.getLeftNode();
sb.append(" -> Left");
} else {
visitedNode = visitedNode.getRightNode();
sb.append(" -> Right");
}
if (visitedNode == null) {
return null;
}
}
System.out.println(sb);
return visitedNode.getValue();
}
做法與上述的初始化類似，都是由根節點開始往下找，原理與二元搜尋法有異曲同工之妙。筆者在範例程式中還會印出拜訪路徑的左右方向。
此處同樣用 visitedNode 變數紀錄目前走到的節點。若節點的值比目標值大，就往左節點移動，否則往右節點。若遇到 visitedNode 為 null 的情況，代表走到樹葉（終端節點）都沒有找到目標值，所以目標值不在這棵樹中。
三、刪除節點的方式
在第二節建立二元搜尋樹的過程中，我們知道如何在樹中新增節點。本節將會解說如何刪除節點，並於第四節進行程式實作。首先當然是確認欲刪除節點的位置，根據它的所在位置，會有數種情形要考慮。而為了維持二元搜尋樹的特性（左小右大），也會不同的處理方式。
第一種情形是欲刪除節點並沒有子節點，意即樹葉節點。此時只要將父節點原先指向欲刪除節點的指標，改為指向 null 即可。若刪除的正好是根節點，則將其設為 null，代表這棵樹沒有走訪的進入點了。
第二種情形是欲刪除節點有一個子節點。此時只要將父節點，接上欲刪除節點的子節點即可。若刪除的正好是根節點，則將欲刪除節點的子節點取代到根節點的位置。
第三種情形是欲刪除節點有兩個子節點。我們要找出與欲刪除節點的資料最相近的節點，取代其位置。此時有兩個選擇，分別是左子樹的最大值節點和右子樹的最小值節點。筆者以下圖的二元搜尋樹為例。
假設刪除節點20，那麼可以選擇從左節點一路向右到底，找到15。或從右節點一路向左到底，找到25。並將該節點取代到欲刪除節點。
在進行節點的取代時，還要記得更新指標。首先是取代用節點的父節點，要接上它的子節點，例如上圖左邊的10接上13，右邊的30接上28。
再來是取代用節點的左右指標，要更新成與欲刪除節點相同。例如上圖挑選出的15或25，都接上原先20的子節點（10和30）。
最後是讓欲刪除節點的父節點改為指向取代用節點。例如上圖的節點40，會指向挑選出來的15或25。但若刪除的是根節點，則取代用節點將應放置在根節點的位置。
四、實作刪除節點
經由上一節的說明，我們知道在刪除二元搜尋樹節點的過程中，會有四個重要的節點。以下是在程式實作中的變數名稱以及用途。
- 欲刪除節點（removingNode）：提供左、右節點的指標給取代用節點。
- 欲刪除節點的父節點（parentOfRemovingNode）：獲取欲刪除節點，並在最後指向取代用節點。
- 取代用節點（replacingNode）：被欲刪除節點的父節點所指向，並在最後指向欲刪除節點的子節點。
- 取代用節點的父節點（parentOfReplacingNode）：指向取代用節點的子節點。
有概念後，本節就來實作程式。我們先在 BinarySearchTree 類別宣告 remove 方法，它會接收一個整數，並刪除具有這個值的節點。
一開始會先找出欲刪除節點（removingNode）和它的父節點（parentOfRemovingNode），做法與新增節點相當類似。若找不到欲刪除節點，程式就結束。至於布林值 isLeftNode 代表 removingNode 位於父節點的左或右。意即尋找到節點的前一步，是向左還是向右。
public void remove(int target) {
if (this.rootNode == null) {
return;
}
TreeNode<Integer> parentOfRemovingNode = null;
TreeNode<Integer> removingNode = this.rootNode;
boolean isLeftNode = false;
while (removingNode.getValue() != target) {
parentOfRemovingNode = removingNode;
if (target < removingNode.getValue()) {
removingNode = removingNode.getLeftNode();
isLeftNode = true;
} else {
removingNode = removingNode.getRightNode();
isLeftNode = false;
}
if (removingNode == null) {
return;
}
}
// TODO
}
接著依序判斷上一節提及的三個刪除情況，進行不同的處理。以下的三個方法：removeLeafNode、removeNodeHavingOneChild 與 removeNodeHavingTwoChildren，筆者會逐一完成。
public void remove(int target) {
// 其餘略過
if (removingNode.getLeftNode() == null && removingNode.getRightNode() == null) {
removeLeafNode(parentOfRemovingNode, isLeftNode);
} else if (removingNode.getLeftNode() == null ^ removingNode.getRightNode() == null) {
removeNodeHavingOneChild(parentOfRemovingNode, isLeftNode);
} else {
removeNodeHavingTwoChildren(parentOfRemovingNode, isLeftNode);
}
}
（一）樹葉節點
當欲刪除節點沒有左、右節點，代表我們正在刪除樹葉節點。做法很簡單，只要知道 removingNode 位於父節點的左邊還是右邊，就可以將 parentOfRemovingNode 對應的指標指向 null。
private void removeLeafNode(TreeNode<Integer> parentOfRemovingNode, boolean isLeftNode) {
if (parentOfRemovingNode == null) {
this.rootNode = null;
} else if (isLeftNode) {
parentOfRemovingNode.setLeftNode(null);
} else {
parentOfRemovingNode.setRightNode(null);
}
}
（二）具有一個子節點
當欲刪除節點只有左節點或只有右節點，就符合這個情形。首先判斷要刪除的是否為根節點，是的話，就將其子節點取代到根節點位置即可。
private void removeNodeHavingOneChild(TreeNode<Integer> parentOfRemovingNode, boolean isLeftNode) {
if (parentOfRemovingNode == null) {
this.rootNode = isLeftNode
? this.rootNode.getLeftNode()
: this.rootNode.getRightNode();
return;
}
// TODO
}
若要刪除的不是根節點，則先透過 parentOfRemovingNode 得到欲刪除節點，再進而獲得取代用節點（replacingNode）。最後藉由 isLeftNode 來得知 removingNode 是左節點還是右節點，讓 parentOfRemovingNode 接上 replacingNode 就完成了。
private void removeNodeHavingOneChild(TreeNode<Integer> parentOfRemovingNode, boolean isLeftNode) {
// 其餘略過
TreeNode<Integer> removingNode = isLeftNode
? parentOfRemovingNode.getLeftNode()
: parentOfRemovingNode.getRightNode();
TreeNode<Integer> replacingNode = removingNode.getLeftNode() != null
? removingNode.getLeftNode()
: removingNode.getRightNode();
if (isLeftNode) {
parentOfRemovingNode.setLeftNode(replacingNode);
} else {
parentOfRemovingNode.setRightNode(replacingNode);
}
}
（三）具有兩個子節點
當欲刪除節點具有左節點或右節點，就符合這個情形。首先透過父節點得到欲刪除節點。
private void removeNodeHavingTwoChildren(TreeNode<Integer> parentOfRemovingNode, boolean isLeftNode) {
TreeNode<Integer> removingNode;
if (parentOfRemovingNode == null) {
removingNode = this.rootNode;
} else {
removingNode = isLeftNode
? parentOfRemovingNode.getLeftNode()
: parentOfRemovingNode.getRightNode();
}
// TODO
}
接著再從它獲得左子樹的最大值節點，或右子樹的最小值節點。為了做這件事，筆者設計了兩個方法，來得到這兩種節點的父節點。
private TreeNode<Integer> findParentOfMaxInLeftTree(TreeNode<Integer> node) {
TreeNode<Integer> parentNode = node;
TreeNode<Integer> visitedNode = node.getLeftNode();
while (visitedNode.getRightNode() != null) {
parentNode = visitedNode;
visitedNode = visitedNode.getRightNode();
}
return parentNode;
}
private TreeNode<Integer> findParentOfMinInRightTree(TreeNode<Integer> node) {
TreeNode<Integer> parentNode = node;
TreeNode<Integer> visitedNode = node.getRightNode();
while (visitedNode.getLeftNode() != null) {
parentNode = visitedNode;
visitedNode = visitedNode.getLeftNode();
}
return parentNode;
}
回到主要邏輯，我們有左子樹和右子樹兩個選擇。此處筆者優先考慮右子樹，並判斷是否存在後，將結果存放於布林值 isRemovingNodeHasRightNode。根據不同的判斷結果，可以拿到對應的取代用節點之父節點（parentOfReplacingNode）。有了它，再進一步得到取代用節點（replacingNode）。
然而，如果欲刪除節點的左節點已經是最大值，或右節點已經是最小值，則 parentOfReplacingNode 將會等於 removingNode。此時我們直接將子節點做為 replacingNode。
private void removeNodeHavingTwoChildren(TreeNode<Integer> parentOfRemovingNode, boolean isLeftNode) {
// 其餘略過
boolean isRemovingNodeHasRightNode = removingNode.getRightNode() != null;
TreeNode<Integer> parentOfReplacingNode;
TreeNode<Integer> replacingNode;
if (isRemovingNodeHasRightNode) {
parentOfReplacingNode = findParentOfMinInRightTree(removingNode);
replacingNode = parentOfReplacingNode == removingNode
? removingNode.getRightNode()
: parentOfReplacingNode.getLeftNode();
} else {
parentOfReplacingNode = findParentOfMaxInLeftTree(removingNode);
replacingNode = parentOfReplacingNode == removingNode
? removingNode.getLeftNode()
: parentOfReplacingNode.getRightNode();
}
// TODO
}
需要的節點都準備好後，最後就是處理指標了，筆者分成三個步驟。
- 若上述提到的 parentOfReplacingNode 不等於 removingNode 時，要讓 parentOfReplacingNode 接上 replacingNode 的子節點。
- 讓 replacingNode 接上與 removingNode 相同的子節點。
- 讓 parentOfRemovingNode 接上 replacingNode。
接著是第二步。為了讓 replacingNode 能取代到欲刪除節點的位置，replacingNode 的左右節點勢必要與 removingNode 相同。
private void removeNodeHavingTwoChildren(TreeNode<Integer> parentOfRemovingNode, boolean isLeftNode) {
// 其餘略過
if (parentOfReplacingNode != removingNode) {
if (isRemovingNodeHasRightNode) {
parentOfReplacingNode.setLeftNode(replacingNode.getRightNode());
} else {
parentOfReplacingNode.setRightNode(replacingNode.getLeftNode());
}
}
replacingNode.setLeftNode(removingNode.getLeftNode());
replacingNode.setRightNode(removingNode.getRightNode());
// TODO
}
最後是第三步。replacingNode 對子節點的指標已經處理好，這一步要讓上層的 parentOfRemovingNode 指向它。如果欲刪除節點不是根節點，我們直接根據它是左節點還是右節點，來決定 replacingNode 的擺放位置。否則只要將 replacingNode 取代到根節點的位置即可。
private void removeNodeHavingTwoChildren(TreeNode<Integer> parentOfRemovingNode, boolean isLeftNode) {
// 其餘略過
if (parentOfRemovingNode == null) {
this.rootNode = replacingNode;
} else {
if (isLeftNode) {
parentOfRemovingNode.setLeftNode(replacingNode);
} else {
parentOfRemovingNode.setRightNode(replacingNode);
}
}
}
以下是本文的完整程式碼：
https://gist.github.com/ntub46010/b4a4a15ffb85ab53558a7b80f4937e2f
留言
張貼留言