Binary Search Tree

[deven1974]

Implement the insert, remove, and search methods of the BinarySearchTree
class. Included are the Main, Tree, and TreeException classes.
Do not make changes to those classes. Your tree should work with
them as shown. All operations should be implemented recursively.
Additional methods may be needed.

/*
* Tree.java
 *
 */

import java.util.Iterator;
import java.util.Vector;

public abstract class Tree<E> implements Iterable<E> {

    protected class Node<T> {

        protected Node(T data) {
            this.data = data;
        }

        protected T data;
        protected Node<T> left;
        protected Node<T> right;
    }

    public void insert(E data) {

        Node<E> temp = new Node<E>(data);

        root = insert(root, temp);
    }

    protected abstract Node<E> insert(Node<E> curr, Node<E> node);

    public Iterator<E> iterator() {

        Vector<E> vector = new Vector<E>();

        traverse(vector, root);

        return vector.iterator();
    }

    public void remove(E data) {

        root = remove(root, data);
    }

    protected abstract Node<E> remove(Node<E> curr, E data) throws TreeException;

    public boolean search(E key) {

        return search(root, key);
    }

    protected abstract boolean search(Node<E> curr, E key);

    private void traverse(Vector<E> vector, Node<E> curr) {

        if (curr != null) {
            traverse(vector, curr.left);
            vector.add(curr.data);
            traverse(vector, curr.right);
        }
    }

    private Node<E> root;
}

/*
 *
 *  TreeException.java
 *
 */

public class TreeException extends RuntimeException {

    public TreeException() {}
    public TreeException(String msg) { super(msg); }
}

/*
 *
 *  BinarySearchTree.java
 *
 */

public class BinarySearchTree<E extends Comparable<? super E>> extends Tree<E> 
{
    private Node insert(Comparable temp, Node curr) {
        if(curr == null)
            curr = new Node(temp);
        else if(temp.compareTo(curr.data) < 0)
            curr.left = insert(temp, curr.left);
        else if(temp.compareTo(curr.data) > 0)
            curr.right = insert(temp, curr.right);
        return curr;
    }
    
    private Node remove(Comparable temp, Node curr) {
        if(curr == null)
            throw new TreeException(temp.toString( ));
        if(temp.compareTo(curr.data) < 0)
            curr.left = remove(temp, curr.left );
        else if(temp.compareTo(curr.data) > 0 )
            curr.right = remove(temp, curr.right );
        else if(curr.left != null && curr.right != null ) {
            curr.data = findMin(curr.right).data;
            curr.right = removeMin(curr.right );
        } else
            curr = ( curr.left != null ) ? curr.left : curr.right;
        return curr;
    }
    private Node removeMin(Node curr) {
        if(curr == null) {
            throw new TreeException();
        }
        else if(curr.left != null) {
            curr.left = removeMin(curr.left);
            return curr;
        }
        else {
            return curr.right;
        }
    }
    
    private Node findMin(Node curr) {
        if(curr != null) {
            while(curr.left != null) {
                curr = curr.left;
            }
        }
        return curr;
    }
    private Node search(Comparable temp, Node curr) {
        while(curr != null) {
            if(temp.compareTo(curr.data) < 0)
                curr = curr.left;
            else if(temp.compareTo(curr.data) > 0)
                curr = curr.right;
            else
                return curr;    // Match
        }
        return null;         // Not found
    }
}

Can anybody help with this program, I'm getting an error message after I'd complie it.

Here is the error message:

Exception in thread "main" java.lang.AbstractMethodError: Tree.insert(LTree$Node;LTree$Node;)LTree$Node;
at Tree.insert(Tree.java:21)
at Main.main(Main.java:12)

[stephen84s]

Well Deven the error speaks for itself, let us look at your declaration of the method insert(Node,Node) (also I do not know why would you want two Nodes to be passed to the insert() method) in the Tree class: -

protected abstract Node<E> insert(Node<E> curr, Node<E> node);

Now you have declared this as abstract, no hassles here, since you want to force the extending class to provide an implementation, But the only insert() method I see in the child class "BinarySearchTree" is this :-

private Node insert(Comparable temp, Node curr) {

So you haven't actually provided an implementation for the insert(Node,Node) method of the Tree class and hence the compiler is complaining about it. Also I think you should get more errors when you are actually try to create an instance of the BinarySearchTree class.

One fix I see is changing the declaration of insert(Node,Node) in the parent Tree class to insert(Comparable,Node).
Also you are reducing the visibility of the method from "protected" to "private" in the child class, which **I think** should also cause problems.

Note I haven't paid too much attention to your design or the rest of the code, so you should be a better judge as to what solution you should opt for.

[deven1974]

okay I have updated the Binary Search Tree, but I'm still getting one message.

public class BinarySearchTree<E extends Comparable<? super E>> extends Tree<E>
{
protected Node insert(Comparable temp, Node curr) {
//Node<E> temp= new Node<E>(node.data) ;
if(curr == null)
curr = new Node(temp);
else if(temp.compareTo(curr.data) < 0)
curr.left = insert(temp,curr.left);
else if(temp.compareTo(curr.data) > 0)
curr.right = insert(temp,curr.right);
return curr;
}
protected Node remove(Comparable temp, Node curr) {
if (curr == null)
throw new TreeException();
if (temp.compareTo(curr.data) < 0)
curr.left = remove(temp, curr.left);
else if(temp.compareTo(curr.data) > 0)
curr.right = remove(temp, curr.right);
return curr;
}
}

[stephen84s]

Please paste the compiler error or whatever message you are getting. I mean how can we help you solve your problem if we do not know what the problem is ???

[deven1974]

public class BinarySearchTree<E extends Comparable<? super E>> extends Tree<E> {
protected Node insert(Comparable temp, Node curr) {

//Node<E> temp= new Node<E>(node.data) ;
if(curr == null)
curr = new Node(temp);
else if(temp.compareTo(curr.data) < 0)
curr.left = insert(temp,curr.left);
else if(temp.compareTo(curr.data) > 0)
curr.right = insert(temp,curr.right);

return curr;
}

protected Node remove(Comparable temp, Node curr) {
if (curr == null)
throw new TreeException();
if (temp.compareTo(curr.data) < 0)
curr.left = remove(temp, curr.left);
else if(temp.compareTo(curr.data) > 0)
curr.right = remove(temp, curr.right);
return curr;
}

protected boolean search (Comparable temp, E key)
{
while (curr != null){
if(temp.data.compareTo(key) < 0)
{

temp = temp.left;
return true;
}

else if (temp.data.compareTo(key) > 0);
{

temp = temp.right;
return true;
}
else

return false;

}

return false;

}
}

Error Message is:

C:\Program Files\Java\jdk1.6.0_10\bin>javac *.java
BinarySearchTree.java:42: 'else' without 'if'
else
^
1 error

C:\Program Files\Java\jdk1.6.0_10\bin>

Well Deven the error speaks for itself, let us look at your declaration of the method insert(Node,Node) (also I do not know why would you want two Nodes to be passed to the insert() method) in the Tree class: -

protected abstract Node<E> insert(Node<E> curr, Node<E> node);

Now you have declared this as abstract, no hassles here, since you want to force the extending class to provide an implementation, But the only insert() method I see in the child class "BinarySearchTree" is this :-

private Node insert(Comparable temp, Node curr) {

So you haven't actually provided an implementation for the insert(Node,Node) method of the Tree class and hence the compiler is complaining about it. Also I think you should get more errors when you are actually try to create an instance of the BinarySearchTree class.

One fix I see is changing the declaration of insert(Node,Node) in the parent Tree class to insert(Comparable,Node).
Also you are reducing the visibility of the method from "protected" to "private" in the child class, which **I think** should also cause problems.

Note I haven't paid too much attention to your design or the rest of the code, so you should be a better judge as to what solution you should opt for.

[Ezzaral]

Check your semicolons prior to that else statement.

[deven1974]

Same error message, and even correcting semicolons issue;

Thanks

[deven1974]

Same error message, and even correcting semicolons issue

public class BinarySearchTree<E extends Comparable<? super E>> extends Tree<E>
{
protected Node insert(Comparable temp, Node curr) {
//Node<E> temp= new Node<E>(node.data) ;
if(curr == null)
curr = new Node(temp);
else if(temp.compareTo(curr.data) < 0)
curr.left = insert(temp,curr.left);
else if(temp.compareTo(curr.data) > 0)
curr.right = insert(temp,curr.right);
return curr;
}
protected Node remove(Comparable temp, Node curr) {
if (curr == null)
throw new TreeException();
if (temp.compareTo(curr.data) < 0)
curr.left = remove(temp, curr.left);
else if(temp.compareTo(curr.data) > 0)
curr.right = remove(temp, curr.right);
return curr;
}

protected boolean search (Node<E> curr, E key)
{
while (curr != null){
if(curr.data.compareTo(key) < 0)
{
curr = curr.left;
return true;
}
else if (curr.data.compareTo(key) > 0)
{
curr = curr.right;
return true;
}
else
{
return false;
}
return false;
}
}
}

Error message that I'm getting, can anybody help with this error message:

C:\Documents and Settings\Deven\Desktop\Project 7>javac *.java
BinarySearchTree.java:1: BinarySearchTree is not abstract and does not override
abstract method remove(Tree<E>.Node<E>,E) in Tree
public class BinarySearchTree<E extends Comparable<? super E>> extends Tree<E> {
^
Note: BinarySearchTree.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error

[quuba]

Implement the insert, remove, and search methods of the BinarySearchTree class
This mean: override abstract methods of abstract class Tree<E>

protected abstract Node<E> remove(Node<E> curr, E data) throws TreeException;
    protected abstract boolean search(Node<E> curr, E key);
    protected abstract Node<E> insert(Node<E> curr, Node<E> node);

In public class BinarySearchTree you need write:

@Override
    protected Node<E> insert(Node<E> curr, Node<E> node) {
    throw new UnsupportedOperationException("Not supported yet.");
    }
    
    @Override
    protected Node<E> remove(Node<E> curr, E data) throws TreeException {
    throw new UnsupportedOperationException("Not supported yet.");
    }
    
    @Override
    protected boolean search(Node<E> curr, E key) {
    throw new UnsupportedOperationException("Not supported yet.");
    }

throw new UnsupportedOperationException("Not supported yet.");
- replace this lines with own code
Use NetBeans to develop your program!

[deven1974]

public class BinarySearchTree<E extends Comparable<? super E>> extends Tree<E>

{
protected Node<E> insert(Node<E> curr, Node<E> node) {
throw new UnsupportedOperationException;
Node<E> temp= new Node<E>(node.data) ;
if( temp == null )
temp = new Node<E>(curr.data);
else if( (temp.data.compareTo(node.data))<0 )
temp.left = insert( curr.right, node.left );
else if( (temp.data.compareTo(node.data))>0 )
temp.right = insert( node.right, curr.left );

return temp;
}

protected Node<E> remove(Node<E> curr, E data)
{
throw new UnsupportedOperationException;
Node<E> temp= new Node<E>(curr.data) ;
if( temp == null )
throw new TreeException();
if( temp.data.compareTo( curr.data ) < 0 )
temp.left = remove( temp.left,data );
else if( temp.data.compareTo( curr.data ) >0)
temp.right = remove( temp.right,data );
return temp;

}

protected boolean search (Node<E> curr, E key)
{
throw new UnsupportedOperationException;

while (curr != null){
if(curr.data.compareTo(key) < 0)
{
curr = curr.left;
return true;
}

else if (curr.data.compareTo(key) > 0)
{
curr = curr.right;
return true;
}
else
{

return false;
}

return false;

}
}

}

Error Message:

C:\Documents and Settings\Deven\Desktop\Project 7>javac *.java
BinarySearchTree.java:3: '(' or '[' expected
throw new UnsupportedOperationException;
^
BinarySearchTree.java:17: '(' or '[' expected
throw new UnsupportedOperationException;
^
BinarySearchTree.java:32: '(' or '[' expected
throw new UnsupportedOperationException;
^
3 errors

C:\Documents and Settings\Deven\Desktop\Project 7>

Implement the insert, remove, and search methods of the BinarySearchTree class
This mean: override abstract methods of abstract class Tree<E>

protected abstract Node<E> remove(Node<E> curr, E data) throws TreeException;
    protected abstract boolean search(Node<E> curr, E key);
    protected abstract Node<E> insert(Node<E> curr, Node<E> node);

In public class BinarySearchTree you need write:

@Override
    protected Node<E> insert(Node<E> curr, Node<E> node) {
    throw new UnsupportedOperationException("Not supported yet.");
    }
    
    @Override
    protected Node<E> remove(Node<E> curr, E data) throws TreeException {
    throw new UnsupportedOperationException("Not supported yet.");
    }
    
    @Override
    protected boolean search(Node<E> curr, E key) {
    throw new UnsupportedOperationException("Not supported yet.");
    }

throw new UnsupportedOperationException("Not supported yet.");
- replace this lines with own code
Use NetBeans to develop your program!

[quuba]

once more - Use NetBeans to develop your program!
text throw new UnsupportedOperationException("Not supported yet."); - replace this lines with own code.
There should be invocations of your private methods with same name (sometime you need make some adaptation).
Use NetBeans , proper tool for this advanced java program. NetBeans helps you in develop.

[Ezzaral]

Deven, you really need to use [code] [/code] tags around any code that you post. Putting it in as a quote does nothing to preserve it's formatting.

[quuba]

meantime relate to #10

@Override
    protected boolean search(Node<E> curr, E key) {
        while (curr != null) {
            if (curr.data.compareTo(key) < 0) {
                curr = curr.left;
                return true;
            } else if (curr.data.compareTo(key) > 0) {
                curr = curr.right;
                return true;
            } else {
                return false;
            }
            //return false;// 1.Not proper position for return
        }
        return false;//2.Correct position for return
    }

Inside your methods, if you filled them , don't still use throw new UnsupportedOperationException;

[deven1974]

Hello,
I want thank for your guys help with this diffcult program. I finally got the program to work, but I don't know the output is right. Can anybody tell me is this what output should be or something else. Is this output answer the question that is given from the program.

public class BinarySearchTree<E extends Comparable<? super E>> extends Tree<E> {
    protected Node<E> insert(Node<E> curr, Node<E> node) {
         //throw new UnsupportedOperationException; 
        Node<E> temp= new Node<E>(node.data) ;
        if( temp == null )
            temp = new Node<E>(curr.data);
        else if(  (temp.data.compareTo(node.data))<0 )
            temp.left = insert( curr.right, node.left );
        else if( (temp.data.compareTo(node.data))>0 )
            temp.right = insert( node.right, curr.left );

        return temp;
     }

   protected  Node<E> remove(Node<E> curr, E data)
    {
        //throw new UnsupportedOperationException;
        Node<E> temp= new Node<E>(curr.data) ;
        if( temp == null )
            throw new TreeException();
        if( temp.data.compareTo( curr.data ) < 0 )
            temp.left = remove( temp.left,data );
        else if( temp.data.compareTo( curr.data ) >0)
            temp.right = remove( temp.right,data );
       return temp;

    }


    protected boolean search(Node<E> curr, E key) {
        while (curr != null) {
            if (curr.data.compareTo(key) < 0) {
                curr = curr.left;
                return true;
            } else if (curr.data.compareTo(key) > 0) {
                curr = curr.right;
                return true;
            } else {
                return false;
            }

        }
        return false;
    }
  }

Output Result:

Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

C:\Documents and Settings\Deven>cd Desktop

C:\Documents and Settings\Deven\Desktop>cd Project 7

C:\Documents and Settings\Deven\Desktop\Project 7>javac *.java

C:\Documents and Settings\Deven\Desktop\Project 7>java Main
0
8
9
7
5
3
1
1
9
4
0 => true
8 => true
9 => true
7 => true
15 => true
13 => true
11 => true
1 => true
19 => true
14 => true
4
4
4
4
4
4
4
4
4
4

Thanks for your help on this.

[quuba]

check your code:

protected Node<E> insert(Node<E> curr, Node<E> node) {
//throw new UnsupportedOperationException;
        System.out.println(" curr " + curr + " " + ((curr == null) ? "." : "data=" + curr.data));
        System.out.println(" node " + node + " " + ((node == null) ? "." : "data=" + node.data));
        Node<E> temp = new Node<E>(node.data);
        System.out.println(" temp " + temp + " " + ((temp == null) ? "." : "data=" + temp.data));
        if (temp == null) {
            temp = new Node<E>(curr.data);
            System.out.println(" temp == null ");
        } else if ((temp.data.compareTo(node.data)) < 0) {
            System.out.print("L ");
            temp.left = insert(curr.right, node.left);
        } else if ((temp.data.compareTo(node.data)) > 0) {
            System.out.print("R ");
            temp.right = insert(node.right, curr.left);
        }

        return temp;
    }

Result--> always one element inside the tree (last inserted).