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.

Explanation / Answer

// Tree Class

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

// Main Class

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 ");
} // 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

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.