BST java hw #18

/*
* Max Bratnichenko
* CSCI-401
* Height and Breafth in BST
*/

//HeightandBFT
public class HeightBFT
{
    //main method
    public static void main(String[]args)
    {
        //Create an object for BST of type String
        BST<String> stringTree = new BST<String>();
        stringTree.insert("Max");
        stringTree.insert("Tom");
        stringTree.insert("Joe");
        stringTree.insert("Ron");
        stringTree.insert("Sue");
        stringTree.insert("Cal");
        stringTree.insert("Pat");

        //call the traversal methods of stringTree
        System.out.print("Inorder (sorted): ");
        stringTree.inorder ();
        System.out.print("\n Postorder: ");
        stringTree.postorder();
        System.out.print("\n Preorder: ");
        stringTree.preorder();

        //Calling the height method for tree of strings
        System.out.print("\n Height of the tree is : "
        + stringTree.height());

        //Calling the breadtFirstTraversal method for tree of strings
        System.out.println("\n Breadth frist traversal: ");
        stringTree.breadthFirstTraversal();

        //Creating object for BST
        Integer[] numbers= {2,4,3,1,8,5,6,7};
        BST<Integer> intTree = new BST<Integer>(numbers);

        //call traverse methods of intTree
        System.out.println("\n Inorder (sorted): ");
        intTree.inorder();
        System.out.print("\n Postorder: ");
        intTree.postorder();

        //call height method for tree of ints
        System.out.print("\n Height of the tree: " + intTree.height());

        //call breadthFirstTraversal method free of ints
        System.out.println("\n Breadth first traversal: ");
        intTree.breadthFirstTraversal();

    }
}

///////////////////////////////////////////////////////////////////



import java.util.*;

public class BST<E extends Comparable<E>>extends AbstractTree<E>
{
    protected  TreeNode<E>  root;
    protected static int size = 0;

    //Default binary search tree
    public BST() {
    }

    //binary search tree from an array of objects */
    public BST(E[] objects) {
        for (int i = 0; i < objects.length; i++)
            insert(objects[i]);
    }


     // Return true if the element is in the tree */
    public boolean search(E e) {
        TreeNode<E> current = root; // Start from the root

        while (current != null) {
            if (e.compareTo(current.element) < 0) {
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                current = current.right;
            } else
                // element matches current.element
                return true; // Element is found
        }

        return false;
    }

    /**
     * Insert element e into the binary search tree. Return true if the element
     * is inserted successfully.
     */

    public boolean insert(E e) {
        if (root == null)
            root = createNewNode(e); // Create a new root
        else {
            // Locate the parent node
            TreeNode<E> parent = null;
            TreeNode<E> current = root;
            while (current != null)
                if (e.compareTo(current.element) < 0) {
                    parent = current;
                    current = current.left;
                } else if (e.compareTo(current.element) > 0) {
                    parent = current;
                    current = current.right;
                } else
                    return false; // Duplicate node not inserted

            // Create the new node and attach it to the parent node
            if (e.compareTo(parent.element) < 0)
                parent.left = createNewNode(e);
            else
                parent.right = createNewNode(e);
        }

        size++;
        return true; // Element inserted
    }

    protected TreeNode<E> createNewNode(E e) {
        return new TreeNode<E>(e);
    }
    @Override/** Inorder traversal from the root */
    public void inorder() {
        inorder(root);
    }

    /** Inorder traversal from a subtree */
    protected void inorder(TreeNode<E> root) {
        if (root == null)
            return;
        inorder(root.left);
        System.out.print(root.element + " ");
        inorder(root.right);
    }

    @Override/** Postorder traversal from the root */
    public void postorder() {
        postorder(root);
    }

    /** Postorder traversal from a subtree */
    protected void postorder(TreeNode<E> root) {
        if (root == null)
            return;
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.element + " ");
    }

    @Override/** Preorder traversal from the root */
    public void preorder() {
        preorder(root);
    }

    /** Preorder traversal from a subtree */
    protected void preorder(TreeNode<E> root) {
        if (root == null)
            return;
        System.out.print(root.element + " ");
        preorder(root.left);
        preorder(root.right);
    }

    /**
     * This inner class is static, because it does not access any instance
     * members defined in its outer class
     */
    public static class TreeNode<E extends Comparable<E>> {
        protected E element;
        protected TreeNode<E> left;
        protected TreeNode<E> right;

        public TreeNode(E e) {
            element = e;
        }

        public int getSize() {
            return size;
        }

        /** Returns the root of the tree */
        public TreeNode<E> getRoot() {
            return root;
        }

        /** Returns a path from the root leading to the specified element */
        public java.util.ArrayList<TreeNode<E>> path(E e) {
            java.util.ArrayList<TreeNode<E>> list = new java.util.ArrayList<TreeNode<E>>();
            TreeNode<E> current = root; // Start from the root

            while (current != null) {
                list.add(current); // Add the node to the list
                if (e.compareTo(current.element) < 0) {
                    current = current.left;
                } else if (e.compareTo(current.element) > 0) {
                    current = current.right;
                } else
                    break;
            }

            return list; // Return an array of nodes
        }

        /**
         * Delete an element from the binary search tree. Return true if the
         * element is deleted successfully. Return false if the element is not
         * in the tree.
         */
        public boolean delete(E e) {
            // Locate the node to be deleted and also locate its parent node
             TreeNode<E> parent = null;
             TreeNode<E> current = root;
             while (current != null) {
             if (e.compareTo(current.element) < 0) {
             parent = current;
             current = current.left;
             }
             else if (e.compareTo(current.element) > 0) {
             parent = current;
             current = current.right;
             }
             else
             break; // Element is in the tree pointed at by current
             }

             if (current == null)
             return false; // Element is not in the tree

             // Case 1: current has no left children
             if (current.left == null) {
                // Connect the parent with the right child of the current node
                 if (parent == null)
                     root = current.right;
                      else {
                      if (e.compareTo(parent.element) < 0)
                     parent.left = current.right;
                      else
                      parent.right = current.right;
                      }
                      }
                      else {
                      // Case 2: The current node has a left child.
                      // Locate the rightmost node in the left subtree of
                      // the current node and also its parent.
                      TreeNode<E> parentOfRightMost = current;
                      TreeNode<E> rightMost = current.left;

                      while (rightMost.right != null) {
                      parentOfRightMost = rightMost;
                      rightMost = rightMost.right; // Keep going to the right
                      }

                      // Replace the element in current by the element in rightMost
                      current.element = rightMost.element;

                      // Eliminate rightmost node
                      if (parentOfRightMost.right == rightMost)
                      parentOfRightMost.right = rightMost.left;
                      else
                      // Special case: parentOfRightMost == current
                      parentOfRightMost.left = rightMost.left;
                      }

                      size --;
                      return true; // Element deleted
                      }

        ///////////////////////BreadthFirstTraversal Method//////////////////////
        //Displays elements of tree in order, level by level
        public void breadthFirstTraversal()
        {
            List<TreeNode<E>> list=new
                    ArrayList<TreeNode<E>>();
            if(root != null)
                list.add(root);

            TreeNode<E> current;

            while(!list.isEmpty()){
                current= (TreeNode<E>)list.remove(0);
                //display the element of the tree
                System.out.print(current.element + "");

                if(current.left != null)
                    list.add(current.left);
                if(current.right != null)
                    list.add(current.right);
            }
        }

        ///////////////////////////Height Method///////////////////////
        //Find and return the height of the tree
        public int height()
        {
            return height(root);
        }

        //helper method for height
        private int height(TreeNode<E> root)
        {
            if(root ==null)
            {
                return 0;
            }
            else
            {
                return 1 + Math.max(height(root.left),height(root.right));
            }
        }
    }

    /** Obtain an iterator. Use inorder. */
    public java.util.Iterator<E> iterator() {
        return new InorderIterator();
    }

    // Inner class InorderIterator
    private class InorderIterator implements java.util.Iterator<E> {
        // Store the elements in a list
        private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
        private int current = 0; // Point to the current element in list

        public InorderIterator() {
            inorder(); // Traverse binary tree and store elements in list
        }

        /** Inorder traversal from the root */
        private void inorder() {
            inorder(root);
        }

        /** Inorder traversal from a subtree */
        private void inorder(TreeNode<E> root) {
            if (root == null)
                return;
            inorder(root.left);
            list.add(root.element);
            inorder(root.right);
        }

        /** More elements for traversing? */
        public boolean hasNext() {
            if (current < list.size())
                return true;

            return false;
        }

        /** Get the current element and move to the next */
        public E next() {
            return list.get(current++);
        }

        /** Remove the current element */
        public void remove() {
            delete(list.get(current)); // Delete the current element
            list.clear(); // Clear the list
            inorder(); // Rebuild the list
        }
    }

    /** Remove all elements from the tree */
    public void clear() {
        root = null;
        size = 0;
    }
}


//////////////////////////////////////////////////////////

public abstract class AbstractTree<E extends Comparable<E>>
implements Tree<E>
{
//Inorder traversal from the root
public void inorder(){}

//Postorder traversal from the root
public void postorder(){}

//Preorder traversal from the root
public void preorder(){}

//Check if tree empty
public boolean isEmpty()
{
    return getSize() ==0;
}

//Retrun an interator to traverse elements in the tree
public java.util.Iterator<E> iterator()
{
    return null;
}

}

////////////////////////////////////////////////////////////////////////////////////////////////////

public interface Tree<E extends Comparable<E>>
{
//return true if the element is in the tree
public boolean search(E e);

//Insert element e into the binary tree
public boolean insert (E e);

//Delete the specified element from tree
public boolean delete(E e);

//Inorder traversal
public void inorder();

//Postorder traversal
public void postorder();

//Preorder traversal
public void preorder();

//get number of nodes
public int getSize();

//return true if tree empty
public boolean isEmpty();

//Return iterator to traverse elements
public java.util.Iterator<E> iterator();
}