Binary Search Tree

12 points

In this program you modify a Binary Search Tree program.  The program is listed at the end of section 16.5 in the text and given to you below for download.  You also work with the TreeSet class from the standard Java library.  A TreeSet is a Set that is implemented as a Binary Search Tree.

Here is the output from my program:
 

BINARY SEARCH TREE PROGRAM

Add 9 Original Star Trek names to each tree

Check for the presence of a few names:
Is Kirk in my tree: true
Is Kirk in Java's tree: true
Is Roddenberry in my tree: false
Is Roddenberry in Java's tree: false

Remove 'Sulu'

Print list in sorted order:
Chapel
Chekhov
Kirk
McCoy
Rand
Scott
Spock
Uhura

Chapel
Chekhov
Kirk
McCoy
Rand
Scott
Spock
Uhura

Return 'Sulu' to each tree

Find 'smallest' element:
Chapel
Chapel

Do an inorder traversal and call 'visit1()' to modify each Node

Print list in sorted order:
Original Star Trek character: Chapel
Original Star Trek character: Chekhov
Original Star Trek character: Kirk
Original Star Trek character: McCoy
Original Star Trek character: Rand
Original Star Trek character: Scott
Original Star Trek character: Spock
Original Star Trek character: Sulu
Original Star Trek character: Uhura

Do a preorder traversal of the tree

At each Node, call visit2() to modify the Node

Print list, using inorder traversal:
4 Original Star Trek character: Chapel
3 Original Star Trek character: Chekhov
2 Original Star Trek character: Kirk
1 Original Star Trek character: McCoy
0 Original Star Trek character: Rand
6 Original Star Trek character: Scott
5 Original Star Trek character: Spock
8 Original Star Trek character: Sulu
7 Original Star Trek character: Uhura

Do a postorder traversal of the tree

At each Node, call visit3() to modify the Node

Print list, using inorder traversal:
A 4 Original Star Trek character: Chapel
B 3 Original Star Trek character: Chekhov
C 2 Original Star Trek character: Kirk
D 1 Original Star Trek character: McCoy
I 0 Original Star Trek character: Rand
E 6 Original Star Trek character: Scott
H 5 Original Star Trek character: Spock
F 8 Original Star Trek character: Sulu
G 7 Original Star Trek character: Uhura

Set up a new binary search tree, and populate it with Integer objects

Find the average of these integers
The average is 10.0

Starting Point

You can download BinarySearchTree.java and BST_Main.java to use as starting points in writing your program. (Right-click on the links, choose 'Save Target As' and add the '.java' extension to each file name.)  The Java files contain instructions on writing code.