package com.citi.tree;
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
private static class BinaryNode<AnyType> {
AnyType element;
BinaryNode<AnyType> left;
BinaryNode<AnyType> right;
BinaryNode(AnyType theElement) {
this(theElement, null, null);
}
BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt) {
element = theElement;
left = lt;
right = rt;
}
}
private static class UnderflowException extends RuntimeException {
public UnderflowException (String message) {
super(message);
}
}
private BinaryNode<AnyType> root;
public BinarySearchTree() {
root = null;
}
public void makeEmpty() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public boolean contains(AnyType x) {
return contains(x, root);
}
private boolean contains(AnyType x, BinaryNode<AnyType> t) {
if (t == null)
return false;
int compareResult = x.compareTo(t.element);
if (compareResult < 0)
return contains(x, t.left);
else if (compareResult > 0)
return contains(x, t.right);
else
return true; //Match
}
public AnyType findMin() {
if (isEmpty())
throw new UnderflowException("BinaryTree is empty");
return findMin(root).element;
}
private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
if (t == null)
return null;
else if (t.left == null)
return t;
return findMin(t.left);
}
public AnyType findMax() {
if (isEmpty())
throw new UnderflowException("BinaryTree is empty");
return findMax(root).element;
}
/*private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
if (t == null)
return null;
else if (t.right == null)
return t;
return findMax(t.right);
}*/
private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
if (t != null)
while (t.right != null)
t = t.right;
return t;
}
public void insert(AnyType x) {
root = insert(x, root);
}
private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
if (t == null)
return new BinaryNode<AnyType> (x, null, null);
int compareResult = x.compareTo(t.element);
if (compareResult < 0)
t.left = insert(x, t.left);
else if (compareResult > 0)
t.right = insert(x, t.right);
else ; // Duplicate; do nothing;
return t;
}
private void remove(AnyType x) {
root = remove(x, root);
}
private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
if (t == null)
return t; // Item not found; do nothing;
int compareResult = x.compareTo(t.element);
if (compareResult < 0)
t.left = remove(x, t.left);
else if (compareResult > 0)
t.right = remove(x, t.right);
else if (t.left != null && t.right != null) { // 2 children
t.element = findMin(t.right).element;
t.right = remove(t.element, t.right);
} else
t = (t.left != null) ? t.left : t.right;
return t;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论