Binary Search Tree Instantiaition

3
votes

I have Created Binary Search Tree by Using a Tree Interface and Recursion (I am aware that using a Node Class I can Implement the same ) providing methods for Adding and Checking if an element is in the Binary Search Tree or not.

The Problem I am facing is in instantiating & displaying the elements of the BST.

Here is my code

Tree Interface:

package bst;

public interface Tree<D extends Comparable>{

    public boolean isempty();
    public int cardinality();
    public boolean member(D elt);
    public NonEmptyBst<D> add(D elt);

}

EmptyBst Class: 

 package bst;

 public class EmptyBst<D extends Comparable> implements Tree<D>{
    public EmptyBst(){
        D data=null;
    }

    @Override
    public boolean isempty() {
        // TODO Auto-generated method stub
        return true;
    }

    @Override
    public int cardinality() {
        // TODO Auto-generated method stub
        return 0;
    }

    @Override
    public boolean member(D elt) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public NonEmptyBst<D>add(D elt) {
        // TODO Auto-generated method stub
        return new NonEmptyBst<D>(elt);
    }

}

NonEmptyBst Class

 package bst;

 public class NonEmptyBst<D extends Comparable> implements Tree<D> {
    D data;
    D root;
    Tree<D> left;
    Tree <D>right;

    public NonEmptyBst(D elt){
        data=elt;
        root=elt;
        left=new EmptyBst<D>();
        right=new EmptyBst<D>();

    }
    NonEmptyBst(){
        D dataThis=this.data;
    }
    public NonEmptyBst(D elt,Tree<D>leftTree,Tree<D>rightTree){
        data=elt;
        left=leftTree;
        right=rightTree;
    }
    @Override
    public boolean isempty() {
        // TODO Auto-generated method stub
        return false;
    }
    @Override
    public int cardinality() {
        // TODO Auto-generated method stub
        return 1+left.cardinality()+right.cardinality();
    }



    public boolean member(D elt) {
        if (data == elt) {
            return true;
        } else {
            if (elt.compareTo(data) < 0) {
                return left.member(elt);
            } else {
                return right.member(elt);
            }
        }
    }

    public NonEmptyBst<D> add(D elt) {
        if (data == elt) {
            return this;
        } else {
            if (elt.compareTo(data) < 0) {
                return new NonEmptyBst(data, left.add(elt), right);
            } else {
                return new NonEmptyBst(data, left, right.add(elt));
            }
        }
    }
}

BinarySearchTree Class

package bst;
import bst.Tree;
import bst.EmptyBst;
import bst.NonEmptyBst;

public class BinarySearchTree {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        NonEmptyBst abcd=new NonEmptyBst( "abc");
        NonEmptyBst ab=new NonEmptyBst(67);

        abcd.add("cry me a river");
        abcd.add("geeehfvmfvf");
        abcd.add("I'm Sexy and i know it");
        abcd.add("zzzzsd");
        abcd.add("zzzzsd");
        abcd.add("zzzfdsf");
        abcd.add("zzfedfrsd");
        abcd.add("tgrgdzsd");
        abcd.add("gtrgrtgtrgtrzzzzsd");
        abcd.add("zzzzsd");
        abcd.add("zdddzzzsd");
        abcd.add("zzzzsd");
        abcd.add("zzzzsd");

    }
}

** How Can I access the data at all nodes and then Print Them out?The Particular Problem I am facing is In Getting an exception namely ClassCastException when I access the "leaf Nodes" and even if I Initalize new NonEmptyBst<D>in My NonEmptyBst<D>(D elt) constructor I end Up having a null pointer Exception

  Exception in thread "main" java.lang.NullPointerException 
    at java.lang.String.compareTo(Unknown Source) 
    at java.lang.String.compareTo(Unknown Source) 
    at bst.NonEmptyBst.add(NonEmptyBst.java:51) 
    at bst.NonEmptyBst.add(NonEmptyBst.java:54) 
    at bst.BinarySearchTree.main(BinarySearchTree.java:11)
2
javaclasscastingnullpointerexceptionbinary-search-tree
What are you expecting D dataThis=this.data; to do? this.data is null at that point - OneCricketeer
I wanted to create an empty Instance of a NonEmptyBst<D> in order to create a "pointer" through which I could iterate through my NonEmptyBst and assign the data that pointer has to the data at the node at which I am currently "pointing to" - Hardik Vats
Where is the exception, then? Please show the stacktrace - OneCricketeer
Also, you never set left or right... Your add method is returning something, but you do nothing with those results - OneCricketeer
Does add modify the current tree or return a new tree? - Andrew Rueckert

2 Answers

3
votes

I'm not really sure I see the need for EmptyBst unless you are trying to follow the design-pattern for a Null Object.

Specifically, an "empty" tree can easily be checked if data == null && left == null && right == null. Also, no need for data here, since it is a local variable and never referenced. 

public EmptyBst(){
    D data=null; 
}

And is there a difference between D data and D root?

I think you need to adjust your add method to capture the result of the recursion. 

public NonEmptyBst<D> add(D elt) {
    if (data == elt) {
        return this;
    } else {
        if (elt.compareTo(data) < 0) {
            this.left = this.left.add(elt);
        } else {
            this.right = this.right.add(elt);
        }
    }

    return this;
}
0
votes

You need to access it recursively. As I don't have your node implementation I'll write a general example:

// Return a list with all the nodes
public List<Node> preOrder() {
    List<Node> l = new ArrayList<Node>();
    l.add(this.value); // Add the data of the root
    if(this.left != null) // Add elements to the left
        l.addAll(this.left.preOrder());
    if(this.right != null) // Add elements to the right
        l.addAll(this.right.preOrder());
    return l;
}

Then you would simply call it:

List<Node> nodes = myTree.preOrder();

And then loop through the list to do whatever you want.