The goal of this question is to implement binary tree nodes which will then be used for implementing a generic binary tree which, in turn, will be used to implement heaps and binary search trees. As you know, heaps and binary search trees are defined for objects with associated keys that are comparable to each other. For these keys, we will use comparable objects. For testing purposes, keys will be instances of the class MyInteger and you will need the Hashable interface. If you are using Eclipse, create a  project for this assignment and add Comparable and MyInteger before you continue.

a) Complete the following class for representing nodes in a binary tree and add this class to your project.

public class BinaryTreeNode
{
    // Instance variables (Note: they are all "private")
    private Comparable key           // The key at this node
    private Object element;          // The data at this node
    private BinaryTreeNode left;     // Left child
    private BinaryTreeNode right;    // Right child
    private BinaryTreeNode p;        // The Parent

    // Constructors
    BinaryTreeNode( Comparable theKey, Object theElement, BinaryTreeNode lt, 
                    BinaryTreeNode rt, BinaryTreeNode pt  )
    {
        key      = theKey;
        element  = theElement;
        left     = lt;
        right    = rt;
        p        = pt;
    }

    BinaryTreeNode(Comparable theKey, Object theElement)
    {
        key      = theKey;
        element  = theElement;
        left     = null;
        right    = null;
        p        = null;
    }

    // return the key attached to this node
    public Comparable getKey()
    {
    ...
    }

    // set the key attached to this node to be Comparable k
    public void setKey(Comparable k)
    {
    ...
    }

    // return the element attached to this node
    public Object getElement()
    {
    ...
    }

    // set the element attached to this node to be Object o
    public void setElement(Object o)
    {
    ...
    }

    // return left child
    public BinaryTreeNode leftChild()
    {
    ...
    }

    // set left child to be node n
    public void setLeftChild(BinaryTreeNode n)
    {
    ...
    }

    // return right child
    public BinaryTreeNode rightChild()
    {
    ...
    }

    // set right child to be node n
    public void setRightChild(BinaryTreeNode n)
    {
    ...
    }
   
    // return parent
    public BinaryTreeNode parent()
    {
    ...
    }

    // set parent to be node n
    public void setParent(BinaryTreeNode n)
    {
    ...
    }
}

The goal of this question is to implement generic binary trees consisting of BinaryTreeNode instances.

a) Add an interface "BinaryTree" for generic binary trees which support the following methods:

    // make the tree empty
    void makeEmpty( );

    // create a root node with key "k" and element "el"
    void makeRoot (Comparable k, Object el);

    // return the root node
    BinaryTreeNode root();

    // return left child of node "node"
    public BinaryTreeNode leftChild(BinaryTreeNode node);

    // set left child of node "node" to "child"
    public void setLeftChild(BinaryTreeNode node, BinaryTreeNode child);

    // return right child of node "node"
    public BinaryTreeNode rightChild(BinaryTreeNode node)

    // set right child of node "node" to "child"
    public void setRightChild(BinaryTreeNode node, BinaryTreeNode child);

    // return parent of node "node"
    public BinaryTreeNode parent(BinaryTreeNode node)

    // set parent of node "node" to "pt"
    public void setparent(BinaryTreeNode node, BinaryTreeNode pt);

    // return the key attached to node "node"
    public Comparable getKey(BinaryTreeNode node);

    // set the key attached to node "node" to be key "k"
    public void setKey(BinaryTreeNode node, Comparable k);

    // return the element attached to node "node"
    public Object getElement(BinaryTreeNode node);

    // set the element attached to node "node" to be Object "o"
    public void setElement(BinaryTreeNode node, Object o);

    // add a left child node (with key "k" and element "el") to a tree node "theNode"
    void addLeftChild (BinaryTreeNode theNode, Comparable k, Object el);

    // add a right child node (with key "k" and element "el") to a tree node "theNode"
    void addRightChild (BinaryTreeNode theNode, Comparable k, Object el);

    // remove the left child of node "theNode"
    void removeLeftChild (BinaryTreeNode theNode);

    // remove the right child of node "theNode"
    void removeRightChild (BinaryTreeNode theNode);

    // return a string representation of the tree as an inorder traversal
    // with each node, n, indented by height(n) blanks. 
    // If the tree is empty, return a string "*** tree is empty ***".
    String toString();

    // return a string representation of the tree as an inorder traversal
    // with each node, n, indented by height(n) blanks. In addition, node "currentPosition"
    // is marked with an asterix ("*"). 
    // (No asterix if currentPosition =  null or currentPosition is not in the tree.)
    // If the tree is empty, return a string "*** tree is empty ***".
    String toString(BinaryTreeNode currentPosition);

Make sure that you also add the necessary exceptions (Add "throws" statements to the above and create the necessary exception classes). Think about the possible error conditions.

b) Add a class "SimpleBinaryTree" which implements the interface "BinaryTree".

c) Create using JUnit test classes for BinaryTreeNode, BinaryTree, SimpleBinaryTree. Be sure to carefully test the boundary condidtions.

    // make the heap empty
    void makeEmpty( );

    // insert an element "el" with key "k" 
    void insert (Comparable k, Object el);

    // return the key of the smallest element (but don't remove it yet)
    Comparable getMinKey ();

    // return the smallest element (but don't remove it yet)
    Object getMinElement ();

    // remove the smallest element (and it's key) from the heap
    void removeMin ();

Make sure that you also add the necessary exceptions (Add "throws" statements to the above and create the necessary exception classes). Think about the possible error conditions.

b) Add a class "SimpleBinaryTreeHeap" which is a subclass of "SimpleBinaryTree" and implements the interface "Heap".

c) Create using JUnit test classes for SimpleBinaryTreeHeap and Heap. Be sure to carefully test the boundary condidtions.

The goal of this question is to implement binary search trees as a subclass of binary trees.

a) Add an interface "Dictionary" for generic dictionaries which support the following methods:

    // empty the dictionary
    void makeEmpty( );

    // insert an element "el" with key "k" 
    void insert (Comparable k, Object el);

    // remove an element with key "k" 
    void remove (Comparable k);

    // find (and return) an element with key "k" 
    Object find (Comparable k);

Make sure that you also add the necessary exceptions (Add "throws" statements to the above and create the necessary exception classes). Think about the possible error conditions.

b) Add a class "SimpleBinarySearchTree" which is a subclass of "SimpleBinaryTree" and implements the interface "Dictionary".

c) Create using JUnit test classes for SimpleBinarySearchTree and Dictionary. Be sure to carefully test the boundary condidtions.