Java tree help

[Paul Reed]

I am trying to complete an assignment and have become quite stumped. I am going along with the logic I have formed in my head and on paper yet im getting very strange output that is preventing me from completing my program.
Here is the problem:


Start with the tree.java program (Listing 8.1) and modify it to create a binary
tree from a string of letters (like A, B, and so on) entered by the user. Each
letter will be displayed in its own node. Construct the tree so that all the nodes
that contain letters are leaves. Parent nodes can contain some non-letter
symbol like +. Make sure that every parent node has exactly two children.
Don’t worry if the tree is unbalanced. Note that this will not be a search tree;
there’s no quick way to find a given node. You may end up with something
like this:


It also says all Letters must be Leaves

Now I had it almost similar to that picture, but it wasn't right. So ive been working on it but im getting some very strange (and frustrating) output from the following methods.

Ive included the display method just for reference. The book told me to use it so I haven't edited it. I believe my main issue is with my (incomplete) insert() method. The output goes into an infinite loop despite having a return statement break the while loop when a character is inserted.
The way I see to solve the problem is just add a (+) whenever a new subtree needs to be created. Say I add A and B, then it first creates a subtree at the root with a (+) and afterwards lists A and B as its leaves. If I insert a C, it should be able to simply move to the right child of the root and deposit the C there.

package pkg4333_hwk1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;


/**
 *
 * @author preed_000
 */
 class Main {

    /**
     * @param args the command line arguments
     */
     public static void main(String[] args) throws IOException {

         System.out.println("Please enter a string of letters. No numbers/symbols are allowed.");

         Scanner cin = new Scanner(System.in);
         String input = cin.next();

        
         
         char[] cArray = input.toCharArray(); // split the string into characters
        
    
      Tree theTree = new Tree();
      for (int i = 0; i < input.length(); i++ )
          theTree.insert( cArray[i]);
      
     System.out.println("The characters have been inserted.");
     
      while(true)
         {
         System.out.print("Enter first letter of show, ");
         System.out.print("insert, find, delete, or traverse: ");
         int choice = getChar();
         switch(choice)
            {
            case 's':
               theTree.displayTree();
               break;
            case 'i':
                System.out.println("Type the characters you would like to insert");
                String in = cin.next();
                char [] cArray1 = in.toCharArray();
                
                //created another character array because there is no telling if 
                //the first cArray will be large enough to hold the new string
                for (int i = 0; i < cArray1.length; i++)
                {
                    
                    theTree.insert(cArray1[i]);
                }
                break;
          
           
            default:
               System.out.print("Invalid entry\n");
            }  // end switch
         }  // end while
      }  // end main()
// -------------------------------------------------------------
   public static String getString() throws IOException
      {
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      String s = br.readLine();
      return s;
      }
// -------------------------------------------------------------
   public static char getChar() throws IOException
      {
      String s = getString();
      return s.charAt(0);
      }
//-------------------------------------------------------------
   public static int getInt() throws IOException
      {
      String s = getString();
      return Integer.parseInt(s);
      }
// -------------------------------------------------------------
   }  // end class TreeApp

package pkg4333_hwk1;

import java.io.*;
import java.util.*;               // for Stack class
////////////////////////////////////////////////////////////////

class Node {

    public char sData;              // data item (key)
    //public double dData;           // data item
    public Node leftChild;         // this node's left child
    public Node rightChild;        // this node's right child

    public void displayNode() // display ourself
    {
        System.out.print('{');
        System.out.print(sData);
        System.out.print(", ");
        //System.out.print(dData);
        System.out.print("} ");
    }
}  // end class Node
////////////////////////////////////////////////////////////////

class Tree {

    private Node root;             // first node of tree

// -------------------------------------------------------------
    public Tree() // constructor
    {
        root = null;
    }            // no nodes in tree yet
// -------------------------------------------------------------

// -------------------------------------------------------------
    public void insert(char character) {
        Node newNode = new Node();
        newNode.sData = character;
        Node current;
        if (root == null) {
            Node newRootNode = new Node();
            newRootNode.sData = '+';
            root = newRootNode ;
            root.leftChild = newNode;
            
        } else {
            current = root;
            Node parent;

            while (true) {
                parent = current;

                if (character < current.leftChild.sData) {
                    parent = current.leftChild;
                    current = current.leftChild.leftChild; //current was root, now its the left child of root
                        

                    if (current == null) 
                    {
                        Node newChildNode = new Node();
                        newChildNode = parent;  //copy parent before overwriting it 
                        parent.rightChild = newChildNode;  // put the parent into the right child slot
                        current = newNode;
                                 
                        System.out.println(current.sData+""+ parent.sData);
                 
                        return;
                    }
                    
                    
                } else 
                    current = current.rightChild;
                if (current== null)
                {
                    parent.rightChild = newNode;
                    return;
                }
                
            }
        }
    }

// -------------------------------------------------------------
// -------------------------------------------------------------

 public void displayTree() {
        Stack globalStack = new Stack();
        globalStack.push(root);
        int nBlanks = 32;
        boolean isRowEmpty = false;
        System.out.println(
                "......................................................");
        while (isRowEmpty == false) {
            Stack localStack = new Stack();
            isRowEmpty = true;

            for (int j = 0; j < nBlanks; j++) {
                System.out.print(' ');
            }

            while (globalStack.isEmpty() == false) {
                Node temp = (Node) globalStack.pop();
                if (temp != null) {
                    System.out.print(temp.sData);
                    localStack.push(temp.leftChild);
                    localStack.push(temp.rightChild);

                    if (temp.leftChild != null
                            || temp.rightChild != null) {
                        isRowEmpty = false;
                    }
                } else {
                    System.out.print("--");
                    localStack.push(null);
                    localStack.push(null);
                }
                for (int j = 0; j < nBlanks * 2 - 2; j++) {
                    System.out.print(' ');
                }
            }  // end while globalStack not empty
            System.out.println();
            nBlanks /= 2;
            while (localStack.isEmpty() == false) {
                globalStack.push(localStack.pop());
            }
        }  // end while isRowEmpty is false
        System.out.println(
                "......................................................");
    }  // end displayTree()---------------------------------
}  // end class Tree

[Jorge Montes]

you have trouble inserting on the tree.

Recursion will work better for you.

I've made some changes in your code, i didn't understand why you need the '+' char (unnecessary), but i've included anyway. I hope it is not too late.

Please try to understand recursion. It is very useful

    package pkg4333_hwk1;  
      
    import java.io.BufferedReader;  
    import java.io.IOException;  
    import java.io.InputStreamReader;  
    import java.util.Scanner;  
      
      
    /** 
     * 
     * @author preed_000 
     */  
     class Main {  
      
        /** 
         * @param args the command line arguments 
         */  
         public static void main(String[] args) throws IOException {  

//             System.out.println("Please enter a string of letters. No numbers/symbols are allowed.");  
      
             Scanner cin = new Scanner(System.in);  
//             String input = cin.next();  
      
              
               
//             char[] cArray = input.toCharArray(); // split the string into characters  
              
          
          Tree theTree = new Tree();  
//          for (int i = 0; i < input.length(); i++ )  
//              theTree.insert( cArray[i],theTree.root);  
            
//         System.out.println("The characters have been inserted.");  
           
          while(true)  
             {  
             System.out.print("Enter first letter of show, ");  
             System.out.print("insert, find, delete, or traverse: ");  
             int choice = getChar();  
             switch(choice)  
                {  
                case 's':  
                   theTree.displayTree();  
                   break;  
                case 'i':  
                    System.out.println("Type the characters you would like to insert");  
                    String in = cin.next();  
                    char [] cArray1 = in.toCharArray();  
                      
                    //created another character array because there is no telling if   
                    //the first cArray will be large enough to hold the new string  
                    for (int i = 0; i < cArray1.length; i++)  
                    {  
                          
                        theTree.root=theTree.insert(cArray1[i], theTree.root);  
                    }  
                    break;  
                
                 
                default:  
                   System.out.print("Invalid entry\n");  
                }  // end switch  
             }  // end while  
          }  // end main()  
    // -------------------------------------------------------------  
       public static String getString() throws IOException  
          {  
          InputStreamReader isr = new InputStreamReader(System.in);  
          BufferedReader br = new BufferedReader(isr);  
          String s = br.readLine();  
          return s;  
          }  
    // -------------------------------------------------------------  
       public static char getChar() throws IOException  
          {  
          String s = getString();  
          return s.charAt(0);  
          }  
    //-------------------------------------------------------------  
       public static int getInt() throws IOException  
          {  
          String s = getString();  
          return Integer.parseInt(s);  
          }  
    // -------------------------------------------------------------  
       }  // end class TreeApp  

and

    package pkg4333_hwk1;  
      
    import java.io.*;  
    import java.util.*;               // for Stack class  
    ////////////////////////////////////////////////////////////////  
      
    class Node {  
      
        public char sData;              // data item (key)  
        //public double dData;           // data item  
        public Node leftChild;         // this node's left child  
        public Node rightChild;        // this node's right child  
      
        public void displayNode() // display ourself  
        {  
            System.out.print('{');  
            System.out.print(sData);  
            System.out.print(", ");  
            //System.out.print(dData);  
            System.out.print("} ");  
        }  
    }  // end class Node  
    ////////////////////////////////////////////////////////////////  
      
    class Tree {  
      
        public Node root;             // first node of tree  
      
    // -------------------------------------------------------------  
        public Tree() // constructor  
        {  
            root = null;  
        }            // no nodes in tree yet  
    // -------------------------------------------------------------  
      
    // -------------------------------------------------------------  
        public Node insert(char character,Node root) {
        	if(root==null){
        		Node newNode = new Node();  
        		Node newRootNode = new Node();  
                newRootNode.sData = '+';  
                root = newRootNode ;  
                root.leftChild = newNode;  
                root.leftChild.sData = character;
                return root;
        	}else{
        		if(character < root.leftChild.sData){
        			root.leftChild = insert(character,root.leftChild);
        			return root;
        		}else{
        			root.rightChild = insert(character,root.rightChild);
        			return root;
        		}
        	}
        	
        }  
      
    // -------------------------------------------------------------  
    // -------------------------------------------------------------  
      
     public void displayTree() {  
            Stack globalStack = new Stack();  
            globalStack.push(root);  
            int nBlanks = 32;  
            boolean isRowEmpty = false;  
            System.out.println(  
                    "......................................................");  
            while (isRowEmpty == false) {  
                Stack localStack = new Stack();  
                isRowEmpty = true;  
      
                for (int j = 0; j < nBlanks; j++) {  
                    System.out.print(' ');  
                }  
      
                while (globalStack.isEmpty() == false) {  
                    Node temp = (Node) globalStack.pop();  
                    if (temp != null) {  
                        System.out.print(temp.sData);  
                        localStack.push(temp.leftChild);  
                        localStack.push(temp.rightChild);  
      
                        if (temp.leftChild != null  
                                || temp.rightChild != null) {  
                            isRowEmpty = false;  
                        }  
                    } else {  
                        System.out.print("--");  
                        localStack.push(null);  
                        localStack.push(null);  
                    }  
                    for (int j = 0; j < nBlanks * 2 - 2; j++) {  
                        System.out.print(' ');  
                    }  
                }  // end while globalStack not empty  
                System.out.println();  
                nBlanks /= 2;  
                while (localStack.isEmpty() == false) {  
                    globalStack.push(localStack.pop());  
                }  
            }  // end while isRowEmpty is false  
            System.out.println(  
                    "......................................................");  
        }  // end displayTree()---------------------------------  
    }  // end class Tree