All pastes #371916 Raw Edit

Untitled

public text v1 · immutable
#371916 ·published 2007-02-25 19:15 UTC
rendered paste body
public interface BinarySearchTree<K extends Comparable> {
	/**
	 * Returns the root node of the tree, or null if none.
	 *
	 * @return a BinaryNode or null
	 */
	public BinaryNode<K> getRoot();
	
	/**
	 * Is this an empty tree?
	 *
	 * @return true if so, false if not
	 */
	public boolean isEmpty();
	
	/**
	 * Inserts a new value (hence creating a new node) into the tree.
	 *
	 * @param c value to insert
	 */
	public void insert(K c);
	
	/**
	 * Look up an element in the tree.  If an object which is equal
	 * (i.e., compareTo is 0) exists in the tree, we return that
	 * object.  Otherwise, we return false.
	 *
	 * @param c value to find
	 * @return the element in the tree, or null
	 */
	public K find(K c);
}

----------------------------------------

public class GenericBST<K extends Comparable> implements BinarySearchTree {
    private BSTNode root;
    
    public GenericBST() {

    }
    
    /**
     * Returns the root node of the tree, or null if none.
     *
     * @return a BinaryNode or null
     */
    public BSTNode getRoot() {
    	return root;
    }
    
    /**
     * Is this an empty tree?
     *
     * @return true if so, false if not
     */
    public boolean isEmpty() {
    	return (root == null);
    }
	
    /**
     * Inserts a new value (hence creating a new node) into the tree.
     *
     * @param c value to insert
     */
    public void insert(K c) {  <----------ERROR:Name clash: The method find(K) of type GenericBST<K> has the same erasure as find(K) of type BinarySearchTree<K> but does not override it
    	insert(c, root);
    }

    /**
     * Recursively traverses tree until we find the proper insertion place.
     *
     * @param c value to insert
     * @param node current node
     */
    public void insert(K c, BSTNode node) {  
		if (c.compareTo(node.getData()) < 0)
		    if (node.getLeft() == null)
			    node.setLeft(new BSTNode(c));
		    else insert(c, node.getLeft());
	
		if (c.compareTo(node.getData()) > 0)
		    if (node.getRight() == null)
			    node.setRight(new BSTNode(C));
		    else insert(c, node.getRight());
    }
	
    /**
     * Look up an element in the tree.  If an object which is equal
     * (i.e., compareTo is 0) exists in the tree, we return that
     * object.  Otherwise, we return false.
     *
     * @param c value to find
     * @return the element in the tree, or null
     */
    public K find(K c) {      <----------ERROR:Name clash: The method find(K) of type GenericBST<K> has the same erasure as find(K) of type BinarySearchTree<K> but does not override it
    	return find(c, root);
    }

    public K find(K c, BSTNode node) {
		if (node == null) return null;
		
		if (c.compareTo(node.getData()) < 0)
		    find(c, node.getLeft());
		
		if (c.compareTo(node.getData()) > 0)
		    find(c, node.getright());
		
		if (c.compareTo(node.getData()) == 0)
		    return c;
    }
}