Project: Treeset

Project: TreeSet

Develop class TreeSet as a generic collection that stores nodes in a binary search tree data structure. Each node has a reference to data, a left binary search, and a right binary search tree. The type to be stored must be limited to types that implement the Comparable interface or any interface that extends Comparable.

publicclassTreeSet<E extends Comparable<E> {

The required method headings are provided below with their behavior listed as comments.

// Add element to this TreeSet and return true keeping this a TreeSet. If element is found

// to already exist, do not change this TreeSet, simply return false.

publicboolean insert(E element)

// The number of elements in this TreeSet, which should be 0 when first constructed.

publicint size()

// The longest path in this TreeSet beginning at the root.

// Note: An empty tree has a height of -1.

publicint height()

// Return one string that concatenates all elements in this TreeSet as they are visited
//inorder. Elements are separated by spaces like "1 4 9" in this TreeSet:

// 4

// / \

// 1 9

public String toStringInorder()

// Return one string that concatenates all elements in this TreeSet as they are visited
// pre order. Elements are separated by spaces like "4 1 9" in this TreeSet:

public String toStringPreorder()

// Return one string that concatenates all elements in this TreeSet as they are visited
// post order. Elements are separated by spaces like "1 9 4" in this TreeSet:

public String toStringPostorder()

// Return true is search equals an element in this TreeSet.

publicboolean contains(E search)

// Return an array that has capacity equal to this TreeSet's size with the

// minimum value at index 0 and the maximum value at index array length-1

public Object[] toArray()

// Return the element in this TreeSet that is greater than all other elements.

// If this TreeSet is empty, return null.

public E max()

// Return the number of leafs in this TreeSet. Note: An empty tree has 0 leafs.

publicint numberOfLeafs()

// Return the intersection of this TreeSet and the other TreeSet. Return a new

// TreeSet. Do not modify this TreeSet or the other TreeSet. Return a new

public TreeSet<E> intersection(TreeSet<E> other)

// Return true if two different TreeSet objects have the same exact structure. Each node

// must have the same number of nodes on every level, the same height, the same size, the

// same number of leaves, and the same number of internal nodes. Most importantlyeach
// corresponding node must have the same childerm (0, 1,or 2) in the same place. The

// data need NOT need be equals. Each of these 4 pairs of TreeSets have the sameStructure:
//

// M P | Lmn Rts | 5 55 | 3 999

// / \ / \ | / / | \ \ | / /

// B R F Q | Abc Lmn | 10 999 | 2 888

// \ \ \ \ | | / \ / \ | / /

// F Z J R | | 8 77 8 12 | 1 777

//

// Empty trees also have the same structure.

//

// All four pairs of these TreeSets do NOT have the sameStucture (do not consider the data)

//

//

// M M | Rts Rts | 5 5 | 3 999

// / \ / \ | / / | \ \ | / / \

// B R B Z | Lmn Abc | 10 12 | 2 888 1001

// \ \ \ / | / \ | / \ / | /

// F Z F R | Abc Lmn | 8 12 10 | 1

// | | / |

// | | 8 |

//

// Precondition: E is the same for both TreeSets

publicboolean sameStructure(TreeSet<E> other)

// If element equals an element in this TreeSet, remove it and return true. Return false

// whenever element is not found. In all cases, this TreeSet must remain a true TreeSet.

// Here is the algorithm discussed in section: BSTRemoveGeneric.pdf

publicboolean remove(E element)

Grading Criteria

100 pts for WebCat Problem Coverage and Code Coverage