Binary Search Tree

Background:

In previous lessons, you stored a data file (file20.txt) in different data structures: an array, a linked list, and a doubly-linked list. In the linked-list labs in Lesson AB29, we built the data structure, printed it out, searched for values, and deleted values. We will solve the same fundamental tasks using a binary tree as the data structure.

Instructions:

1. You may assume the following type definitions apply in this lab assignment.

   public class TreeNode
   {
     private Object value;
     private TreeNode left;
     private TreeNode right;
   
     public TreeNode( Object initValue, TreeNode initLeft, TreeNode initRight )
     {
       value = initValue; left = initLeft; right = initRight;
     }
   
     public Object getValue()
     {
       return value;
     }
   
     public TreeNode getLeft()
     {
       return left;
     }
   
     public TreeNode getRight()
     {
       return right;
     }
   
     public void setValue( Object theNewValue )
     {
       value = theNewValue;
     }
   
     public void setLeft( TreeNode theNewLeft )
     {
       left = theNewLeft;
     }
   
     public void setRight( TreeNode theNewRight )
     {
       right = theNewRight;
     }
   }

2. Build a main menu with the following choices.

   (1) Read a file from disk, build the binary tree
   (2) Print the tree in order
   (3) Count the nodes in the tree

3. Implement a Binary Search Tree class (BSTree) with the following methods:

   1. public BSTree()
   2. public void insert(Comparable next)
   3. private TreeNode insertHelper( TreeNode root, Comparable next )
   4. public void printInOrder()
   5. private void printInorderHelper( TreeNode root )
   6. public int countNodes()
   7. private int countNodesHelper( TreeNode root )