Binary Search Tree

I was hoping for some help with a Binary Search Tree, i have been given a project with the following code:

class BinaryTreeNode {
BinaryTreeNode left;
BinaryTreeNode right;
BinaryTreeNode parent;
Integer value;
}

abstract class BinarySearchTree {
BinaryTreeNode root;
public abstract void add(Integer i);
public abstract void remove(Integer i);
public abstract boolean exists(Integer i);
public abstract String inorder();
public abstract String preorder();
public abstract String postorder();
}

I know I'm supposed to extend The BinarySearchTreeClass and override all the methods but i really don't know what to do with the nodes in my
class should i also override them my BinarySearchTreeImpl class.
heres what ive done so far:

public class BinarySearchTreeImpl extends BinarySearchTree {
private Integer value;
private BinaryTreeNode root = null;
private BinaryTreeNode parent = null;
private BinaryTreeNode right = null;
private BinaryTreeNode left = null;

public BinarySearchTreeImpl(){

}
public void add(Integer i){
int compare = i.compareTo(this.value);
if(this.root == null){
root.value = i;
}

if(compare <= 0){
if(this.left == null){
this.left.value = i;
}
this.left.add(i);
}
else if(compare > 0){
if(this.right == null){
this.right.value = i;
}
this.left.add(i);
}
}
public void remove(Integer i){

}
public boolean exists(Integer i){
return true;
}
public String inorder(){
return "hi";
}
public String preorder(){
return "hi";
}
public String postorder(){
return "hi";
}
}
I would really like some help with the add method so that i can see how it's done.
Thanks in advance.

Comments


  • BinarySearchTreeImpl contains only one BinaryTreeNode, which is the root node. It does not contain any value. All the comparisons are done between the nodes.

    It is not necessary to override the BinaryTreeNode class. It simply contains it's own value and the parent node above it and it's 2 children, left and right, where left's value is less than it's own value and right's value is greater than it's own value, giving a tree as follows ...

    root
    < / >
    /
    left right
    < / >
    /
    left right

    // recursing from the root node
    Add ( Integer i, Node parent )

    if the parent == null
    then create a new root node as the incoming parameter i

    else if the parent != null

    if i.value == parent.value

    //quit as there's nowt to do

    if i.value < parent.value

    if parent.left != null
    then add( i, parent.left )
    else
    create a new left child with incoming i

    else if i.value > parent.value

    if parent.right != null
    then add( i, parent.right )
    else
    create a new right child with incoming i






    : I was hoping for some help with a Binary Search Tree, i have been given a project with the following code:
    :
    : class BinaryTreeNode {
    : BinaryTreeNode left;
    : BinaryTreeNode right;
    : BinaryTreeNode parent;
    : Integer value;
    : }
    :
    : abstract class BinarySearchTree {
    : BinaryTreeNode root;
    : public abstract void add(Integer i);
    : public abstract void remove(Integer i);
    : public abstract boolean exists(Integer i);
    : public abstract String inorder();
    : public abstract String preorder();
    : public abstract String postorder();
    : }
    :
    : I know I'm supposed to extend The BinarySearchTreeClass and override all the methods but i really don't know what to do with the nodes in my
    : class should i also override them my BinarySearchTreeImpl class.
    : heres what ive done so far:
    :
    : public class BinarySearchTreeImpl extends BinarySearchTree {
    : private Integer value;
    : private BinaryTreeNode root = null;
    : private BinaryTreeNode parent = null;
    : private BinaryTreeNode right = null;
    : private BinaryTreeNode left = null;
    :
    : public BinarySearchTreeImpl(){
    :
    : }
    : public void add(Integer i){
    : int compare = i.compareTo(this.value);
    : if(this.root == null){
    : root.value = i;
    : }
    :
    : if(compare <= 0){
    : if(this.left == null){
    : this.left.value = i;
    : }
    : this.left.add(i);
    : }
    : else if(compare > 0){
    : if(this.right == null){
    : this.right.value = i;
    : }
    : this.left.add(i);
    : }
    : }
    : public void remove(Integer i){
    :
    : }
    : public boolean exists(Integer i){
    : return true;
    : }
    : public String inorder(){
    : return "hi";
    : }
    : public String preorder(){
    : return "hi";
    : }
    : public String postorder(){
    : return "hi";
    : }
    : }
    : I would really like some help with the add method so that i can see how it's done.
    : Thanks in advance.
    :

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

In this Discussion