二叉樹
之前的一篇關于數(shù)組的鏈表中的文章中纽甘，我們說了鏈表是存儲在內存中是以一種邏輯上的鏈式結構，每個節(jié)點不僅存儲元素本身，還存儲了指向下一個節(jié)點的指針钉跷。二叉樹也是類似的一種結構，它也是由一個一個的節(jié)點組成肚逸，不同的是每個節(jié)點存儲著兩個指針爷辙，分別指向了另外兩個節(jié)點，這兩個節(jié)點通常被稱為"左孩子"和"右孩子"朦促，而前節(jié)點通常被稱為這兩個孩子的"父親"或者"父節(jié)點"膝晾。這些節(jié)點組成在一起被稱為二叉樹。
本文首發(fā)于心安-XinAnzzZ 的個人博客务冕，轉載請注明出處~
二分搜索樹
二分搜索樹也被稱為二分查找樹血当，它是基于二叉樹的一種樹形結構，它有著很鮮明的特點：
- 任意一個節(jié)點的左子樹中的所有節(jié)點都小于這個節(jié)點。
- 任意一個節(jié)點的右子樹中的所有節(jié)點都大于這個節(jié)點臊旭。
二分搜索樹除了是二叉樹以外落恼，就這兩個特點，請務必記住這個性質离熏。后面所有的對于節(jié)點的操作都要基于這個性質领跛。
代碼
新建 BinarySearchTree 類，以及用于表示節(jié)點的內部類撤奸，根據(jù)二分搜索樹的性質我們知道吠昭，節(jié)點存儲的元素必須具有可比性：
public class BinarySearchTree<E extends Comparable<E>> {
class Node {
// 分別記錄最孩子和右孩子
Node left, right;
E e;
Node(E e) {
this.e = e;
}
@Override
public String toString() {
return e.toString();
}
}
// 樹的根節(jié)點
private Node root;
// 樹的大小
private int size;
}
新增一個元素
所有的遞歸都是可以用循環(huán)來解決的，但是由于樹的特殊性胧瓜，樹的子樹仍然是一棵樹矢棚，所以使用遞歸來解決樹的問題是非常合適的。下面給出增加元素的遞歸和非遞歸兩種實現(xiàn)方式府喳，但后續(xù)的其他操作還是選擇更加簡單明了的遞歸寫法蒲肋。
/**
* 向樹中添加一個元素，若元素已存在钝满，則不插入 -- 非遞歸寫法
*/
public void add(E e) {
if (root == null) {
root = new Node(e);
size++;
return;
}
Node current = this.root;
for (; ; ) {
if (e.compareTo(current.e) < 0) {
if (current.left != null) {
current = current.left;
continue;
}
current.left = new Node(e);
size++;
return;
} else if (e.compareTo(current.e) > 0) {
if (current.right != null) {
current = current.right;
continue;
}
current.right = new Node(e);
size++;
return;
} else {
// 元素存在則不添加
return;
}
}
}
/**
* 向樹中添加一個節(jié)點兜粘，若元素已存在，則不插入 -- 遞歸寫法
*/
public void addRecursive(E e) {
root = addElement(root, e);
}
/**
* 向給定節(jié)點中添加元素 e弯蚜，返回節(jié)點的根
*
* @param node 要添加元素的節(jié)點
* @param e 要添加的元素
* @return 添加完成后的根節(jié)點
*/
private Node addElement(Node node, E e) {
if (node == null) {
size++;
return new Node(e);
}
if (e.compareTo(node.e) < 0) {
node.left = addElement(node.left, e);
} else {
node.right = addElement(node.right, e);
}
return node;
}
核心邏輯都是：如果新元素小于當前元素孔轴，就添加到以左孩子為根節(jié)點的左子樹中，如果新元素大于當前元素碎捺，就添加到以右孩子為根節(jié)點的右子樹中路鹰，以此循環(huán)，直到左孩子或者右孩子為空收厨，則直接放在左孩子或者右孩子的位置即可晋柱。必須理解遞歸的思想，后面的代碼幾乎全部都依賴遞歸的思想來完成诵叁。
查詢一個元素
/**
* 查詢是否包含元素 e
*/
public boolean contains(E e) {
return contains(root, e);
}
private boolean contains(Node node, E e) {
if (node == null) {
return false;
}
if (e.compareTo(node.e) < 0) {
return contains(node.left, e);
} else if (e.compareTo(node.e) > 0) {
return contains(node.right, e);
} else {
return true;
}
}
刪除元素
刪除元素的過程比較復雜雁竞，所以單獨拿出說。
在寫刪除元素的代碼之前拧额，我們先寫幾個輔助函數(shù)碑诉，分別是用于獲取樹中的最大值、最小值以及刪除樹中的最大值和最小值势腮。
獲取一棵樹中的最大節(jié)點和最小節(jié)點
根據(jù)前面我們說的二分搜索樹的性質可以知道联贩，最左邊的元素就是樹中最小的元素，最右邊的元素就是樹中的最大元素捎拯。
/**
* 從以 node 為根的二叉樹中找到元素值最小的節(jié)點
*/
private Node getMin(Node node) {
if (node == null) {
throw new IllegalArgumentException("根節(jié)點為空，不存在最小節(jié)點！");
}
while (node.left != null) {
node = node.left;
}
return node;
}
/**
* 從以 node 為根的二叉樹中找到元素值最大的節(jié)點
*/
private Node getMax(Node node) {
if (node == null) {
throw new IllegalArgumentException("根節(jié)點為空署照，不存在最大節(jié)點");
}
while (node.right != null) {
node = node.right;
}
return node;
}
刪除一棵樹中的最大節(jié)點和最小節(jié)點
根據(jù)上面的代碼我們可以發(fā)現(xiàn)祸泪，樹中的最小節(jié)點一定是在樹的最左邊，樹中的最大節(jié)點一定是在樹的最右邊建芙。那么如果刪除掉了最小節(jié)點没隘，這個節(jié)點的右子樹應該如何處理呢？最簡單的想法就是把右子樹整個直接放到被刪除的節(jié)點的位置禁荸，如下圖所示右蒲。根據(jù)二分搜索樹的性質，可以知道：
要刪除的節(jié)點 < 右子樹 2 < 根節(jié)點 < 右子樹 1
那么刪除之后仍然滿足二分搜索樹的性質赶熟，所以這么操作是合理的瑰妄。同樣的，刪除最大值的過程與下面的過程相反映砖，所以也應該是合理的间坐。
/**
* 從以 node 為根的二叉樹中刪除最小節(jié)點，返回新的二叉樹的根
*/
private Node removeMin(Node node) {
// 左子樹為空邑退，說明當前節(jié)點就是最小節(jié)點
if (node.left == null) {
size--;
// 直接返回右子樹即可竹宋，如果右子樹也為空，那么也是沒問題的
return node.right;
}
// 走到這里地技，說明左子樹不為空蜈七，則從左子樹中刪除最小元素，然后將刪除后的新的子樹掛在當前節(jié)點的左邊
node.left = removeMin(node.left);
return node;
}
/**
* 從以 node 為根的二叉樹中刪除最大節(jié)點莫矗，返回新的二叉樹的根
*/
private Node removeMax(Node node) {
if (node.right == null) {
size--;
return node.left;
}
return null;
}
要刪除的節(jié)點可能的四種情況
-
要刪除的節(jié)點左右子樹都為空宪潮。
這種情況其實涵蓋在第二種或者第三種情況中，所以可以不用討論趣苏。
-
要刪除的節(jié)點左子樹為空狡相。
這種情況就意味著要刪除的節(jié)點就是整個樹中最小的元素，直接使用上面已經(jīng)寫好的刪除最小元素的方法即可食磕。
-
要刪除的節(jié)點右子樹為空尽棕。
同理，這種情況直接使用刪除最大元素的方法即可彬伦。
-
要刪除的節(jié)點左右子樹都不為空滔悉。
這種情況就比較復雜，下面我們單獨來分析一下单绑。
左右子樹都不為空的情況
如上面所說回官，如果左子樹為空，則將右子樹放在被刪除的節(jié)點的位置搂橙；如果右子樹為空歉提，則將左子樹放在被刪除的節(jié)點的位置；但是左右都不為空如何處理呢？最簡單的想法肯定是苔巨，既然這個節(jié)點被刪除了版扩，那么久在兩個子樹中找到一個合適的節(jié)點來替代被刪除的節(jié)點的位置，這個合適的節(jié)點必須滿足一個條件侄泽，那就是替換之后生成的新的二叉樹仍然滿足二分搜索樹的性質礁芦。看下圖：
要刪除的節(jié)點為 node悼尾，pre 為 node 節(jié)點的左子樹中最大的節(jié)點柿扣，通常被稱為前驅（predecessor）和后繼（successor）。根據(jù)二分搜索樹的性質闺魏，我們可以得到此時樹中的節(jié)點的大小順序為：
左子樹除了pre以外的其他節(jié)點 < pre < node < suc < 右子樹除了suc以外其他節(jié)點
那么刪除掉 node 節(jié)點以后的順序為：
左子樹除了pre以外的其他節(jié)點 < pre < suc < 右子樹除了suc以外其他節(jié)點
可以發(fā)現(xiàn)未状，刪除掉 node 節(jié)點之后如果使用 pre 或者 suc 節(jié)點替代 node 節(jié)點都是仍然滿足二分搜索樹的性質的，而如果使用其他的節(jié)點是不滿足的舷胜，所以這個合適的節(jié)點就是 pre 或者 suc娩践，而實際上兩者實現(xiàn)起來區(qū)別并不是很大，本文就使用前驅(predecessor)的方式來舉例：
根據(jù)前面的分析烹骨，刪除元素的代碼如下：
/**
* 從樹中刪除元素 e
*/
public void remove(E e) {
root = remove(root, e);
}
/**
* 從已 node 為根的樹中刪除元素為 e 的節(jié)點翻伺，并且返回新的樹的根
*
* @param node 要刪除的樹的根節(jié)點
* @param e 要刪除的節(jié)點的元素
* @return 刪除后新的樹的根
*/
private Node remove(Node node, E e) {
if (node == null) {
throw new IllegalArgumentException("要刪除的元素不存在！");
}
// 如果要刪除的節(jié)點比當前節(jié)點小沮焕，說明要刪除的節(jié)點在左子樹中
if (e.compareTo(node.e) < 0) {
// 從左子樹刪除吨岭，并且將刪除后得到的新的樹掛在當前節(jié)點在左邊
node.left = remove(node.left, e);
// 返回刪除后的樹的根
return node;
}
// 要刪除的節(jié)點在右子樹中
if (e.compareTo(node.e)>0) {
// 從右子樹中刪除，并且將刪除后得到的新的子樹掛在當前節(jié)點的右邊
node.right = remove(node.right, e);
return node;
}
// 如果走到這里峦树，說明 e.compareTo(node.e) = true辣辫，即當前節(jié)點就是要刪除的節(jié)點
// 如果當前節(jié)點的左子樹為空，說明要刪除的節(jié)點是以（當前節(jié)點為根的子樹）中的最小值
if (node.left == null) {
return removeMin(node);
}
// 如果右子樹為空魁巩，說明要刪除的節(jié)點是（當前節(jié)點為根的子樹）中的最大值
if (node.right == null) {
return removeMax(node);
}
// 左右子樹都不為空急灭，找到前驅或者后繼來替代當前節(jié)點，這里使用前驅
Node predecessor = getMax(node.left);
// 將刪除前驅后的左子樹和右子樹掛在前驅上谷遂，并且返回前驅
predecessor.left = removeMax(node.left);
predecessor.right = node.right;
return predecessor;
}
完整示例代碼
以上面實現(xiàn)的二分搜索樹為基礎還可以實現(xiàn) Set 和 Map 結構葬馋，全部代碼詳見下面鏈接。
