Binary Tree

You might want to read these notes about trees before working on this program :
  Trees Introduction

/*** Binary Tree *******************************************************\
A BINARY SEARCH TREE stores Strings in "alphabetical order",
in the sense that it's very easy to print an alphabetical
list of the Strings. Here is an example of a properly ordered
binary search tree.

             Mildred
           /         \
       Chuck          Sue
      /     \        /   \
    Alex   Ellen   Pete  Tommy

This program reads strings from the keyboard, in any order.
Each word is inserted into the binary search tree in the proper position.
Then an in-order traversal prints the words in alphabetical order.
This concept could be used to sort a text file, if the input came
from a text file and the output went back into the same file.
\***********************************************************************/

public class BinaryTree
{
   class TreeNode
   {
      String data;
      TreeNode leftChild;
      TreeNode rightChild;

      TreeNode(String info)
      {
         data = info;
         leftChild = null;
         rightChild = null;
      }
   }

   TreeNode root = null;

   public BinaryTree()
   {
      makeTree();
      showTree(root);
   }

   public void makeTree()
   {
      root = null;
      String word = "";
      do
      {
         word = input("Type a word (xxx to quit):");
         if (!word.equals("xxx"))
         {  addTreeNode(word);  }
      } while(!word.equals("xxx"));
   }

   public void addTreeNode(String word)
   {
      boolean done = false;
      if (root == null)
      {
         root = new TreeNode(word);
         done = true;
      }

      TreeNode temp = root;
      while (!done)
      {
         if (temp.data.equals(word))
         {  done = true;  }             // word found, so don't add
         else if (word.compareTo(temp.data)<0)
         {
            if (temp.leftChild == null)
            {  temp.leftChild = new TreeNode(word);
               done = true;
            }
            else
            {  temp = temp.leftChild;  }
         }
         else
         {
            if (temp.rightChild == null)
            {  temp.rightChild = new TreeNode(word);
               done = true;
            }
            else
            {  temp = temp.rightChild;  }
         }
      }
      return;
   }

   public void showTree(TreeNode here)
   {
      if (here == null)
      {  return;  }
      else
      {
         showTree(here.leftChild);
         System.out.println(here.data);
         showTree(here.rightChild);
      }
   }

   public static void main(String[] args)
   {  new BinaryTree(); }
  
   public void output(String message)
   {  javax.swing.JOptionPane.showMessageDialog(null,message);  }
  
   public String input(String prompt)
   {  return javax.swing.JOptionPane.showInputDialog(null,prompt);  }
}
//****************************************************************\\

(1) Run the program.  Try typing in a variety of lists of words,
    and check that each time the program prints the words in
    correct alphabetical order.
 
(2) Change "showTree" so that it prints the names in REVERSE order.
    This only requires changing the order of the commands in
    the "showTree" method.
   
(3) Add a new method called "sampleData" that automatically inserts
    8 names into the tree when the program starts.
   
(4) Change the program so that it starts by inserting sample data,
    and then inputs a name to SEARCH for.  Then it uses a SEARCH
    method to TRAVERSE the tree and then tell whether the name
    was found or not found.  The SEARCH method is very similar
    to the "showTree" method, except that it should not print
    all the names - instead, it checks whether the right name
    is found and print "found", and then quit.  If it makes it
    all the way through the tree without printing "found", then
    it prints "not found" at the end.

\\****************************************************************//