之前整理了兩篇關于二叉樹的文章：
這兩篇都是基于二叉樹，以及一些練習題，本篇主要對二叉查找樹做一個實現(xiàn)，即增刪改查，實際上二叉查找樹也很容易理解，滿足的條件就是左子節(jié)點的值小于根節(jié)點，右子節(jié)點的值大于根節(jié)點。
代碼實現(xiàn)
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）添加時，就是遍歷樹，比根節(jié)點大，轉到到右邊，比根節(jié)點小，轉到左邊，這樣遍歷到最后就找到了添加的位置
（2）刪除時需要先找到需要刪除的節(jié)點，即和要刪除的值相同的節(jié)點，找到之后，分為兩種情況，一種是只有左子節(jié)點或者只有又子節(jié)點或者沒有子節(jié)點，刪除節(jié)點后，如果有子節(jié)點，子節(jié)點代替根節(jié)點，沒有子節(jié)點，根節(jié)點就為空；第二種是需要刪除的節(jié)點有左子節(jié)點和右子節(jié)點，這時候需要找到右邊樹的中最小的節(jié)點，將這個節(jié)點的值賦給待刪除的根節(jié)點，然后就變成刪除右邊樹的中最小的節(jié)點，變成了第一種情況，按照第一種情況處理即可。
