二叉查询树的实现

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;
    }

}

评论

暂无评论