Question: Below are classes to build a binary tree. Please check the code to make sure it is functional and provide some test cases displaying the
Below are classes to build a binary tree. Please check the code to make sure it is functional and provide some test cases displaying the usage of the tree. The code must use the interfaces provided(generics are necessary). The full assignment is to create a binary expression tree which works with an expression that contains only variables or double values and supports operations +, -, *, and /. The expression tree must provide the following additional methods:
1. void setVariable(String name, double value) set the variable name with a value
2. void displayPostfix() output the ET in postfix format in one line, each token is separated by one space. Here is sample usage for the expression tree program.
Sample usage
ExpressionTree expr = new ExpressionTree(new String[]{"a", "b", "2", "/","+"});
expr.setVariable("a", 1.5);
expr.setVariable("b", 2);
System.out.println(expr.evaluate()); expr.displayPostfix();
It would be awesome if you could implement the expression tree, but I only ask that you check the code for building the tree is fit for this purpose.Here is the code I have that needs to be fixed/checked. Again please provide a main with test cases for how to use the tree.
BinaryNode.java
class BinaryNode< T >
{
private T data;
private BinaryNode < T > leftChild;
private BinaryNode < T > rightChild;
public BinaryNode ()
{
this (null); // call next constructor
} // end default constructor
public BinaryNode (T dataPortion)
{
this (dataPortion, null, null); // call next constructor
} // end constructor
public BinaryNode (T dataPortion, BinaryNode < T > newLeftChild,
BinaryNode < T > newRightChild)
{
data = dataPortion;
leftChild = newLeftChild;
rightChild = newRightChild;
} // end constructor
public T getData ()
{
return data;
} // end getData
public void setData (T newData)
{
data = newData;
} // end setData
public BinaryNode< T > getRightChild ()
{
return rightChild;
} // end getRightChild
public void setRightChild (BinaryNode< T > newRightChild)
{
rightChild = newRightChild;
} // end setRightChild
public boolean hasRightChild ()
{
return rightChild != null;
} // end hasRighttChild
public BinaryNode< T > getLeftChild ()
{
return leftChild;
} // end getLeftChild
public void setLeftChild (BinaryNode< T > newLeftChild)
{
leftChild = newLeftChild;
} // end setLeftChild
public boolean hasLeftChild ()
{
return leftChild != null;
} // end hasLeftChild
public boolean isLeaf ()
{
return (leftChild == null) && (rightChild == null);
} // end isLeaf
/*< Implementations of getRightChild, setRightChild, and hasRightChild are
analogous to their left-child counterparts. >
< Implementation of copy appears in Segment 24.6. >*/
public BinaryNode< T > copy ()
{
BinaryNode < T > newRoot = new BinaryNode < > (data);
if (leftChild != null)
newRoot.setLeftChild(leftChild.copy());
if (rightChild != null)
newRoot.setRightChild(rightChild.copy());
return newRoot;
}
private void privateSetTree (T rootData, BinaryTree < T > leftTree,////////////////////////////////////////////////////////////////////
BinaryTree < T > rightTree)
{
BinaryNode
if ((leftTree != null) && !leftTree.isEmpty ())
root.setLeftChild (leftTree.getRootNode().copy ());
if ((rightTree != null) && !rightTree.isEmpty ())
root.setRightChild (rightTree.getRootNode().copy ());
} // end privateSetTree
public int getHeight ()
{
return getHeight (this); // call private getHeight
} // end getHeight
private int getHeight (BinaryNode < T > node)
{
int height = 0;
if (node != null)
height = 1 + Math.max(getHeight(node.getLeftChild()),
getHeight(node.getRightChild()));
return height;
} // end getHeight
public int getNumberOfNodes ()
{
int leftNumber = 0;
int rightNumber = 0;
if (leftChild != null)
leftNumber = leftChild.getNumberOfNodes ();
if (rightChild != null)
rightNumber = rightChild.getNumberOfNodes ();
return 1 + leftNumber + rightNumber;
} // end getNumberOfNodes
} // end BinaryNode
BinaryTree.java
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Stack;
// needed by tree iterators
public class BinaryTree < T > implements BinaryTreeInterface < T >
{
private BinaryNode< T > root;
public BinaryTree ()
{
root = null;
} // end default constructor
public BinaryTree (T rootData)
{
root = new BinaryNode < T > (rootData);
} // end constructor
public BinaryTree (T rootData, BinaryTree < T > leftTree,
BinaryTree < T > rightTree)
{
privateSetTree (rootData, leftTree, rightTree);
} // end constructor
public void setTree (T rootData)
{
root = new BinaryNode < T > (rootData);
} // end setTree
public void setTree (T rootData, BinaryTreeInterface < T > leftTree,
BinaryTreeInterface < T > rightTree)
{
privateSetTree (rootData, (BinaryTree < T > ) leftTree,
(BinaryTree < T > ) rightTree);
} // end setTree
private void privateSetTree (T rootData, BinaryTree < T > leftTree,
BinaryTree < T > rightTree)
{
/* FIRST DRAFT - See Segments 24.5 - 24.8 for improvements. */
root = new BinaryNode < T > (rootData)
;
if (leftTree != null)
root.setLeftChild (leftTree.root);
if (rightTree != null)
root.setRightChild (rightTree.root);
} // end privateSetTree
/*Implementations of getRootData, getHeight, getNumberOfNodes, isEmpty, clear,
and the methods specified in TreeIteratorInterface are here. >
. . .*/
public T getRootData ()
{
T rootData = null;
if (root != null)
rootData = root.getData ();
return rootData;
} // end getRootData
public boolean isEmpty ()
{
return root == null;
} // end isEmpty
public void clear ()
{
root = null;
} // end clear
protected void setRootData (T rootData)
{
root.setData (rootData);
} // end setRootData
protected void setRootNode (BinaryNode < T > rootNode)
{
root = rootNode;
} // end setRootNode
protected BinaryNode< T > getRootNode ()
{
return root;
} // end getRootNode
public int getHeight ()
{
return root.getHeight ();
} // end getHeight
public int getNumberofNodes ()
{
return root.getNumberOfNodes ();
} // end getNumberOfNodes
@Override
public Iterator
return new PreorderIterator();
}
@Override
public Iterator
return new PostorderIterator();
}
@Override
public Iterator
return new InorderIterator();
}
@Override
public Iterator
return new LevelOrderIterator();
}
private class PreorderIterator implements Iterator
private Stack nodeStack;
private BinaryNode
// Define the constructor and assign the value of
//root to the currentNode.
public PreorderIterator()
{
nodeStack = new Stack<>();
currentNode = root;
}
@Override
public boolean hasNext() {
return !nodeStack.isEmpty() || (currentNode != null);
}
@Override
public T next() {
if(!nodeStack.isEmpty())
{
currentNode=null;
}
nodeStack.push(currentNode);
while (!nodeStack.isEmpty())
{
currentNode =
(BinaryNode)nodeStack.peek();
break;
} // end while
return null;
}
}
private class PostorderIterator implements Iterator
private Stack nodeStack;
private BinaryNode
public PostorderIterator(){
// Create an object.
nodeStack = new Stack<>();
// assign the value of root to currentNode.
currentNode = root;
} // end default constructor
public boolean hasNext(){
return !nodeStack.isEmpty() || (currentNode !=
null);
} // end hasNext
public T next(){
// Check the condition using if statement whether
// value of currentNode is equal to null.
if(currentNode== null){
return null;
}
while (true){
// Push root's right child and then root
// to stack.
if (currentNode!=null){
if(currentNode.getRightChild()!=null)
nodeStack.push(
currentNode.getRightChild());
nodeStack.push(currentNode);
currentNode =
currentNode.getLeftChild();
continue;
}
// Check the condition using if
// statement.
if(nodeStack.isEmpty()){
return null;
}
// Set root as root's left child
// Find leftmost node with no left
// child
// Pop an item from stack and set it as
// root
currentNode =(BinaryNode) nodeStack.pop();
// If the popped item has a right child
// and the right child is not
// processed yet, then make sure right
// child is processed before root
// Visit leftmost node, then traverse
// its right subtree
if (currentNode.getRightChild()!=null && ! nodeStack.isEmpty() && currentNode.getRightChild() == nodeStack.peek())
{
nodeStack.pop();
// remove right child from stack
nodeStack.push(currentNode);
// push root back to stack
currentNode =
currentNode.getRightChild();
// change root so that the right
// child is processed next
}
else
{
System.out.print(currentNode.
getData()+" ");
currentNode= null;
}
} // end while
}
}
private class InorderIterator implements Iterator
private Stack nodeStack;
private BinaryNode
public InorderIterator(){
nodeStack = new Stack<>();
currentNode = root;
}
public boolean hasNext(){
return !nodeStack.isEmpty() || (currentNode != null);
}
public T next(){
BinaryNode
while(currentNode != null){
nodeStack.push(currentNode);
currentNode = currentNode.getLeftChild();
}
if(!nodeStack.isEmpty()){
nextNode = (BinaryNode
assert nextNode != null;
currentNode = nextNode.getRightChild();
}
else
throw new NoSuchElementException();
return nextNode.getData();
}
}
private class LevelOrderIterator implements Iterator
private LinkedList nodeQueue;
private BinaryNode currentNode;
public LevelOrderIterator(){
nodeQueue = new LinkedList();
currentNode = root;
} // end default constructor
public boolean hasNext(){
return !nodeQueue.isEmpty() || (currentNode != null);
} // end hasNext
public T next(){
//Check for empty tree
if(currentNode==null){
return null;
}
while (!nodeQueue.isEmpty() || (currentNode != null))
{
// Find leftmost node with no left child
while (currentNode != null){
nodeQueue.push(currentNode);
currentNode =
currentNode.getLeftChild();
} // end while
// Visit leftmost node, then traverse
// its right subtree
if (!nodeQueue.isEmpty()){
BinaryNode
(BinaryNode
assert nextNode != null;
// Since nodeStack was not empty
// before the pop
System.out.print(nextNode.getData() +" ");
currentNode = nextNode.getRightChild();
} // end if
} // end while
return null;
}
}
} // end BinaryTree
BinaryTreeInterface.java
public interface BinaryTreeInterface
public void setTree(T rootData);
public void setTree(T rootData, BinaryTreeInterface
}
TreeInterface.java
public interface TreeInterface
public T getRootData();
public int getHeight();
public int getNumberofNodes();
public boolean isEmpty();
public void clear();
}
TreeIteratorInterface.java
import java.util.Iterator;
public interface TreeIteratorInterface
public Iterator
public Iterator
public Iterator
public Iterator
}
GeneralNode.java (I'm not sure if this is a needed class given that we have BinaryNode, but I'm providing it)
(Also, do not make BinaryNode extend this interface)
import java.util.Iterator; interface GeneralNodeInterface < T > { public T getData (); public void setData (T newData); public boolean isLeaf (); public Iterator < T > getChildrenIterator (); public void addChild (GeneralNodeInterface < T > newChild); } // end GeneralNodeInterface
Here is the code I began for implementing the extression tree if you can help with this.
ExpressionTreeInterface.java
public interface ExpressionTreeInterface extends BinaryTreeInterface < String > { /** Computes the value of the expression in this tree. @return the value of the expression */ public double evaluate (); } // end ExpressionTreeInterface
ExpressionTree.java
import java.util.Stack;
public class ExpressionTree extends BinaryTree
implements ExpressionTreeInterface
{
// Call the ExpressionTree
public ExpressionTree()
{} // end default constructor
private double getValueOf(String variable)
{
// Strings allow multicharacter variables
double result = 0;
return result;
} // end getValueOf
private double compute(String operator, double
firstOperand, double secondOperand)
{
// Set the value of result with 0.
double result = 0;
return result;
}
public void createExpressionTree(String postfix)
{
// Create the object.
Stack nodeStack = new Stack<>();
// Create the object of BinaryTree.
BinaryTreeInterface chtree = new
BinaryTree<>();
// Create the object of BinaryTree.
BinaryTreeInterface ltree = new
BinaryTree<>();
// Create the object of BinaryTree.
BinaryTreeInterface rtree = new
BinaryTree<>();
// Iterate for loop till value of i is less
// than postfix.length()
for (int i = 0; i < postfix.length(); i++)
{
// Get the vcharacter at the specific
// position.
char ch = postfix.charAt(i);
// Check the condition using if statement.
if (getValueOf(ch)==1||getValueOf(ch)==2
||getValueOf(ch)==3||getValueOf(ch)==4)
{
BinaryNode rightNode = (BinaryNode)
nodeStack.pop();
BinaryNode leftNode = (BinaryNode)
nodeStack.pop();
rtree.setTree(rightNode.toString());
ltree.setTree(leftNode.toString());
// Check the condition using if statement.
if (getValueOf(ch)==1)
chtree.setTree("+", ltree, rtree);
// Check the condition using if statement.
if (getValueOf(ch)==2)
chtree.setTree("-", ltree, rtree);
// Check the condition using if statement.
if (getValueOf(ch)==3)
chtree.setTree("*", ltree, rtree);
// Check the condition using if statement.
if (getValueOf(ch)==4)
chtree.setTree("/", ltree, rtree);
nodeStack.push(new BinaryNode(ch,
rightNode, leftNode));
System.out.println("Root is"+chtree.getRootData()+" "+ "Right node is"+ rightNode.getData()+ " Left node is "+ leftNode.getData());
}
else
{
nodeStack.push(new BinaryNode(ch, null,
null));
}
}
setRootNode((BinaryNode) nodeStack.pop());
}
private int getValueOf(char c)
{
if(c == '+')
{
return 1;
}
if(c == '-')
{
return 2;
}
if(c == '*')
{
return 3;
}
if(c == '/')
{
return 4;
}
else
return 0;
}
@Override
public double evaluate()
{
throw new UnsupportedOperationException("Not supported yet.");
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help