package demo;
import java.util.LinkedList;
/**
* 二分查找树
*
* @author Administrator
*
* @param <K>
* @param <V>
*/
public class BST<K extends Comparable<K>, V> {
private final static Node EmptyNode = null;
private Node head;
private int count;
private static class Node<K extends Comparable<K>, V> {
K key;
V value;
Node<K, V> left;
Node<K, V> right;
private Node(K key, V val) {
this.key = key;
this.value = val;
this.left = EmptyNode;
this.right = EmptyNode;
}
private Node(Node<K,V> node) {
this.key = node.key;
this.value = node.value;
this.left = node.left;
this.right = node.right;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{ ").append(key).append(":").append(value).append(" }");
return sb.toString();
}
}
public BST() {
head = EmptyNode;
count = 0;
}
public int size() {
return count;
}
public boolean isEmpty() {
return count == 0;
}
public void insert(K key, V val) {
checkArg(key, "key is null");
head = insert(head, key, val);
}
private Node<K, V> insert(Node<K, V> root, K key, V val) {
if (root == EmptyNode) {
count++;
return new Node<K, V>(key, val);
}
if (root.key.compareTo(key) > 0)
root.left = insert(root.left, key, val);
else if (root.key.compareTo(key) < 0)
root.right = insert(root.right, key, val);
else
root.value = val;
return root;
}
public V search(K key) {
return (V) search(head, key);
}
private V search(Node<K, V> root, K key) {
checkArg(key, "key is null");
if (root == EmptyNode)
return null;
if (root.key.compareTo(key) == 0)
return root.value;
else if (root.key.compareTo(key) > 0)
return (V) search(root.left, key);
else
return (V) search(root.right, key);
}
public void preOrder() {
preOrder(head);
}
private void preOrder(Node root) {
if (root == EmptyNode)
return;
System.out.print(root);
preOrder(root.left);
preOrder(root.right);
}
public void midOrder() {
midOrder(head);
}
private void midOrder(Node root) {
if (root == EmptyNode)
return;
midOrder(root.left);
System.out.print(root);
midOrder(root.right);
}
public void postOrder() {
postOrder(head);
}
private void postOrder(Node root) {
if (root == EmptyNode)
return;
postOrder(root.left);
postOrder(root.right);
System.out.println(root);
}
private void checkArg(Object key, String thrStr) {
if (key == null)
throw new IllegalArgumentException(thrStr);
}
public void levelOrder() {
if (head == EmptyNode)
return;
LinkedList<Node> ll = new LinkedList();
ll.addLast(head);
while (!ll.isEmpty()) {
Node node = ll.removeFirst();
System.out.println(node);
if (node.left != EmptyNode)
ll.addLast(node.left);
if (node.right != EmptyNode)
ll.addLast(node.right);
}
}
public K getMinNode() {
checkArg(head, "this tree is empty!!");
return (K) getMinNode(head).key;
}
private Node getMinNode(Node root) {
if (root.left == EmptyNode)
return root;
return getMinNode(root.left);
}
public K getMaxNode() {
checkArg(head, "this tree is empty!!");
return (K) getMaxNode(head).key;
}
private Node<K, V> getMaxNode(Node<K, V> root) {
if (root.right == EmptyNode)
return root;
return getMaxNode(root.right);
}
public void removeMin() {
checkArg(head, "the tree is empty");
head = removeMin(head);
}
private Node removeMin(Node root) {
if (root.left == EmptyNode) {
Node rightNode = root.right;
root = EmptyNode;
count--;
return rightNode;
}
root.left = removeMin(root.left);
return root;
}
public void removeMax() {
checkArg(head, "the tree is empty");
head = removeMax(head);
}
private Node removeMax(Node root) {
if (root.right == EmptyNode) {
Node leftNode = root.left;
root = null;
count--;
return leftNode;
}
root.right = removeMax(root.right);
return root;
}
public void remove(K key) {
head = remove(head, key);
}
private Node remove(Node root, K key) {
if(root ==EmptyNode) return null;
if (root.key.compareTo(key) < 0) {//
root.right = remove(root.right, key);
return root;
} else if (root.key.compareTo(key) > 0) {
root.left = remove(root.left, key);
return root;
} else {// equal
if(root.left ==EmptyNode) {//没有左节点
Node rightNode = root.right;
root=EmptyNode;
count--;
return rightNode;
}
if(root.right == EmptyNode) {//没有右节点
Node leftNode = root.right;
root=EmptyNode;
count--;
return leftNode;
}
//左右节点都存在
Node min = getMinNode(root.right);
Node s = new Node<K, V>(min);
s.right = removeMin(root.right);
s.left = root.left;
return s;
}
}
public static void main(String[] args) {
BST<Integer, Object> bst = new BST();
bst.insert(1, "hello");
bst.insert(10, "hello");
bst.insert(9, "hello");
bst.insert(20, "hello");
bst.insert(11, "hello");
bst.insert(14, "hello");
bst.insert(90, "hello");
bst.insert(25, "hello");
bst.midOrder();
bst.remove(10);
System.out.println("");
bst.midOrder();
}
}
网友评论