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

Java Program With Strings & Integers
Homework Solution
$20.00
Java
Programming
Coding
Strings
Integers
Computer Science
Symbols
Special Characters
Reading
Writing
Rows
Columns
Statements
Conditions
Loops
Maze Program in Java
Homework Solution
$50.00
Computer Science
Java
Programming
Recursion
Backtracking
Algorithms
Maze Problem
Steps
Variables
Statements
Functions
Classes
Arrays
Strings
Integers
Input
Output
Java Program And UML Diagram For Divers
Homework Solution
$20.00
Java
Programming
Computer Science
Coding
Divers
Testers
UML Diagram
Methods
Loops
Statements
Average Scores
Variables
Input Files
Output Files
Contest
Winner
Records
Data Sets
Java Programming: Strings, Odd & Even Numbers, Absolute Values
Homework Solution
$25.00
Java
Programming
Computer Science
Odd Numbers
Even Numbers
Integers
Absolute Values
While Loop
IF-Statements
Data Sets
Input
Output
Sum
Functions
Methods
Strings
Lexicography Order
Airplane Seating Chart System Simulation in Java
Homework Solution
$30.00
Java
Programming
Codes
Computer Science
Algorithms
Airplane Seating Chart
Simulation
Tickets
Seats
Diagrams
Coordinates
Customers
Passengers
Methods
Statements
Variables
Java Problems: Student Details & Fibonacci Series
Homework Solution
$20.00
Java
Programming
OOP
Computer Science
Fibonacci Series
Students
Classes
Instances
Loops
Conditions
Statements
Variables
Integers
Mathematics
Get help from a qualified tutor
Live Chats