Start with the tree.java program (Listing 8.1) and modify it to create a binary
ID: 3670971 • Letter: S
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:
Here's my main method: (Main method cannot be edited or modified)
/* You need to write classes Node, Tree, BottomUp, and BottomUpApp with main method */
public static void main(String[] args) throws IOException
{
BottomUp bup;
Tree theTree = null;
int value;
String str;
while(true)
{
System.out.print("Enter first letter of balanced, ");
System.out.print("unbalanced, show, or traverse: ");
int choice = getChar();
switch(choice)
{
case 'b':
System.out.print("Enter string: ");
str = getString();
bup = new BottomUp(str);
bup.balanced();
theTree = bup.getTree();
break;
case 'u':
System.out.print("Enter string: ");
str = getString();
bup = new BottomUp(str);
bup.unbalanced();
theTree = bup.getTree();
break;
case 's':
theTree.displayTree();
break;
case 't':
System.out.print("Enter type 1, 2 or 3: ");
value = getInt();
theTree.traverse(value);
break;
default:
System.out.print("Invalid entry ");
} // end switch
} // end while
} // end main()
Here's my code so far:
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
I need BottomUp and BottomUpApp classes to go with the main method! PLEASE HELP ME!!! I BEG YOU!! FIX MY CODE THAT I DESPERATELY NEED HELP WITH!!
Explanation / Answer
import java.io.* ;
import java.util.* ;
class Node
{
public char ch ;
public Node leftChild ;
public Node rightChild ;
Node ( char c )
{
ch =c ;
}
public void displayNode ()
{
System.out.print ( ch ) ;
}
}
class Tree
{
public Node root ;
public Tree ( Node nd )
{
root =nd ;
}
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 )
{
localRoot.displayNode () ;
preOrder ( localRoot.leftChild ) ;
preOrder ( localRoot.rightChild ) ;
}
}
private void inOrder ( Node localRoot )
{
if ( localRoot !=null )
{
inOrder ( localRoot.leftChild ) ;
localRoot.displayNode () ;
inOrder ( localRoot.rightChild ) ;
}
}
private void postOrder ( Node localRoot )
{
if ( localRoot !=null )
{
postOrder ( localRoot.leftChild ) ;
postOrder ( localRoot.rightChild ) ;
localRoot.displayNode () ;
}
}
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 )
{
temp.displayNode () ;
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 - 1 ; j++ )
System.out.print ( ' ' ) ;
}
System.out.println () ;
nBlanks / = 2 ;
while ( localStack.isEmpty () == false )
globalStack.push (localStack.pop () ) ;
}
System.out.println ( " ...................................................... " ) ;
}
}
class BottomUp
{
private String inString ;
private int strlen ;
private Tree[] treeArray ;
private Tree aTree ;
private int numNodes ;
BottomUp ( String s )
{
inString= s ;
strlen= inString.length () ;
treeArray= new Tree[100] ;
for ( int j = 0 ; j < strlen ; j++ )
{
char ch= inString.charAt ( j ) ;
Node aNode= new Node ( ch ) ;
treeArray[j]= new Tree ( aNode ) ;
}
}
public Tree getTree ()
{
return aTree ;
}
public void balanced ()
{
numNodes= strlen ;
while( numNodes > 1 )
{
int i= 0 ;
int j= 0 ;
Tree[] tempArray= new Tree[100] ;
for ( j = 0 ; j < strlen - 1 ; j++ )
{
Tree tree1= treeArray[j] ;
Tree tree2= treeArray[j+1] ;
Node aNode= new Node ( '+' ) ;
aTree= new Tree ( aNode ) ;
aTree.root.leftChild= tree1.root ;
aTree.root.rightChild= tree2.root ;
tempArray[i++]= aTree ;
numNodes-- ;
j++ ;
}
if ( strlen % 2 == 1 )
{
Tree tree1= treeArray[j] ;
Node aNode= new Node ( '+' ) ;
aTree= new Tree ( aNode ) ;
aTree.root.leftChild= tree1.root ;
tempArray[i++]= aTree ;
}
treeArray= tempArray ;
strlen= numNodes ;
}
aTree= treeArray[0] ;
}
}
class BottomUpApp
{
public static void main ( String[] args ) throws IOException
{
BottomUp bup ;
Tree theTree= null ;
int value ;
String str ;
while ( true )
{
System.out.print ( " Enter first letter of " ) ;
System.out.print ( " balanced , show , or traverse : " ) ;
int choice=getChar() ;
switch ( choice )
{
case 'b' :
System.out.print ( " Enter string : " ) ;
str =getString () ;
bup =new BottomUp ( str ) ;
bup.balanced () ;
theTree =bup.getTree () ;
break ;
case 's' :
theTree.displayTree () ;
break ;
case 't' :
System.out.print ( " Enter type 1, 2 or 3 : " ) ;
value =getInt() ;
theTree.traverse ( value ) ;
break ;
default:
System.out.print ( " Invalid entry " ) ;
}
}
}
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 ) ;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.