I need help in building a binary tree and putting integers in it.

I need to write an add method in my MyArrayBinaryTree class (that extends ArrayBinaryTree) that allows me to place the element to be added in the very next available slot in the array.

I also need to write its constructors since MyArrayBinaryTree is derived from ArrayBinaryTree, and therefore inherits all of its methods (except the constructors). I cannot put my add method in ArrayBinaryTree class because that is the implementation of the ADT.

How does the add method look like and what constructors do I have to write in MyArrayBinaryTree class?

Any coding help is APPRECIATED!

My work so far:

MyArrayBinaryTree class:

public class MyArrayBinaryTree extends ArrayBinaryTree {
  //need help here
}

ArrayBinaryTree class:

import java.util.Iterator;
import binarytree.EmptyCollectionException;
import binarytree.ElementNotFoundException;

public class ArrayBinaryTree<T> implements BinaryTreeADT<T>
{
  protected int count;
  protected T[] tree; 
  private final int capacity = 50;

  public ArrayBinaryTree() 
  {
    count = 0;
    tree = (T[]) new Object[capacity];
  }

  public ArrayBinaryTree (T element) 
  {
    count = 1;
    tree = (T[]) new Object[capacity];
    tree[0] = element;
  }

  protected void expandCapacity()
  {
    T[] temp = (T[]) new Object[tree.length * 2];

    for (int ct=0; ct < tree.length; ct++)
       temp[ct] = tree[ct];

    tree = temp;
  }

  public T getRoot() throws EmptyCollectionException
  {
    if (isEmpty())
       throw new EmptyCollectionException("binary tree");

    return tree[0];
  }

  public boolean isEmpty() 
  {
    return (count == 0);
  }

  public int size() 
  {
    return count;
  }

  public boolean contains (T targetElement) 
  {
    boolean found = false;

    for (int ct=0; ct<count && !found; ct++)
       if (targetElement.equals(tree[ct]))
         found = true;

    return found;
  }

  public T find (T targetElement) throws ElementNotFoundException 
  {
    T temp=null;
    boolean found = false;

    for (int ct=0; ct<count && !found; ct++)
       if (targetElement.equals(tree[ct]))
       {
          found = true;
          temp = tree[ct];
       }

    if (!found)
       throw new ElementNotFoundException("binary tree");

    return temp;
  }

  public String toString() 
  {
    ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
    inorder (0, templist);

    return templist.toString();
  }

  public Iterator<T> iteratorInOrder() 
  {
    ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
    inorder (0, templist);

    return templist.iterator();
  }

  protected void inorder (int node, ArrayUnorderedList<T> templist) 
  {
    if (node < tree.length)
       if (tree[node] != null)
       {
          inorder (node*2+1, templist);
          templist.addToRear(tree[node]);
          inorder ((node+1)*2, templist);
       }
  }

  public Iterator<T> iteratorPreOrder() 
  {
    ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
    preorder (0, templist);

    return templist.iterator();
  }

  protected void preorder (int node, ArrayUnorderedList<T> templist) 
  {
    if (node < tree.length)
      if (tree[node] != null) 
      { 
        templist.addToRear(tree[node]);
        inorder (node*2+1, templist);
        inorder ((node+1)*2, templist);
      }
  }

  public Iterator<T> iteratorPostOrder() 
  {
    ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
    postorder (0, templist);

    return templist.iterator();
  }

  protected void postorder (int node, ArrayUnorderedList<T> templist) 
  {
    if (node < tree.length)
       if (tree[node] != null) 
       {
         inorder (node*2+1, templist); 
         inorder ((node+1)*2, templist);
         templist.addToRear(tree[node]);  
       }
  }

  public Iterator<T> iteratorLevelOrder() 
  {
    ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
    int ct = 0; // current number of elements added to list
    int i = 0; // current position in array

    while (ct < count)
    {
      if (tree[i] != null)
      {
        tempList.addToRear(tree[i]);
        ct++;
      }
      i++;
    }

    return tempList.iterator();
  }
}

BinaryTreeADT class:

import java.util.Iterator;

public interface BinaryTreeADT<T> 
{
  public T getRoot ();

  public boolean isEmpty();

  public int size();

  public boolean contains (T targetElement);

  public T find (T targetElement);

  public String toString();

  public Iterator<T> iteratorInOrder();

  public Iterator<T> iteratorPreOrder();

  public Iterator<T> iteratorPostOrder();

  public Iterator<T> iteratorLevelOrder();
}

ElementNotFoundException class:

public class ElementNotFoundException extends RuntimeException
{
  //Sets up this exception with an appropriate message.
  public ElementNotFoundException (String collection)
  {
   super ("The target element is not in this " + collection);
  }
}

EmptyCollectionException class:

public class EmptyCollectionException extends RuntimeException
{
 //Sets up this exception with an appropriate message.
 public EmptyCollectionException (String collection)
 {
    super ("The " + collection + " is empty.");
 }
 }
public void add(E e)
{
    Entry<E> node = new Entry<E>(e);
    index = 0;
    int comp;
    boolean not_add = true;
    while(not_add)
    {
      if (tree[index] == null) //if this node is empty
      {
          tree[index] = node;
          size++;
          not_add  = true;
      }

      comp = ((Comparable)e).compareTo (tree[index].element);

      if(comp == 0) not_add = true; // Same value
      else if (comp < 0) index = index * 2;  // should be insert on the left
      else index = index * 2 + 1; // should be insert on the right
     }
}

Benjamin.
I appreciate that you are trying ot help, but here at DaniWeb we try to help people learn Java and develop their Java skills. We do NOT do people's homework for them. Your post explains and teaches nothing.
In future please help by pointing people in the right direction - eg tell them which classes and methods they should read about, or give them some sample code that they will have to understand and adapt to their needs.
If you need to post actual code then explain why you coded it the way you did. Don't just spoon-feed them a solution to copy and paste.

Edited 3 Years Ago by JamesCherrill

This article has been dead for over six months. Start a new discussion instead.