数据结构（二）-- 二叉树与二分搜索树
二叉树
之前的一篇关于数组的链表中的文章中，我们说了链表是存储在内存中是以一种逻辑上的链式结构，每个节点不仅存储元素本身，还存储了指向下一个节点的指针。二叉树也是类似的一种结构，它也是由一个一个的节点组成，不同的是每个节点存储着两个指针，分别指向了另外两个节点，这两个节点通常被称为"左孩子"和"右孩子"，而前节点通常被称为这两个孩子的"父亲"或者"父节点"。这些节点组成在一起被称为二叉树。
本文首发于心安-XinAnzzZ 的个人博客，转载请注明出处~
二分搜索树
二分搜索树也被称为二分查找树，它是基于二叉树的一种树形结构，它有着很鲜明的特点：
- 任意一个节点的左子树中的所有节点都小于这个节点。
- 任意一个节点的右子树中的所有节点都大于这个节点。
二分搜索树除了是二叉树以外，就这两个特点，请务必记住这个性质。后面所有的对于节点的操作都要基于这个性质。
二分搜索树
代码
新建 BinarySearchTree 类，以及用于表示节点的内部类，根据二分搜索树的性质我们知道，节点存储的元素必须具有可比性：
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();
}
}
// 树的根节点
private Node root;
// 树的大小
private int size;
}
新增一个元素
所有的递归都是可以用循环来解决的，但是由于树的特殊性，树的子树仍然是一棵树，所以使用递归来解决树的问题是非常合适的。下面给出增加元素的递归和非递归两种实现方式，但后续的其他操作还是选择更加简单明了的递归写法。
/**
* 向树中添加一个元素，若元素已存在，则不插入 -- 非递归写法
*/
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;
}
}
}
/**
* 向树中添加一个节点，若元素已存在，则不插入 -- 递归写法
*/
public void addRecursive(E e) {
root = addElement(root, e);
}
/**
* 向给定节点中添加元素 e，返回节点的根
*
* @param node 要添加元素的节点
* @param e 要添加的元素
* @return 添加完成后的根节点
*/
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;
}
核心逻辑都是：如果新元素小于当前元素，就添加到以左孩子为根节点的左子树中，如果新元素大于当前元素，就添加到以右孩子为根节点的右子树中，以此循环，直到左孩子或者右孩子为空，则直接放在左孩子或者右孩子的位置即可。必须理解递归的思想，后面的代码几乎全部都依赖递归的思想来完成。
查询一个元素
/**
* 查询是否包含元素 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;
}
}
删除元素
删除元素的过程比较复杂，所以单独拿出说。
在写删除元素的代码之前，我们先写几个辅助函数，分别是用于获取树中的最大值、最小值以及删除树中的最大值和最小值。
获取一棵树中的最大节点和最小节点
根据前面我们说的二分搜索树的性质可以知道，最左边的元素就是树中最小的元素，最右边的元素就是树中的最大元素。
/**
* 从以 node 为根的二叉树中找到元素值最小的节点
*/
private Node getMin(Node node) {
if (node == null) {
throw new IllegalArgumentException("根节点为空，不存在最小节点！");
}
while (node.left != null) {
node = node.left;
}
return node;
}
/**
* 从以 node 为根的二叉树中找到元素值最大的节点
*/
private Node getMax(Node node) {
if (node == null) {
throw new IllegalArgumentException("根节点为空，不存在最大节点");
}
while (node.right != null) {
node = node.right;
}
return node;
}
删除一棵树中的最大节点和最小节点
根据上面的代码我们可以发现，树中的最小节点一定是在树的最左边，树中的最大节点一定是在树的最右边。那么如果删除掉了最小节点，这个节点的右子树应该如何处理呢？最简单的想法就是把右子树整个直接放到被删除的节点的位置，如下图所示。根据二分搜索树的性质，可以知道：
要删除的节点 < 右子树 2 < 根节点 < 右子树 1
那么删除之后仍然满足二分搜索树的性质，所以这么操作是合理的。同样的，删除最大值的过程与下面的过程相反，所以也应该是合理的。
2018-12-21-data-structure-BinarySearchTree-02.jpg
/**
* 从以 node 为根的二叉树中删除最小节点，返回新的二叉树的根
*/
private Node removeMin(Node node) {
// 左子树为空，说明当前节点就是最小节点
if (node.left == null) {
size--;
// 直接返回右子树即可，如果右子树也为空，那么也是没问题的
return node.right;
}
// 走到这里，说明左子树不为空，则从左子树中删除最小元素，然后将删除后的新的子树挂在当前节点的左边
node.left = removeMin(node.left);
return node;
}
/**
* 从以 node 为根的二叉树中删除最大节点，返回新的二叉树的根
*/
private Node removeMax(Node node) {
if (node.right == null) {
size--;
return node.left;
}
return null;
}
要删除的节点可能的四种情况
-
要删除的节点左右子树都为空。
这种情况其实涵盖在第二种或者第三种情况中，所以可以不用讨论。
-
要删除的节点左子树为空。
这种情况就意味着要删除的节点就是整个树中最小的元素，直接使用上面已经写好的删除最小元素的方法即可。
-
要删除的节点右子树为空。
同理，这种情况直接使用删除最大元素的方法即可。
-
要删除的节点左右子树都不为空。
这种情况就比较复杂，下面我们单独来分析一下。
左右子树都不为空的情况
如上面所说，如果左子树为空，则将右子树放在被删除的节点的位置；如果右子树为空，则将左子树放在被删除的节点的位置；但是左右都不为空如何处理呢？最简单的想法肯定是，既然这个节点被删除了，那么久在两个子树中找到一个合适的节点来替代被删除的节点的位置，这个合适的节点必须满足一个条件，那就是替换之后生成的新的二叉树仍然满足二分搜索树的性质。看下图：
2018-12-21-data-structure-BinarySearchTree-03.jpg
要删除的节点为 node，pre 为 node 节点的左子树中最大的节点，通常被称为前驱（predecessor）和后继（successor）。根据二分搜索树的性质，我们可以得到此时树中的节点的大小顺序为：
左子树除了pre以外的其他节点 < pre < node < suc < 右子树除了suc以外其他节点
那么删除掉 node 节点以后的顺序为：
左子树除了pre以外的其他节点 < pre < suc < 右子树除了suc以外其他节点
可以发现，删除掉 node 节点之后如果使用 pre 或者 suc 节点替代 node 节点都是仍然满足二分搜索树的性质的，而如果使用其他的节点是不满足的，所以这个合适的节点就是 pre 或者 suc，而实际上两者实现起来区别并不是很大，本文就使用前驱(predecessor)的方式来举例：
2018-12-21-data-structure-BinarySearchTree-03.jpg
根据前面的分析，删除元素的代码如下：
/**
* 从树中删除元素 e
*/
public void remove(E e) {
root = remove(root, e);
}
/**
* 从已 node 为根的树中删除元素为 e 的节点，并且返回新的树的根
*
* @param node 要删除的树的根节点
* @param e 要删除的节点的元素
* @return 删除后新的树的根
*/
private Node remove(Node node, E e) {
if (node == null) {
throw new IllegalArgumentException("要删除的元素不存在！");
}
// 如果要删除的节点比当前节点小，说明要删除的节点在左子树中
if (e.compareTo(node.e) < 0) {
// 从左子树删除，并且将删除后得到的新的树挂在当前节点在左边
node.left = remove(node.left, e);
// 返回删除后的树的根
return node;
}
// 要删除的节点在右子树中
if (e.compareTo(node.e)>0) {
// 从右子树中删除，并且将删除后得到的新的子树挂在当前节点的右边
node.right = remove(node.right, e);
return node;
}
// 如果走到这里，说明 e.compareTo(node.e) = true，即当前节点就是要删除的节点
// 如果当前节点的左子树为空，说明要删除的节点是以（当前节点为根的子树）中的最小值
if (node.left == null) {
return removeMin(node);
}
// 如果右子树为空，说明要删除的节点是（当前节点为根的子树）中的最大值
if (node.right == null) {
return removeMax(node);
}
// 左右子树都不为空，找到前驱或者后继来替代当前节点，这里使用前驱
Node predecessor = getMax(node.left);
// 将删除前驱后的左子树和右子树挂在前驱上，并且返回前驱
predecessor.left = removeMax(node.left);
predecessor.right = node.right;
return predecessor;
}
完整示例代码
以上面实现的二分搜索树为基础还可以实现 Set 和 Map 结构，全部代码详见下面链接。
