二叉查找树（Binary Search Tree）是一种能将链表插入的灵活性和有序数组查找的高效性结合起来的算法。下面是实现BST各种方法的干货纯代码。
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
左、右子树也分别为二叉排序树
public class BST<K extends Comparable<K>, V> {
private Node root;
private class Node {
private K key;
private V value;
private Node left;
private Node right;
private int N;
public Node(K key, V value, int N) {
this.key = key;
this.value = value;
this.N = N;
}
}
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null)
return 0;
else
return x.N;
}
}public V get(K key) {
return get(root, key);
}
private V get(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp == 0)
return root.value;
else if (comp < 0)
return get(root.left, key);
else
return get(root.right, key);
} public void put(K key, V value) {
root = put(root, key, value);
}
private Node put(Node root, K key, V value) {
if (root == null)
return new Node(key, value, 1);
int comp = key.compareTo(root.key);
if (comp == 0)
root.value = value;
else if (comp < 0)
root.left = put(root.left, key, value);
else
root.right = put(root.right, key, value);
root.N = size(root.left) + size(root.right) + 1;
return root;
} public K min() {
return min(root).key;
}
private Node min(Node root) {
if (root.left == null)
return root;
return min(root.left);
} public K max() {
return max(root).key;
}
private Node max(Node root2) {
if (root.right == null)
return root;
return max(root.right);
} public K floor(K key) {
Node x = floor(root, key);
if (x == null)
return null;
return x.key;
}
private Node floor(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp < 0)
return floor(root.left, key);
else if (comp > 0 && root.right != null
&& key.compareTo(min(root.right).key) >= 0)
return floor(root.right, key);
else
return root;
} public K ceiling(K key) {
Node x = ceiling(root, key);
if (x == null)
return null;
return x.key;
}
private Node ceiling(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp > 0)
return ceiling(root.right, key);
else if (comp < 0 && root.left != null
&& key.compareTo(max(root.left).key) >= 0)
return ceiling(root.left, key);
else
return root;
} public K select(int k) {
//找出BST中序号为k的键
return select(root, k);
}
private K select(Node root, int k) {
if (root == null)
return null;
int comp = k - size(root.left);
if (comp < 0)
return select(root.left, k);
else if (comp > 0)
return select(root.right, k - (size(root.left) + 1));
else
return root.key;
} public int rank(K key) {
//找出BST中键为key的序号是多少
return rank(root, key);
}
private int rank(Node root, K key) {
if (root == null)
return 0;
int comp = key.compareTo(root.key);
if (comp == 0)
return size(root.left);
else if (comp < 0)
return rank(root.left, key);
else
return 1 + size(root.left) + rank(root.right, key);
} public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node root) {
if (root.left == null)
return root.right;
root.left = deleteMin(root.left);
root.N = size(root.left) + size(root.right) + 1;
return root;
} public void deleteMax() {
root = deleteMax(root);
}
private Node deleteMax(Node root) {
if (root.right == null)
return root.left;
root.right = deleteMax(root.right);
root.N = size(root.left) + size(root.right) + 1;
return root;
} public void delete(K key) {
root = delete(root, key);
}
private Node delete(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp == 0) {
if (root.right == null)
return root = root.left;
if (root.left == null)
return root = root.right;
Node t = root;
root = min(t.right);
root.left = t.left;
root.right = deleteMin(t.right);
} else if (comp < 0)
root.left = delete(root.left, key);
else
root.right = delete(root.right, key);
root.N = size(root.left) + size(root.right) + 1;
return root;
} public void print() {
print(root);
}
private void print(Node root) {
if (root == null)
return;
print(root.left);
System.out.println(root.key);
print(root.right);
}以上是java-二叉查找树（BST）算法的示例代码分享的详细内容。更多信息请关注PHP中文网其他相关文章！
