Question
Java Binary Tree help Expand on the binary tree example we did in class that reads infix formulas and stores them in a binary tree.
Java Binary Tree help
Expand on the binary tree example we did in class that reads infix formulas and stores them in a binary tree. Create methods for reading postfix and prefix formulas and storing them in the tree.
DO NOT convert prefix/postfix to infix before storing in the tree.
Make the methods as efficient as possible. Include a tester class and make sure the tree is printed in all 3 formats after being populated from any of the three. Include Big-Oh notation for all 3 populate methods, and all 3 print methods.
==============================================================================================
public class EquationBinaryTree {
private Node root;
public EquationBinaryTree()
{
root = null;
}
public String toInfix()
{
return toInfixHelper(root);
}
private String toInfixHelper(Node node)
{
String output = "";
if(node.leftChild != null)
{
output += "(";
output += toInfixHelper(node.leftChild);
output += node;
output += toInfixHelper(node.rightChild);
output += ")";
}
else
output += node;
return output;
}
public String toPostfix()
{
return toPostfixHelper(root);
}
private String toPostfixHelper(Node node)
{
String output = "";
if(node.leftChild != null)
{
output += toPostfixHelper(node.leftChild);
output += toPostfixHelper(node.rightChild);
output += node;
}
else
output += node;
return output;
}
public String toPrefix()
{
return toPrefixHelper(root);
}
private String toPrefixHelper(Node node)
{
String output = "";
if(node.leftChild != null)
{
output += node;
output += toPrefixHelper(node.leftChild);
output += toPrefixHelper(node.rightChild);
}
else
output += node;
return output;
}
//infix ((a-d)+(b*c))
public void populateFromInfix(String infix)
{
root = populateFromInfixHelper(infix);
}
private Node populateFromInfixHelper(String infix)
{
/*
* 0 = left
* 1 = middle
* 2 = right
*/
String[] parts = infixBreakdownHelper(infix);
Node temp = new Node(parts[1].charAt(0));
if(parts[0].length() == 1)
temp.leftChild = new Node(parts[0].charAt(0));
else
temp.leftChild = populateFromInfixHelper(parts[0]);
if(parts[2].length() == 1)
temp.rightChild = new Node(parts[2].charAt(0));
else
temp.rightChild = populateFromInfixHelper(parts[2]);
return temp;
}
private String[] infixBreakdownHelper(String infix)
{
//((a-d)+(b*c))
//[0] = (a-d)
//[1] = +
//[2] = (b*c)
String[] temp = new String[3];
int pos = 0;
int count = 0;
for(int i = 1; i < infix.length(); i++)
{
if(infix.charAt(i) == '(')
count++;
else if(infix.charAt(i) == ')')
count--;
if(count == 0)
{
pos = i;
break;
}
}
/** /
System.out.println("pos:"+pos);
System.out.println("left:"+infix.substring(1, pos+1));
System.out.println("middle:"+infix.charAt(pos+1));
System.out.println("right:"+infix.substring(pos+2, infix.length()-1));
/**/
temp[0] = infix.substring(1, pos+1);//left
temp[1] = ""+infix.charAt(pos+1);//middle
temp[2] = infix.substring(pos+2, infix.length()-1);//right
return temp;
}
/*
* Populate from prefix
*/
public void populateFromPrefix(String pre)
{
}
/*
* Populate from postfix
*/
public void populateFromPostfix(String post)
{
}
private class Node{
public Node leftChild, rightChild;
public char data;
public Node(char data) {
leftChild = null;
rightChild = null;
this.data = data;
}
public String toString()
{
return "" + data;
}
}
}
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
public class EquationBinaryTreeTester {
public static void main(String[] args) {
EquationBinaryTree mathFormula = new EquationBinaryTree();
mathFormula.populateFromInfix("((a+(b*c))+(((d*e)+f)*g))");
System.out.println(mathFormula.toInfix());
System.out.println(mathFormula.toPostfix());
System.out.println(mathFormula.toPrefix());
} }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started