Java

Java RSS

Binary Search Tree

•

Join Date: Nov 2008

Posts: 11

Reputation: deven1974 is an unknown quantity at this point

Solved Threads: 0

deven1974

Offline

Newbie Poster

Binary Search Tree

Dec 14th, 2008

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.

 Help with Code Tags 
 Java Syntax (Toggle Plain Text) 
 
/*
* 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); }
}
/*
* 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); }
}

 Help with Code Tags 
 Java Syntax (Toggle Plain Text) 
/*
 *
 *  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
    }
}
/*
 *
 *  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)

•

Join Date: Jul 2007

Posts: 1,175

Reputation: stephen84s is a glorious beacon of light

Solved Threads: 125

stephen84s stephen84s is offline

Offline

Veteran Poster

Re: Binary Search Tree

Dec 15th, 2008

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: -

 Help with Code Tags 
 java Syntax (Toggle Plain Text) 
protected abstract Node<E> insert(Node<E> curr, Node<E> node);
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 :-

 Help with Code Tags 
 java Syntax (Toggle Plain Text) 
private Node insert(Comparable temp, Node curr) {
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.

Last edited by stephen84s; Dec 15th, 2008 at 3:54 am.

"Any fool can write code that a computer can understand. Good programmers write code that humans can understand."

"How to ask questions the smart way ?"

•

Join Date: Nov 2008

Posts: 11

Reputation: deven1974 is an unknown quantity at this point

Solved Threads: 0

deven1974

Offline

Newbie Poster

Re: Binary Search Tree

Dec 15th, 2008

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

}

•

Join Date: Jul 2007

Posts: 1,175

Reputation: stephen84s is a glorious beacon of light

Solved Threads: 125

stephen84s stephen84s is offline

Offline

Veteran Poster

Re: Binary Search Tree

Dec 15th, 2008

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 ???

"Any fool can write code that a computer can understand. Good programmers write code that humans can understand."

"How to ask questions the smart way ?"

•

Join Date: Nov 2008

Posts: 11

Reputation: deven1974 is an unknown quantity at this point

Solved Threads: 0

deven1974

Offline

Newbie Poster

Re: Binary Search Tree

Dec 16th, 2008

•

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>

•

Originally Posted by 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: -
Help with Code Tags

java Syntax (Toggle Plain Text)
protected abstract Node<E> insert(Node<E> curr, Node<E> node);
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 :-
Help with Code Tags

java Syntax (Toggle Plain Text)
private Node insert(Comparable temp, Node curr) {
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.

•

Join Date: May 2007

Posts: 4,454

Reputation: Ezzaral has much to be proud of

Solved Threads: 511

Ezzaral

Offline

Industrious Poster

Re: Binary Search Tree

Dec 16th, 2008

Check your semicolons prior to that else statement.

•

Join Date: Nov 2008

Posts: 11

Reputation: deven1974 is an unknown quantity at this point

Solved Threads: 0

deven1974

Offline

Newbie Poster

Re: Binary Search Tree

Dec 16th, 2008

Same error message, and even correcting semicolons issue;

Thanks

•

Join Date: Nov 2008

Posts: 11

Reputation: deven1974 is an unknown quantity at this point

Solved Threads: 0

deven1974

Offline

Newbie Poster

Re: Binary Search Tree

Dec 16th, 2008

•

Originally Posted by deven1974

Same error message, and even correcting semicolons issue;]

Thanks

•

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

•

Join Date: Nov 2008

Posts: 332

Reputation: quuba is on a distinguished road

Solved Threads: 53

quuba

Offline

Posting Whiz

Re: Binary Search Tree

Dec 16th, 2008

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

Help with Code Tags

(Toggle Plain Text)

    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:

Help with Code Tags

(Toggle Plain Text)

    @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!

•

Join Date: Nov 2008

Posts: 11

Reputation: deven1974 is an unknown quantity at this point

Solved Threads: 0

deven1974

Offline

Newbie Poster

Re: Binary Search Tree

#10

Dec 16th, 2008

•

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>

•

Originally Posted by quuba

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

(Toggle Plain Text)
    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);
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:
Help with Code Tags

(Toggle Plain Text)
    @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.");
    }
@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!