Question

Need help in the below question. Answer in java

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:
+
+ E
+ D - -
+ C - - - - - -
A B - - - - - - - - - - - - - -

Expand the program in Programming Project 8.1 to create a balanced tree. One
way to do this is to make sure that as many leaves as possible appear in the
bottom row. You can start by making a three-node tree out of each pair of onenode
trees, making a new + node for the root. This results in a forest of threenode
trees. Then combine each pair of three-node trees to make a forest of
seven-node trees. As the number of nodes per tree grows, the number of trees
shrinks, until finally there is only one tree left.

Here is the example tree.java program to use below.>>>>>>>

// tree.java
// demonstrates binary tree
// to run this program: C>java TreeApp
import java.io.*;
import java.util.*; // for Stack class
////////////////////////////////////////////////////////////////
class Node
{
public int iData; // 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(iData);
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 Node find(int key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while(current.iData != key) // while no match,
{
if(key < current.iData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if(current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
// -------------------------------------------------------------
public void insert(int id, double dd)
{
Node newNode = new Node(); // make new node
newNode.iData = id; // insert data
newNode.dData = dd;
if(root==null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node parent;
while(true) // (exits internally)
{
parent = current;
if(id < current.iData) // go left?
{
current = current.leftChild;
if(current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if(current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
public boolean delete(int key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;

while(current.iData != key) // search for node
{
parent = current;
if(key < current.iData) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete

// if no children, simply delete it
if(current.leftChild==null &&
current.rightChild==null)
{
if(current == root) // if root,
root = null; // tree is empty
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}

// if no right child, replace with left subtree
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;

// if no left child, replace with right subtree
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;

else // two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);

// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;

// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
// -------------------------------------------------------------
public void traverse(int traverseType)
{
switch(traverseType)
{
case 1: System.out.print("\nPreorder traversal: ");
preOrder(root);
break;
case 2: System.out.print("\nInorder traversal: ");
inOrder(root);
break;
case 3: System.out.print("\nPostorder 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);
}
}
// -------------------------------------------------------------
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<nBlanks; j++)
System.out.print(' ');

while(globalStack.isEmpty()==false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
System.out.print(temp.iData);
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
////////////////////////////////////////////////////////////////
class TreeApp
{
public static void main(String[] args) throws IOException
{
int value;
Tree theTree = new Tree();

theTree.insert(50, 1.5);
theTree.insert(25, 1.2);
theTree.insert(75, 1.7);
theTree.insert(12, 1.5);
theTree.insert(37, 1.2);
theTree.insert(43, 1.7);
theTree.insert(30, 1.5);
theTree.insert(33, 1.2);
theTree.insert(87, 1.7);
theTree.insert(93, 1.5);
theTree.insert(97, 1.5);

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.print("Enter value to insert: ");
value = getInt();
theTree.insert(value, value + 0.9);
break;
case 'f':
System.out.print("Enter value to find: ");
value = getInt();
Node found = theTree.find(value);
if(found != null)
{
System.out.print("Found: ");
found.displayNode();
System.out.print("\n");
}
else
System.out.print("Could not find ");
System.out.print(value + '\n');
break;
case 'd':
System.out.print("Enter value to delete: ");
value = getInt();
boolean didDelete = theTree.delete(value);
if(didDelete)
System.out.print("Deleted " + value + '\n');
else
System.out.print("Could not delete ");
System.out.print(value + '\n');
break;
case 't':
System.out.print("Enter type 1, 2 or 3: ");
value = getInt();
theTree.traverse(value);
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
////////////////////////////////////////////////////////////////

Answer 1

`Hey,

Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries

// import required packages

import java.io.*;

import java.util.*;

//Class for tree node

class BTFSLNode

{

     // variables declaration

     public String strData;           

     public BTFSLNode ltChild;

     public BTFSLNode rtChild;

    

     // Method to print the tree node

     public void displayNode()

     {

          System.out.print("{" + strData + "}");

     }

}

// class for the binary tree

class BTFSLTree

{

     // root node of the tree

     private BTFSLNode BTFSLroot;         

     // constructor of the class

     public BTFSLTree(String intlString)

     {

          BTFSLroot = null;

         

//code to Parse the input string as array of single-letter nodes

BTFSLNode[] arrayNode = new BTFSLNode[intlString.length()];

          for(int li = 0; li < intlString.length(); li++)

          {

              arrayNode[li] = new BTFSLNode();

arrayNode[li].strData = String.valueOf(intlString.charAt(li));

          }

         

//Code to include "+" nodes and its children iteratively

          BTFSLNode plsNode = new BTFSLNode();

          plsNode.strData = "+";

          plsNode.ltChild = arrayNode[0];

          plsNode.rtChild = arrayNode[1];

         

          for(int lj = 2; lj < arrayNode.length; lj++)

          {

              BTFSLNode nwNode = new BTFSLNode();

              nwNode.strData = "+";

              nwNode.ltChild = plsNode;

              nwNode.rtChild = arrayNode[lj];

              plsNode = nwNode;

          }

          BTFSLroot = plsNode;

     }

    

     // method to perform the tree traversal

     public void traverse(int trvrsType)

     {

          switch(trvrsType)

          {

          case 1: System.out.print("\nPreorder traversal: ");

                   preOrder(BTFSLroot);

                   break;

          case 2: System.out.print("\nInorder traversal: ");

                   inOrder(BTFSLroot);

                   break;

          case 3: System.out.print("\nPostorder traversal: ");

                   postOrder(BTFSLroot);

                   break;

          }

          System.out.println("");

     }

    

     // method to perform the preOrder traversal

     private void preOrder(BTFSLNode lclRoot)

     {

          if(lclRoot != null)

          {

              System.out.print(lclRoot.strData + " ");

              preOrder(lclRoot.ltChild);

              preOrder(lclRoot.rtChild);

          }

     }

    

     // method to perform the inOrder traversal

     private void inOrder(BTFSLNode lclRoot)

     {

          if(lclRoot != null)

          {

              inOrder(lclRoot.ltChild);

              System.out.print(lclRoot.strData + " ");

              inOrder(lclRoot.rtChild);

          }

     }

    

     // method to perform the postOrder traversal

     private void postOrder(BTFSLNode lclRoot)

     {

          if(lclRoot != null)

          {

              postOrder(lclRoot.ltChild);

              postOrder(lclRoot.rtChild);

              System.out.print(lclRoot.strData + " ");

          }

     }

    

     // method to display tree nodes

     public void displayTree()

     {

          Stack<BTFSLNode> glblStack = new Stack<BTFSLNode>();

          glblStack.push(BTFSLroot);

          int nmBlnks = 32;

          boolean isRwempty = false;

System.out.println(".......................................................");

          while(isRwempty==false)

          {

Stack<BTFSLNode> lclStack = new Stack<BTFSLNode>();

              isRwempty = true;

             

              for(int lj = 0; lj < nmBlnks; lj++)

                   System.out.print(" ");

             

              while(glblStack.isEmpty() == false)

              {

                   BTFSLNode tmp = glblStack.pop();

                   if(tmp != null)

                   {

                        System.out.print(tmp.strData);

                        lclStack.push(tmp.ltChild);

                        lclStack.push(tmp.rtChild);

                       

                        if(tmp.ltChild != null ||

                                  tmp.rtChild != null)

                             isRwempty = false;

                   }

                   else

                   {

                        System.out.print("--");

                        lclStack.push(null);

                        lclStack.push(null);

                   }

                   for(int lj = 0; lj < nmBlnks*2 - 2; lj++)

                        System.out.print(" ");

              }

              System.out.println();

              nmBlnks /= 2;

              while(lclStack.isEmpty() == false)

                   glblStack.push( lclStack.pop() );

          }

System.out.println(".......................................................");

     }

}

// class to perform the test of binary tree

class BTFSL

{

     // main method

     public static void main(String[] args) throws IOException

     {

          int vlu;

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

          String intlString = getStringval();

          BTFSLTree btslTree = new BTFSLTree(intlString);

         

          while(true)

          {

System.out.print("Enter first letter of (s)how, (t)raverse or (e)xit: ");

              int usrchc = getCharval();

              switch(usrchc)

              {

              case 's':

                   btslTree.displayTree();

                   break;

              case 't':

System.out.print("Enter type 1-Preorder, 2-Inorder, or 3-Postorder: ");

                   vlu = getIntval();

                   btslTree.traverse(vlu);

                   break;

              case 'e':

                   System.exit(0);

                   break;

              default:

                   System.out.print("Invalid entry!\n");

              }

          }

     }

     // method to read user input

     public static String getStringval() throws IOException

     {

InputStreamReader instr = new InputStreamReader(System.in);

          BufferedReader burdr = new BufferedReader(instr);

          String lclStrng = burdr.readLine();

          return lclStrng;

     }

    

     // method to get first character from user input

     public static char getCharval() throws IOException

     {

          String lclStrng = getStringval();

          return lclStrng.charAt(0);

     }

    

     //method to get the integer values form user input

     public static int getIntval() throws IOException

     {

          String lclStrng = getStringval();

          return Integer.parseInt(lclStrng);

     }

}

plsNode.rt Child arrayNode [1] = 2; lj < arrayNode.length; lj++) for (int lj = new BTFSLNode (); BTFSLNode nwNode nwNode. strData = nwNode.ltChild plsNode; arrayNode [1jl nwNode.rtChild nwNode plsNode BTFSLroot plsNode; = } /method to perform the tree traversal public void traverse (int trvrsType) switch (trvrsType) f case 1: System.out.print ("\nPreorder traversal: "); preorder (BTFSLroot); break case 2: System.out.print ("\nInorder traversal: "); inorder (BTFSLroot) break case 3: System.out.print ("\nPostorder traversal: "): postorder (BT FSLroot); break System.out.println (""); } /method to perform the preOrder traversal private void preorder (BTFSLNode lclRoot) if (lclRoot ! null) System.out. print (lclRoot. strData + preorder (1lclRoot.ltChild); preOrder (lc1 Root.rtChild) " "); /method to perform the inorder traversal private void inorder (BTFSLNode 1clRoot) { if (lclRoot != null )

inorder (lc1Root.ltChild); System.out.print (lclRoot.strData inorder (lcl Root.rtchild) ") } /method to perform the postorder traversal private void postorder (BTFSLNode lclRoot) { if (lclRoot != null) postorder (lclRoot.ltchild) postorder (lclRoot.rtChild) System.out.print (lclRoot.strData + ") } /method to display tree nodes public void displayTree ( { new Stack<BTFSLNode> () Stack<BTFSLNode> glblStack glblstack.push (BTFSLroot); int nmBlnks boolean is Rwempty System.out.println (" 32 false; ") while (isRwempty== false) Stack<BTFSLNode lclStack Stack<BTFSLNode> () isRwempty new = true 0 ljnmBlnks; lj++) for (int lj System.out.print (" ") ; while (glblStack.isEmpty () false) glblstack.pop ) BTFSLNode tmp if (tmp ! null) System.out.print (tmp. strData) lclstack.push (tmp.ltChild); lclstack.push (tmp.rtChild); if (tmp.ltChild !null || tmp.rtChild null) isRwempty false;

} else System.out.print ("--"); lclstack.push (null) lclstack.push (null); } 2; lj++ for (int lj 0 1j nmBlnks*2 System.out.print (" "); System.out.println () ; nmBlnks 2; while (lclsStack.isEmpty () glblstack.push lclstack.pop false) == System.out.println (" "); } /class to perform the test of binary tree class BTFSL { main method public static void main (String [ args) throws IOException { int vlu System.out.print ("Enter user String intlstring string:") getStringval () new BTFSLTree (intlString); BTFSLTree btslTree while (true) { System.out.print ("Enter first letter of (s)how (t) raverse or (e)xit: "); int usrchc switch (usrchc) getCharval ) s' case btslTree.displayTree (); break case 't': System.out.print ("Enter type 1-Preorder, 2- Inorder, or 3-Postorder: "); getIntval ); btslTree.traverse (vlu) vlu = break

e': case System.exit (0) break; default: System.out.print ("Invalid entry!\n") } /method to read user input public static String getStringval ( throws IOException InputStreamReader instr InputStreamReader (System.in) new new BufferedReader (instr) BufferedReader burdr burdr.readLine () String lclStrng return lclStrng; /method to get first character from user public static char getCharval ) throws IOException input getStringval () String lclStrng return lclstrng.charAt (0) - } input //method to get the integer values form user public static int getIntval ( throws IOException getStringval () String lclstrng return Integer.parseInt (lclStrng) - Result: D: \Java\bin>javac BTFSL.java D: Java\bin>java BTFSL string:ABCDE FGH Enter user (e)xit: s Enter first letter of (s) how, (t) raverse or H F T

Kindly revert for any queries

Thanks.