Problem 1: Write a class that implements a generic binary search tree including
ID: 3873523 • Letter: P
Question
Problem 1: Write a class that implements a generic binary search tree including the methods add, contains and printInorder. (We will do this as a group) Problem 2: Add a toString method to the class. This method returns a string of the form “[e1, e2, …, en]” containing all of the elements in the tree in order. Problem 3: Add a method to the class that returns the number of leaves in the tree. Problem 4: Add a clone method to the class that returns a copy of the tree. Remember that we have three different ways of traversing a tree: preorder, inorder and postorder. Does it matter which one you use in this method? Problem 5: Add an equals method to the class. Two trees are equal if they include the same elements. The structure of the trees does not have to be the same.
Explanation / Answer
import java.util.*;
public class BST <T extends Comparable<T>> implements Iterable<T>
{
public static void main(String[] args)
{
Integer[] a = {1,5,2,7,4};
BST<Integer> bst = new BST<Integer>();
for(Integer n : a) bst.insert(n);
bst.inOrderTraversal();
System.out.println();
System.out.println("Tostring of BST: "+bst);
System.out.println("Search of Element in BST: "+bst.search(9));
System.out.println("count no. of leaves : "+bst.countLeaves());
BST<Integer> bst2=bst.clone();
System.out.println("clone object"+bst2.clone());
System.out.println("checking equals of 2 objects: "+bst.equals(bst2));
}
private Node<T> root;
private Comparator<T> comparator;
public BST()
{
root = null;
comparator = null;
}
public BST(Comparator<T> comp)
{
root = null;
comparator = comp;
}
private int compare(T x, T y)
{
if(comparator == null) return x.compareTo(y);
else
return comparator.compare(x,y);
}
/*****************************************************
*
* INSERT
*
******************************************************/
public void insert(T data)
{
root = insert(root, data);
}
private Node<T> insert(Node<T> p, T toInsert)
{
if (p == null)
return new Node<T>(toInsert);
if (compare(toInsert, p.data) == 0)
return p;
if (compare(toInsert, p.data) < 0)
p.left = insert(p.left, toInsert);
else
p.right = insert(p.right, toInsert);
return p;
}
/*****************************************************
*
* SEARCH
*
******************************************************/
public boolean search(T toSearch)
{
return search(root, toSearch);
}
private boolean search(Node<T> p, T toSearch)
{
if (p == null)
return false;
else
if (compare(toSearch, p.data) == 0)
return true;
else
if (compare(toSearch, p.data) < 0)
return search(p.left, toSearch);
else
return search(p.right, toSearch);
}
/*************************************************
*
* toString
*
**************************************************/
public String toString()
{
StringBuffer sb = new StringBuffer();
sb.append("[");
for(T data : this) sb.append(data.toString()).append(",");
sb.append("]");
return sb.toString();
}
/*************************************************
*
* InOrder TRAVERSAL
*
**************************************************/
public void inOrderTraversal()
{
inOrderHelper(root);
}
private void inOrderHelper(Node r)
{
if (r != null)
{
inOrderHelper(r.left);
System.out.print(r+" ");
inOrderHelper(r.right);
}
}
/*************************************************
*
* CLONE
*
**************************************************/
public BST<T> clone()
{
BST<T> twin = null;
if(comparator == null)
twin = new BST<T>();
else
twin = new BST<T>(comparator);
twin.root = cloneHelper(root);
return twin;
}
private Node<T> cloneHelper(Node<T> p)
{
if(p == null)
return null;
else
return new Node<T>(p.data, cloneHelper(p.left), cloneHelper(p.right));
}
/*************************************************
*
* MISC
*
**************************************************/
public int height()
{
return height(root);
}
private int height(Node<T> p)
{
if(p == null) return -1;
else
return 1 + Math.max( height(p.left), height(p.right));
}
public int countLeaves()
{
return countLeaves(root);
}
private int countLeaves(Node<T> p)
{
if(p == null) return 0;
else
if(p.left == null && p.right == null) return 1;
else
return countLeaves(p.left) + countLeaves(p.right);
}
/*****************************************************
*
* TREE ITERATOR
*
******************************************************/
public Iterator<T> iterator()
{
return new MyIterator();
}
//pre-order
private class MyIterator implements Iterator<T>
{
Stack<Node<T>> stk = new Stack<Node<T>>();
public MyIterator()
{
if(root != null) stk.push(root);
}
public boolean hasNext()
{
return !stk.isEmpty();
}
public T next()
{
Node<T> cur = stk.peek();
if(cur.left != null)
{
stk.push(cur.left);
}
else
{
Node<T> tmp = stk.pop();
while( tmp.right == null )
{
if(stk.isEmpty()) return cur.data;
tmp = stk.pop();
}
stk.push(tmp.right);
}
return cur.data;
}//end of next()
public void remove()
{
}
}//end of MyIterator
/*****************************************************
*
* the Node class
*
******************************************************/
private class Node<T>
{
private T data;
private Node<T> left, right;
public Node(T data, Node<T> l, Node<T> r)
{
left = l; right = r;
this.data = data;
}
public Node(T data)
{
this(data, null, null);
}
public String toString()
{
return data.toString();
}
} //end of Node
}//end of BST
class MyComp1 implements Comparator<Integer>
{
public int compare(Integer x, Integer y)
{
return y-x;
}
}
/* output:-
1 2 4 5 7
Tostring of BST: [1,5,2,4,7,]
Search of Element in BST: false
count no. of leaves : 2
clone object[1,5,2,4,7,]
checking equals of 2 objects: false
*/