BinaryTreeExpression { ExpressionNode root = new ExpressionNode("XXX"); // it will simply hold the tree int nodes = 0, parents = 0; // counter int height = -1; public BinaryTreeExpression()
Im missing parts, as in getting method to throw InvalidSyntaxExpression and I dont think its printing in order it should! See image for full assignment details. Help :'-(
BinaryTreeExpression.java
public class BinaryTreeExpression {
ExpressionNode root = new ExpressionNode("XXX"); // it will simply hold the tree
int nodes = 0, parents = 0; // counter
int height = -1;
public BinaryTreeExpression() {
root.pflag = true;
}
void makeTree() {
// makeTree tree
ExpressionNode node = root;
StringBuilder t = new StringBuilder(); // expression node value
int s = "(A(C(k)(2))(n(24)))".length();
// assumed first last will open and closed brackets
for(int i = 1; i < s - 1; i++) {
char x = "(A(C(k)(2))(n(24)))".charAt(i);
if(x == '(' || x == ')') {
String val = t.toString();
if(t.length() > 0) {
if(!node.pflag) {
// not marked yet
node.pflag = true;
parents++;
}
if(node.left == null) {
// left first
node.left = new ExpressionNode(val);
node.left.parent = node;
node = node.left;
} else {
// then right
node.right = new ExpressionNode(val);
node.right.parent = node;
node = node.right;
}
nodes++;
}
height++; // move downward
if(x == ')') {
// back to immediate parent
node = node.parent;
height--; // move back
}
t = new StringBuilder(); // reset
} else {
// node value
t.append(x);
}
}
}
int size() {
return nodes;
}
int totalParents() {
return parents;
}
int totalLeaves() {
return nodes - parents;
}
int getHeight() {
return height;
}
// recursive approach
int height(ExpressionNode node) {
if(node == null) {
// base case
return 0;
}
return 1 + Math.max(height(node.left), height(node.right));
}
boolean balanced(ExpressionNode node) {
if(node == null) {
// base case
return true;
}
boolean ok = balanced(node.left) && balanced(node.right);
int h1 = height(node.left);
int h2 = height(node.right);
return ok && (Math.abs(h1 - h2) <= 1);
}
boolean isBalanced() {
return balanced(root.left); // root.left is our original root node
}
boolean full(ExpressionNode node) {
if(node.pflag) {
// if it's leaf then return true, otherwise
if(node.left == null || node.right == null) {
// it's not full
return false;
}
// recursive call
return full(node.left) && full(node.right);
} else {
// leaf
return true;
}
}
boolean isFull() {
// root.left is our original root node
return full(root.left);
}
void inorder(ExpressionNode node) {
if(node == null) {
return;
}
inorder(node.left);
System.out.print(node.node + " ");
inorder(node.right);
}
void recursiveInorder() {
System.out.print("[");
inorder(root.left);
System.out.println("]");
}
// driver program to test
public static void main(String[] args) {
BinaryTreeExpression tree = new BinaryTreeExpression();
// try with some other test case like (A(C(K)(2))(N(24(10(12(13))))))
tree.makeTree();
System.out.println("Size: " + tree.size());
System.out.println("Height: " + tree.getHeight());
System.out.println("Parents: " + tree.totalParents());
System.out.println("Leaves: " + tree.totalLeaves());
System.out.println("Balanced: " + tree.isBalanced());
System.out.println("Full:" + tree.isFull());
System.out.println("In-Order: ");
tree.recursiveInorder();
}
}
ExpressionNode.java
class ExpressionNode {
String node;
ExpressionNode left, right;
ExpressionNode parent;
boolean pflag = false;
public ExpressionNode(String node) {
this.node = node;
left = right = null;
}
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
