Question

Create a binary search tree that implements the following interface:

public interface BSTInterface<T> {

boolean isEmpty();

void add(T item);
boolean contains(T item);
void delete(T item);
void removeAll();
}

In addition to the methods required by the interface, provide the following:

a) Throw custom exception, BSTException, for the following conditions:
a. Attempt to add an item already in the tree

b. Attempt to delete an item not in the tree
b) methods to print the tree in in-­‐order, pre-­‐order and post-­‐order traversal

c) methods to save the tree to a file as comma separated values in in-­‐order, pre-­‐order and post-­‐ order

d) methods to report the following details about the tree:

1. number of nodes
2. minimum and maximum height of the tree
3. isLeaf(T item) which indicates if the value supplied is a leaf node.
4. isBalanced(), isFull(), isComplete() methods which return a boolean value indicating if the tree is a balanced tree, a full tree and a complete tree respectively

Write a test program to use your Binary Search Tree. In this program, you will create three trees: the first will contain Integers, the second Doubles, and the third String. You will start with an empty BST for each, typed appropriately.

a) Add 15-­‐30 items to each tree (make each a different number).
b) Report the number of nodes, min/max height of the tree, and if the tree is full, complete and balanced.
c) Print the trees using the three print methods.
d) Retrieve and report two examples of a leaf nodeand two examples of a non-­‐leaf node from each tree – use your isLeaf() method to report if it is a leaf or not.
e) Delete two internal nodes and two leaf nodes from each tree.
f) Report the number of nodes, min/max height of the tree, and if the tree isfull, complete and balanced.
g) Print the trees using the three print methods.

Finally, create a method called treeBuildFromSorted(T[] items) that accepts an array of items. Using the array, the method must build a new balanced tree.

For each of your three trees in your test program, demonstrate this method by saving one of the traversals (in, pre or post) to a file, reading the file back into an appropriate array from the file, then using the array to rebuild the tree with the buildTreeFromSorted method.

Demonstrate the rebuild works by printing the in-­‐order, pre-­‐order, and post-­‐order traversals of the tree before and after the rebuild.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

public void add(T item) throws BSTException
{
if(this.contains(item))
{
System.out.println(item);
throw new BSTException("Item already in tree, can't add!");
}
else
{
Node node = head;
while(true)
{
if(node == null)
{
node = new Node(item);
if(head == null)
head = node;
break;
}
else if(item.compareTo(node.data) < 0)
if(node.left == null)
{
node.left = new Node(item);
break;
}
else
node = node.left;
else
if(node.right == null)
{
node.right = new Node(item);
break;
}
else
node = node.right;
}
size++;
}
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

Strong Password Creation Game for Kids
Homework Solution
$35.00
Computer Science
Java Programming
Passwords
GUI
Object Composition
UML Diagram
Random Access
Classes
Files
Linear Dungeon Exploration in Java
Homework Solution
$60.00
Computer Science
Java Programming
Nodes
Objects
Variables
Linked Lists
Text Files
Monsters
Rooms
Classes
Java Programming Projects
Homework Solution
$90.00
Computer Science
Java Programming
Sorting Algorithms
Recursion
Critical Operations
Methods
Interfaces
Significance
Variance
Big O Analysis
Papers
Cryptography Problems in Java
Homework Solution
$30.00
Computer Science
Java Programming
Cryptography
Caesar Shift
Alphabet
Hierarchy
Classes
Inheritance
Functions
Decryption
Path Planning in Java
Homework Solution
$60.00
Computer Science
Java Programming
Path Planning
Drones
Maps
Tower
Power
Batteries
Labels
Parameters
Objects
Java Program For ABC Enterprise
Homework Solution
$40.00
Computer Science
Java Programming
ABC Enterprise
Database
Array List
Products
Manufactures
String
Get help from a qualified tutor
Live Chats