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 with the following methods:

   1. public BinarySearchTree()
   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)