一、准备知识
二叉搜索树，英文名称Binary Search Tree，又叫二叉查找树，二叉排序树。特点是：任意一个节点的值都大于其左子树所有节点的值；任意一个节点的值都小于其右子树所有节点的值；左右子树也是一棵二叉搜索树；存储的元素不允许为空。
二叉搜索树存储的元素必须具备可比较性。如果是自定义类型，需要指定比较规则。二叉搜索树的元素的比较，可以利用Comparable接口和Compartor接口。java的jdk中内置的Integer、Double等包装类以及String类都实现了Comparable接口，因此元素类型如果是这些的话，是具有默认比较的规则的。
删除操作需要用到前驱节点或后继节点。二叉树的前驱节点是指中序遍历时该节点的前一个节点，而二叉搜索树的前驱节点，就是前一个比它小的节点。1、如果当前节点的左子树不为空，它的前驱就是左子树的最大节点，也即是左子树的最右边的节点；2、如果当前节点的左子树为空，且它的父节点不为空，找前驱节点就是一直向上找父节点，直到找到比它小的父节点；3、如果当前节点的左子树为空，父节点也为空，那就没有前驱节点。同理，二叉搜索树的后继节点，就是后一个比它大的节点。
二、添加节点
如果二叉搜索树为空树，那么添加的节点就是根节点；如果二叉搜索树不是空树，即添加的节点不是第一个节点，那么需要找到父节点，然后根据比较规则决定添加到父节点的左子树还是右子树的位置。下面通过代码进行说明。
package wjun.blog.binarytree.traversal.searchtree;
import java.util.Comparator;
/**
* @author Wjun
*/
public class BinarySearchTree<E> {
private int size;
private Node<E> root;
//比较方式一：在二叉搜索树内部传递一个比较器，用于定义比较规则
private Comparator<E> comparator;
public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}
public BinarySearchTree() {
//不传比较器，就是比较器为null
this(null);
}
private class Node<E> {
E element;
Node<E> parent;
Node<E> left;
Node<E> right;
public Node(E element, Node<E> parent) {
this.element = element;
this.parent = parent;
}
}
/*
* 比较规则：返回值=0，表示e1和e2相等；返回值>0，表示e1>e2
* */
private int compare(E e1, E e2) {
//比较器不为空
//比较方式一：在二叉搜索树内部传递一个比较器，用于定义比较规则
if (comparator != null) {
return comparator.compare(e1, e2);
}
//如果代码执行到这里，说明比较器为空。
// 那就用比较方式二：强制使用Comparable接口进行比较
return ((Comparable<E>)e1).compareTo(e2);
}
public void add(E element) {
//首先进行参数检查
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
//添加元素，如果二叉搜索树为空，就是添加root
if (root == null) {
root = new Node<E>(element, null);
size++;
return;
}
//如果二叉搜索树不为空，添加的元素不在根节点，需要找到父节点
//怎么找到父节点？从根节点开始，依次比较
Node<E> node = root;
Node<E> parent = root;
int cmp = 0;//需要记录最后一次的值，用以判断添加的节点在父节点的左还是右
while (node != null) {
cmp = compare(element, node.element);
parent = node;//向左子树或向右子树找之前，保存的这个节点就是父节点
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else {
node.element = element;//让相等的元素覆盖，也可以什么都不做
}
}
//找到父节点之后，就是判断将节点添加到左子树还是右子树
Node<E> newNode = new Node<>(element, parent);
if (cmp >0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
}
}
三、删除节点
删除节点的时候，需要判断所删除的节点的度为2还是为0或1。1、如果删除的节点是叶子节点即度为0，就让该节点的父节点指向空；2、如果删除的节点是度为1的节点，就用它的子节点代替原节点的位置；3、如果删除的节点是度为2的节点，需要先用前驱或者后继节点的值覆盖原节点，然后删除相应的前驱或后继节点。下面是具体的代码，代码中度为2的节点我们用后继节点覆盖，如果选择前驱节点覆盖原理是一样的。
package wjun.blog.binarytree.traversal.searchtree;
import java.util.Comparator;
/**
* @author Wjun
*/
public class BinarySearchTree<E> {
private int size;
private Node<E> root;
//比较方式一：在二叉搜索树内部传递一个比较器，用于定义比较规则
private Comparator<E> comparator;
public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}
public BinarySearchTree() {
//不传比较器，就是比较器为null
this(null);
}
private class Node<E> {
E element;
Node<E> parent;
Node<E> left;
Node<E> right;
public Node(E element, Node<E> parent) {
this.element = element;
this.parent = parent;
}
}
/*
* 比较规则：返回值=0，表示e1和e2相等；返回值>0，表示e1>e2
* */
private int compare(E e1, E e2) {
//比较器不为空
//比较方式一：在二叉搜索树内部传递一个比较器，用于定义比较规则
if (comparator != null) {
return comparator.compare(e1, e2);
}
//如果代码执行到这里，说明比较器为空。
// 那就用比较方式二：强制使用Comparable接口进行比较
return ((Comparable<E>)e1).compareTo(e2);
}
/*
* 找前驱节点
* */
private Node<E> predecessor(Node<E> node) {
if (node == null) return null;
//在左子树中寻找前驱节点
Node<E> p = node.left;
if (p != null) {
//如果左子树不为空，前驱就是左子树最右边的节点node.left.right.right...
while(p.right != null) {
p = p.right;
}
return p;
}
//如果左子树为空，且它的父节点不为空，就一直向上找父节点，知道找到比它小的父节点
while(node.parent != null && node == node.parent.left) {
node = node.parent;
}
return node.parent;
}
/*
* 找后继节点
* */
private Node<E> successor(Node<E> node) {
if (node == null) return null;
Node<E> s = node.right;
if (s != null) {
while(s.left != null) {
s = s.left;
}
return s;
}
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
/*根据元素找到节点对象*/
private Node<E> node(E element) {
Node<E> node = root;
while (node != null) {
int cmp = compare(element, node.element);
if (cmp == 0) return node;
if (cmp > 0) {
node = node.right;
} else {
node = node.left;
}
}
return null;
}
public void remove(E element) {
remove(node(element));
}
private void remove(Node<E> node){//度为2的节点
if (node == null) return;
size--;
if (node.left != null && node.right != null) {
Node<E> s = successor(node);
//用后继节点的值覆盖度为2的节点的值
node.element = s.element;
//删除后继节点,度为1或0
node = s;
}
//删除node节点（此node节点度必然为1或0）
Node<E> replacement = node.left != null ? node.left : node.right;
if (replacement != null) {
//node是度为1的节点
//更改parent
replacement.parent = node.parent;
//更改parent.left或parent.right的指向
if (node.parent == null) {
//node是度为1并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else if (node == node.parent.right) {
node.parent.right = replacement;
}
} else if(node == root) {
//node是叶子节点并且是根节点
root = null;
} else {
//node是叶子节点但不是根节点
if (node == node.parent.left) {
node.parent.left = null;
} else {
node.parent.right = null;
}
}
}
}
