Need insert, search, and remove.

import java.util.*;

public class BST> extends AbstractTree

{

protected TreeNode root;

protected int size = 0;

/**

* Create a default binary tree

*/

public BST()

{

}

/**

* Create a binary tree from an array of objects

*/

public BST (E[] objects)

{

for (int i = 0; i < objects.length; i++)

{

insert (objects[i]);

}

}

/**

* Get the number of nodes in the tree

*/

@Override

public int getSize()

{

return size;

}

/**

* Returns the root of the tree

*/

public TreeNode getRoot()

{

return root;

}

/**

* This inner class is static, because it does not access

* any instance members defined in the BST class

*/

public static class TreeNode> implements Comparable>

{

protected E element;

protected TreeNode left;

protected TreeNode right;

public TreeNode (E e)

{

element = e;

}

@Override

public int compareTo (TreeNode node)

{

return element.compareTo (node.element);

}

}

/**

* Remove all elements from the tree

*/

public void clear()

{

root = null;

size = 0;

}

/**

* Returns true if the element is in the tree

*/

@Override

public boolean search (E e)

{

return search (root, e);

}

// Recursively finds the element in the Tree

// Returns true if the element is in the tree

protected boolean search (TreeNode subRoot, E e)

{

// todo for Lab6

}

/**

* Insert element o into the binary tree

* Return true if the element is inserted successfully

*/

@Override

public boolean insert (E e)

{

return insert (null, root, e);

}

// Recursively finds the location to place the element in the Tree

// Returns true if the element is placed in the tree

public boolean insert (TreeNode parent, TreeNode current, E e)

{

// todo for Lab6

}

/**

* Delete an element from the binary tree.

* Return true if the element is deleted successfully

*/

@Override

public boolean delete (E e)

{

boolean removed = remove (null, root, e);

if (removed)

{

size--;

}

return removed;

}

// Recursively Deletes element from tree.

public boolean remove (TreeNode parent, TreeNode tree, E e)

{

// todo for Lab6

}

// Deletes the node pointed to by tree.

// The user's data in the node pointed to by tree is no

// longer in the tree. If tree is a leaf node or has only

// one non-NULL child pointer the node pointed to by tree is

// deleted; otherwise, the user's data is replaced by its

// logical predecessor (rightmost node) and that is deleted.

public void deleteNode (TreeNode parent, TreeNode tree)

{

// todo for Lab6

}

/**

* Inorder traversal from the root

*/

@Override

public void inorder()

{

inorder (root);

}

/**

* Inorder traversal from a subtree

*/

protected void inorder (TreeNode subRoot)

{

if (subRoot == null)

{

return;

}

// Recursively traverse the left subtree

inorder (subRoot.left);

// Display the current node

System.out.print (subRoot.element + " ");

// Recursively traverse the right subtree

inorder (subRoot.right);

}

/**

* Postorder traversal from the root

*/

@Override

public void postorder()

{

postorder (root);

}

/**

* Postorder traversal from a subtree

*/

protected void postorder (TreeNode subRoot)

{

if (subRoot == null)

{

return;

}

// Recursively traverse the left subtree

postorder (subRoot.left);

// Recursively traverse the right subtree

postorder (subRoot.right);

// Display the current node

System.out.print (subRoot.element + " ");

}

/**

* Preorder traversal from the root

*/

@Override

public void preorder()

{

preorder (root);

}

/**

* Preorder traversal from a subtree

*/

protected void preorder (TreeNode subRoot)

{

if (subRoot == null)

{

return;

}

// Display the current node

System.out.print (subRoot.element + " ");

// Recursively traverse the left subtree

preorder (subRoot.left);

// Recursively traverse the right subtree

preorder (subRoot.right);

}

/**

* Returns a path from the root

* leading to the specified element

*/

public MyArrayList > path (E e)

{

MyArrayList > list = new MyArrayList<>();

TreeNode current = root; // Start from the root

while (current != null)

{

list.add (current); // Add the node to the list

int comp = e.compareTo (current.element);

if (comp < 0)

{

current = current.left; // Go left

}

else if (comp > 0)

{

current = current.right; // Go right

}

else

{

break;

}

}

return list; // Return an array list of nodes in order

}

/**

* Obtain an iterator. Use inorder.

*/

@Override

public Iterator iterator()

{

return new InorderIterator();

}

// Inner class InorderIterator

private class InorderIterator implements Iterator

{

// Store the elements in a list

private MyArrayList list = new MyArrayList<>();

// Point to the current element in list

private int current = 0;

public InorderIterator()

{

inorder(); // Traverse BST; store elements in list

}

/**

* Inorder traversal from the root

*/

private void inorder()

{

inorder (root);

}

/**

* Inorder traversal from a subtree

*/

private void inorder (TreeNode root)

{

if (root == null)

{

return;

}

inorder (root.left);

list.add (root.element);

inorder (root.right);

}

/**

* More elements for traversing?

*/

@Override

public boolean hasNext()

{

return(current < list.size());

}

/**

* Get the current element and move to the next

*/

@Override

public E next()

{

return list.get (current++);

}

/**

* Remove the current element

*/

@Override

public void remove()

{

// Delete the current element

delete (list.get (current));

// Clear the list

list.clear();

// Rebuild the list

inorder();

}

}

}