二叉查找树
之前整理了两篇关于二叉树的文章：
这两篇都是基于二叉树，以及一些练习题，本篇主要对二叉查找树做一个实现，即增删改查，实际上二叉查找树也很容易理解，满足的条件就是左子节点的值小于根节点，右子节点的值大于根节点。
代码实现
public class BinarySearchTree<T extends Comparable<? super T>> {
private Node<T> root;
private static class Node<T> {
public T data;
public Node<T> left;
public Node<T> right;
public Node() {
}
public Node(T data) {
this.data = data;
}
}
public boolean isEmpty() {
return root == null;
}
public boolean contains(T value) {
return contains(value, root);
}
private boolean contains(T value, Node<T> root) {
if (root == null) {
return false;
}
int result = root.data.compareTo(value);
if (result == 0) {
return true;
} else if (result < 0) {
return contains(value, root.right);
} else {
return contains(value, root.left);
}
}
public void insert(T value) {
root = insert(root, value);
}
private Node<T> insert(Node<T> root, T value) {
if (root == null) {
return new Node<>(value);
}
Node<T> node = new Node<>();
node.data = value;
int result = root.data.compareTo(value);
if (result > 0) {
root.left = insert(root.left, value);
return root;
} else if (result < 0) {
root.right = insert(root.right, value);
return root;
} else {
return root;
}
}
public boolean remove(T value) {
return remove(root, value) != null;
}
private Node<T> remove(Node<T> root, T value) {
if (root == null) {
return null;
}
int result = root.data.compareTo(value);
if (result == 0) {
if (root.left != null && root.right != null) {
Node<T> node = findMin(root.right);
root.data = node.data;
root.right = remove(root.right, node.data);
}
root = root.left == null ? root.right : root.left;
} else if (result > 0) {
root.left = remove(root.left, value);
} else {
root.right = remove(root.right, value);
}
return root;
}
public T findMax() {
Node<T> max = findMax(root);
if (max == null) {
return null;
}
return max.data;
}
private Node<T> findMax(Node<T> root) {
if (root == null) {
return null;
}
if (root.right != null) {
return findMax(root.right);
}
return root;
}
public T findMin() {
Node<T> minNode = findMin(root);
if (minNode == null) {
return null;
}
return minNode.data;
}
private Node<T> findMin(Node<T> root) {
if (root == null) {
return null;
}
if (root.left != null) {
return findMin(root.left);
}
return root;
}
}
主要的操作就是添加和删除：
（1）添加时，就是遍历树，比根节点大，转到到右边，比根节点小，转到左边，这样遍历到最后就找到了添加的位置
（2）删除时需要先找到需要删除的节点，即和要删除的值相同的节点，找到之后，分为两种情况，一种是只有左子节点或者只有又子节点或者没有子节点，删除节点后，如果有子节点，子节点代替根节点，没有子节点，根节点就为空；第二种是需要删除的节点有左子节点和右子节点，这时候需要找到右边树的中最小的节点，将这个节点的值赋给待删除的根节点，然后就变成删除右边树的中最小的节点，变成了第一种情况，按照第一种情况处理即可。
