package practice; public class TestMain {
public static void main(String[] args) {
int[] ao = {50,18,97,63,56,3,71,85,54,34,9,62,45,94,66,65,7,19,22,86};
Integer[] a = new Integer[20];
for (int i = 0; i < a.length; i++) {
a[i] = new Integer(ao[i]);
}
BinarySortTree<Integer, String> tree = new BinarySortTree<Integer, String>();
for (int i = 0; i < a.length; i++) {
tree.put(a[i], a[i].toString());
}
/*tree.delete(3);
System.out.println("min = "+tree.min()+" max = "+tree.max());
tree.delete(97);
System.out.println("min = "+tree.min()+" max = "+tree.max());
tree.delete(19);
tree.delete(18);
tree.delete(85);
System.out.println();
tree.delete(99);*/ }
}
/*
* 二叉查找树及其操作的递归实现
* 二叉查找树:左节点比根节点小,左节点比根节点大。
*/
class BinarySortTree<K extends Comparable<K>, V>{ Node root;
/*
* Node结点类
*/
class Node{
private Node left, right; //左右子树
private K key;
private V value;
private int N; //节点所在树的子节点数(包括自己) private Node(K key, V value) {
this.key = key;
this.value = value;
this.N = 1;
} public K getKey() {
return key;
}
}
/*
* 插入新节点
* O(lgn)
*/
public void put(K key, V value) {
root = put(key, value, root);
} private Node put(K key, V value, Node node) {
if (node == null) { return new Node(key, value);} if (compare(key, node.key) == 0) { node.value = value;} //如果key相等则更新值
else if (compare(key, node.key) < 0) { node.left = put(key, value, node.left);} //进入左子树
else if (compare(key, node.key) > 0) { node.right = put(key, value, node.right);} //进入右子树
node.N = size(node.left) + size(node.right) + 1; //子节点数 return node;
}
/*
* 查找
*/
public V get(K key) {
return get(key, root);
} private V get(K key, Node node) {
if (node == null) { return null;} if (compare(key, node.key) < 0) { return get(key, node.left);}
else if (compare(key, node.key) > 0) { return get(key, node.right);}
else { return node.value;} //递归结束条件,找到key
}
/*
* 获取最大最小值
*/
public K min() {
return min(root).key;
} private Node min(Node node) {
if (node.left == null) { return node;}
else { return min(node.left);}
} public K max() {
return max(root).key;
} private Node max(Node node) {
if (node.right == null) { return node;}
else { return max(node.right);}
}
/*
* 获取键的排名
*/
public int rank(K key) {
return rank(key, root);
} private int rank(K key, Node node) {
if (node == null) { return 0;} //键不存在返回0 if (compare(key, node.key) < 0) { return rank(key, node.left);}
else if (compare(key, node.key) > 0) { return size(node.left) + 1 + rank(key, node.right);}
//当查找进入右子树时,加上同级左子树的大小,再加1(父节点本身)
else { return size(node.left);} //该节点左子树的大小(它的左子树的key全部比它小)
}
/*
* 根据排名获取键
*/
public Node select(int N) {
return select(N, root);
} private Node select(int N, Node node) { int t = size(node.left) + 1; //获取当前节点在以它为根节点的树中的排名(从1开始排)
if (N < t) { return select(N, node.left);} //与当前排名比较,选择进入左子树还是右子树
else if (N > t) { return select(N - t, node.right);}
//进入右子树时,右子树所有的节点的排名都要加上"同级左子树的大小,再加1(父节点本身)",所以 N - t
else { return node;}
}
/*
* 删除最小键
*/
public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node node) {
if (node.left == null) { return node.right;} //将最小节点的右子树连在他的父节点上即将它删除
node.left = deleteMin(node.left);
node.N = size(node.left) + size(node.right) + 1; //更新树的大小
return node;
}
/*
* 删除指定键
*/
public void delete(K key) {
root = delete(key, root);
}
private Node delete(K key, Node node) {
if (node == null) { return null;} //找不到键,不做任何处理,原样返回 if (compare(key, node.key) < 0) { node.left = delete(key, node.left);} //向左向右找
else if (compare(key, node.key) > 0) { node.right = delete(key, node.right);}
else {
if (node.right == null) { return node.left;} //如果要删的节点有一边时null,直接把另一条子树连到父节点上
if (node.left== null) { return node.right;}
/*Node tnode = min(node.right);
node.right = deleteMin(node.right);
tnode.left = node.left;
tnode.right = node.right;
tnode.N = size(tnode.left) + size(tnode.right) + 1;
return tnode;*/
//上下两段代码实现了同样的功能,充分体现了差距
Node tnode = node; //将右子树中的最小值(后继节点)连到父节点上,或左子树中的最大值(前趋节点)也可以
node = min(tnode.right);
node.right = deleteMin(tnode.right); //把将要连到父节点上的那个后继节点在当前位置删除
node.left = tnode.left; //更新左右子树
} node.N = size(node.left) + size(node.right) + 1; //更新树的大小
return node;
}
/*
* key1 < key2 -1
* key1 > key2 1
* key1 == key2 0
*/
private int compare(K key1, K key2) {
return key1.compareTo(key2);
} private int size(Node node) {
if (node == null) { return 0;}
else { return node.N;}
} /*
* 中序遍历
*/
public void print(Node node) {
if (node == null) {
return;
}
print(node.left);
System.out.print(node.key+" ");
print(node.right);
}
}
算法动态演示
http://www.cs.usfca.edu/~galles/visualization/BST.html