什么是二叉搜索树

二叉搜索树(Binary Search Tree)，是最基础，且相对简单的一种数据结构，支持Insert，Delete，Search，Min，Max，Successor，Predecessor等操作。最大的特点是每一个节点有不超过两个子节点，并且左子节点小于或者等于父节点，而右节点大于或者等于父节点。说它基础，是因为很多其它树形数据结构以它为原型而扩展，比如红黑树，B树。

相关阅读：

具体实现

public class BinaryTree> {
private Node root;

public void insert(T element) {
if (element == null) {
throw new IllegalArgumentException("element can not be null");
}

if (root == null) {
root = new Node(null, element);
} else {
Node node = root;
while (true) {
if (element.compareTo(node.value) <= 0) {
if (node.left == null) {
Node newNode = new Node(node, element);
node.left = newNode;
break;
} else {
node = node.left;
}
} else {
if (node.right == null) {
Node newNode = new Node(node, element);
node.right = newNode;
break;
} else {
node = node.right;
}
}
}
}
}

private int childCount(Node node) {
if (node == null) {
throw new IllegalArgumentException("node can not be null");
}

int count = 0;

if (node.left != null) {
count++;
}

if (node.right != null) {
count++;
}

return count;
}

public void delete(Node node) {
if (node == null) {
throw new IllegalArgumentException("node can not be null");
}

int childCount = childCount(node);
Node parentNode = node.parent;

if (childCount == 0) {
if (parentNode == null) {
// node is root
root = null;
} else {
if (node == parentNode.left) {
parentNode.left = null;
} else {
parentNode.right = null;
}
}
} else if (childCount == 1) {
if (parentNode == null) {
// node is root, set child of node to be new root
if (node.left != null) {
root = node.left;
node.left.parent = null;
} else {
root = node.right;
node.right.parent = null;
}
} else {
if (node == parentNode.left) {
if (node.left != null) {
parentNode.left = node.left;
node.left.parent = parentNode;
} else {
parentNode.left = node.right;
node.right.parent = parentNode;
}
} else {
if (node.left != null) {
parentNode.right = node.left;
node.left.parent = parentNode;
} else {
parentNode.right = node.right;
node.right.parent = parentNode;
}
}
}
} else {
// successor has no left child
Node successor = min(node);

if (successor != node.right) {
transplant(successor, successor.right);

successor.right = node.right;
node.right.parent = successor;
}

transplant(node, successor);

successor.left = node.left;
node.left.parent = successor;
}
}

private void transplant(Node u, Node v) {
if (u == null) {
throw new IllegalArgumentException("node can not be null");
}

if (u.parent == null) {
root = v;
} else if (u == u.parent.left) {
u.parent.left = v;
} else {
u.parent.right = v;
}

if (v != null) {
v.parent = u.parent;
}
}

public Node search(T element) {
if (element == null) {
throw new IllegalArgumentException("element can not be null");
}

Node node = root;
while (node != null) {
if (node.value.equals(element)) {
return node;
} else if (element.compareTo(node.value) < 0) {
node = node.left;
} else {
node = node.right;
}
}

return null;
}

public Node min(Node rootNode) {
if (rootNode == null) {
throw new IllegalArgumentException("node can not be null");
}

Node node = rootNode;
while (node.left != null) {
node = node.left;
}

return node;
}

public Node min() {
if (root != null) {
return min(root);
} else {
return null;
}
}