Data Structure Java Binary Tree Help

BinaryTreeFormula 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());

} }