Program to Sort Binary Trees

import java.io.DataInputStream;   // to load DataInputStream class 


public class BinaryTreeSort
{




   static class TreeNode
   {
      // An object of type TreeNode represents one node
      // in a binary tree of integers.
      int item;         // The data in this node.
      TreeNode left;    // Pointer to left subtree.
      TreeNode right;   // Pointer to right subtree.
      TreeNode(int str)
      {
             // Constructor.  Make a node containing the specified integer.
         item = str;
      }
   }  // end nested class TreeNode


   
   static TreeNode root;  // Pointer to the root node in a binary tree.  This
                          // tree is used in this program as a binary sort tree.
                          // When the tree is empty, root is null.
   
   


   public static void main(String[] args)
   {
      
int x[]=new int[25];
int i,n = 0;
DataInputStream in = new DataInputStream(System.in); 


try
{
 System.out.print("Enter how many numbers to be sorted : ");
                 n = Integer.parseInt(in.readLine());
                  System.out.println("Enter "+n+" numbers in any order....");
                  for(i=0;i<n;i++)
                  {
                System.out.print("\t\tElement x["+(i+1)+"]=");
                   x[i] = Integer.parseInt(in.readLine());
                  }
}
catch(Exception e) {  System.out.println("I/O Error");   }




        for( i=0;i<n;i++)
        {
             treeInsert(x[i]);  // Add user's number to the tree.
             System.out.println("\nThe tree contains " + countNodes(root) + " items.");
             System.out.println("\nContents of tree:\n");
             treeList(root);
        }
            
   }  // end main()
   
   
   static void treeInsert(int newItem)
   {
          // Add the item to the binary sort tree to which the global
          // variable "root" refers.  (Note that root can't be passed as
          // a parameter to this routine because the value of root might
          // change, and a change in the value of a formal parameter does
          // not change the actual parameter.)
      if ( root == null )
      {
             // The tree is empty.  Set root to point to a new node containing
             // the new item.  This becomes the only node in the tree.
             root = new TreeNode( newItem );
             return;
      }
      TreeNode runner;  // Runs down the tree to find a place for newItem.
      runner = root;   // Start at the root.
      while (true)
     {
         if ( newItem<(runner.item))
         {
                  // Since the new item is less than the item in runner,
                  // it belongs in the left subtree of runner.  If there
                  // is an open space at runner.left, add a new node there.
                  // Otherwise, advance runner down one level to the left.
            if ( runner.left == null )
            {
               runner.left = new TreeNode( newItem );
               return;  // New item has been added to the tree.
            }
            else
               runner = runner.left;
         }
         else
        {
                  // Since the new item is greater than or equal to the item in
                  // runner it belongs in the right subtree of runner.  If there
                  // is an open space at runner.right, add a new node there.
                  // Otherwise, advance runner down one level to the right.
            if ( runner.right == null )
            {
               runner.right = new TreeNode( newItem );
               return;  // New item has been added to the tree.
            }
            else
               runner = runner.right;
        }
      } // end while
   }  // end treeInsert()
   
   
   static boolean treeContains( TreeNode root, int item )
  {
          // Return true if item is one of the items in the binary
          // sort tree to which root points.   Return false if not.
      if ( root == null )
      {
            // Tree is empty, so it certainly doesn't contain item.
         return false;
      }
      else if ( item ==(root.item) )
           {
              // Yes, the item has been found in the root node.
               return true;
           }
      else if ( item < (root.item) )
           {
               // If the item occurs, it must be in the left subtree.
               return treeContains( root.left, item );
           }
      else
      {
             // If the item occurs, it must be in the right subtree.
             return treeContains( root.right, item );
      }
   }  // end treeContains()
   


   static void treeList(TreeNode node)  // Inorder Traversal of tree
  {
      if ( node != null )
      {
          treeList(node.left);                   // Print items in left subtree.
          System.out.println("  " + node.item);  // Print item in the node.
          treeList(node.right);                  // Print items in the right subtree.
      }
   } // end treeList()
   


   static int countNodes(TreeNode node)
  {
         // Count the nodes in the binary tree to which node 
         // points.  Return the answer.
       if ( node == null )
       {
          // Tree is empty, so it contains no nodes.
          return 0;
       }
       else
       {
          // Add up the root node and the nodes in its two subtrees.
          int leftCount = countNodes( node.left );
          int rightCount = countNodes( node.right );
          return  1 + leftCount + rightCount;  
       }
   } // end countNodes()
   


} // end class BinaryTreeSort