Start with the tree.java program (Listing 8.1) and modify it to create a binary

Question

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:

One way to begin is by making an array of trees. (A group of unconnected trees is called a forest.) Take each letter typed by the user and put it in a node. Take each of these nodes and put it in a tree, where it will be the root. Now put all these one-node trees in the array. Start by making a new tree with + at the root and two of the one-node trees as its children. Then keep adding one-node trees from the array to this larger tree. Don’t worry if it’s an unbalanced tree. You can actually store this intermediate tree in the array by writing over a cell whose contents have already been added to the tree. The routines find(), insert(), and delete(), which apply only to search trees, can be deleted. Keep the displayTree() method and the traversals because they will work on any binary tree.

Here's my code:

  case 'u':

               System.out.print("Enter string: ");

               str = getString();

               bup = new BottomUp(str);

               bup.unbalanced();

               theTree = bup.getTree();

               break;

The program should run like this: The output may look like:

Enter first letter of balanced, unbalanced, show, or traverse: u

Enter string: Dolly

Enter first letter of balanced, unbalanced, show, or traverse: s

Enter first letter of balanced, unbalanced, show, or traverse: t

Enter type 1, 2 or 3: 1

Preorder traversal: ++++Dolly

Enter first letter of balanced, unbalanced, show, or traverse: t

Enter type 1, 2 or 3: 2

Inorder traversal: D+o+l+l+y

Enter first letter of balanced, unbalanced, show, or traverse: t

Enter type 1, 2 or 3: 3

Postorder traversal: Do+l+l+y+

Enter first letter of balanced, unbalanced, show, or traverse: b

Enter string: Dolly

Enter first letter of balanced, unbalanced, show, or traverse: s

Please help me, I need help making the program run like above with the tree above. Please any help is appreciated!!! Most of the code is correct, I just need an unbalanced code for my case 'u'. PLEASE HELP ME I BEG!!

Explanation / Answer

import java.io.*; import java.util.*; class Node { public String iData; // data item (key) 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(iData); System.out.print("} "); } } // end class Node class Tree { private Node root; // first node of tree public void setNode(Node newNode) {root = newNode;} public Node getNode() {return root;} // ------------------------------------------------------------- public Tree() // constructor { root = null; } // no nodes in tree yet // ------------------------------------------------------------- public void traverse(int traverseType) { switch(traverseType) { case 1: System.out.print(" Preorder traversal: "); preOrder(root); break; case 2: System.out.print(" Inorder traversal: "); inOrder(root); break; case 3: System.out.print(" Postorder traversal: "); postOrder(root); break; } System.out.println(); } private void preOrder(Node localRoot) { if(localRoot != null) { System.out.print(localRoot.iData + " "); preOrder(localRoot.leftChild); preOrder(localRoot.rightChild); } } //A function I made to try and get the letters into leaves. void preOrderLeaves(Node localRoot, Tree[] forest, int i) { if(localRoot != null) { localRoot.iData = "+"; localRoot.leftChild.iData = "+"; localRoot.rightChild = forest[i].getNode(); preOrderLeaves(localRoot.leftChild, forest, i + 1); preOrderLeaves(localRoot.rightChild, forest, i + 1); } } // ------------------------------------------------------------- private void inOrder(Node localRoot) { if(localRoot != null) { inOrder(localRoot.leftChild); System.out.print(localRoot.iData + " "); inOrder(localRoot.rightChild); } } // ------------------------------------------------------------- private void postOrder(Node localRoot) { if(localRoot != null) { postOrder(localRoot.leftChild); postOrder(localRoot.rightChild); System.out.print(localRoot.iData + " "); } } // ------------------------------------------------------------- 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

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---