P1 Suppose we want to create a method for the class BinaryTree (file BinaryTree.
ID: 3716299 • Letter: P
Question
P1
Suppose we want to create a method for the class BinaryTree (file BinaryTree.java) that counts the number of times an object occurs in the tree.
Write the method
public int count1(T anObject)
which calls the private recursive method
private int count1(BinaryNode<T> rootNode, T anObject)
to count the number of occurrences of anObject
Write the method
public int count2(T anObject)
that counts the number of occurrences of anObject and that uses one of the iterators of the binary tree.
Compare the efficiencies of the previous the two methods count1 and count2 using big O notation. Add your answer as a comment before the function definition
----------------------------------------------------------------------------------------------------------------
P2
Suppose we want to create a method for the class BinaryTree that decides whether two trees have the same structure. Two trees t1 and t2 have the same structure if:
If one has a left child, then both have left children and the left children are isomorphic, AND
if one has a right child, then both have right children and the right children are isomorphic
The header of the method is:
public boolean isIsomorphic(BinaryTree<T> otherTree)
Write this method, using a private recursive method of the same name.
----------------------------------------------------------------------------------------------------------------
P3
Design an algorithm that produces a binary expression tree from a given infix expression. You can assume that the infix expression is a string that has only the binary operators +, -, *, / and one-letter operands. Implement the solution as a construction in ExpressionTree that takes a string argument:
public ExpressionTree(String infix)
that calls the private method
private ExpressionTreeInterface formTree(String expr, int first, int last)
to construct the tree. formTree() builds the tree recursively.
----------------------------------------------------------------------------------------------------------------
//package TreePackage;
class BinaryNode<T>
{
private T data;
private BinaryNode<T> left;
private BinaryNode<T> right;
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> leftChild,
BinaryNode<T> rightChild)
{
data = dataPortion;
left = leftChild;
right = rightChild;
} // end constructor
public T getData()
{
return data;
} // end getData
public void setData(T newData)
{
data = newData;
} // end setData
public BinaryNode<T> getLeftChild()
{
return left;
} // end getLeftChild
public void setLeftChild(BinaryNode<T> leftChild)
{
left = leftChild;
} // end setLeftChild
public boolean hasLeftChild()
{
return left != null;
} // end hasLeftChild
public boolean isLeaf()
{
return (left == null) && (right == null);
} // end isLeaf
public BinaryNode<T> getRightChild()
{
return right;
} // end getLeftChild
public void setRightChild(BinaryNode<T> rightChild)
{
right = rightChild;
} // end setLeftChild
public boolean hasRightChild()
{
return right != null;
} // end
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.left),
getHeight(node.right));
return height;
} // end getHeight
public int getNumberOfNodes()
{
int leftNumber = 0;
int rightNumber = 0;
if (left != null)
leftNumber = left.getNumberOfNodes();
if (right != null)
rightNumber = right.getNumberOfNodes();
return 1 + leftNumber + rightNumber;
} // end getNumberOfNodes
public BinaryNode<T> copy()
{
BinaryNode<T> newRoot = new BinaryNode<T>(data);
if (left != null)
newRoot.left = left.copy();
if (right != null)
newRoot.right = right.copy();
return newRoot;
} // end copy
} // end BinaryNode
----------------------------------------------------------------------------------------------------------------
//package TreePackage;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack ; // for Stack
public class BinaryTree<T>
{
protected 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, BinaryTree<T> leftTree,
BinaryTree<T> rightTree)
{
privateSetTree(rootData, leftTree, rightTree);
} // end setTree
private void privateSetTree(T rootData, BinaryTree<T> leftTree,
BinaryTree<T> rightTree)
{
root = new BinaryNode<T>(rootData);
if (leftTree != null)
root.setLeftChild(leftTree.root);
if (rightTree != null)
root.setRightChild(rightTree.root);
}
public T getRootData () {
T rootData = null;
if (root != null)
rootData = root.getData();
return rootData;
}
public boolean isEmpty () {
return root == null;
}
public void clear (){
root = null;
}
// getHeight and getNumberOfNodes call same functions in BinaryNode<T>
public int getHeight () {
return root.getHeight ();
}
public int getNumberOfNodes () {
return root.getNumberOfNodes ();
}
public void inorderTraversal() {
Stack<BinaryNode<T>> nodeStack = new Stack<BinaryNode<T>>();
BinaryNode<T> currentNode = root;
while (!nodeStack.empty() || currentNode != null) {
while(currentNode != null) {
nodeStack.push(currentNode);
currentNode = currentNode.getLeftChild();
}
if(!nodeStack.empty()) {
BinaryNode<T> nextNode = nodeStack.pop();
System.out.println(nextNode.getData());
currentNode = nextNode.getRightChild();
}
}
}
public Iterator<T> getPreorderIterator() {
return new PreorderIterator();
}
public Iterator<T> getInorderIterator() {
return new InorderIterator();
}
private class PreorderIterator implements Iterator<T> {
private Stack<BinaryNode<T>> nodeStack;
public PreorderIterator() {
nodeStack = new Stack<BinaryNode<T>>();
if (root != null)
nodeStack.push(root);
} // end default constructor
public boolean hasNext() {
return !nodeStack.isEmpty();
} // end hasNext
public T next() {
BinaryNode<T> nextNode;
if (hasNext()) {
}
public void clear (){
root = null;
}
// getHeight and getNumberOfNodes call same functions in BinaryNode<T>
public int getHeight () {
return root.getHeight ();
}
public int getNumberOfNodes () {
return root.getNumberOfNodes ();
}
public void inorderTraversal() {
Stack<BinaryNode<T>> nodeStack = new Stack<BinaryNode<T>>();
BinaryNode<T> currentNode = root;
while (!nodeStack.empty() || currentNode != null) {
while(currentNode != null) {
nodeStack.push(currentNode);
currentNode = currentNode.getLeftChild();
}
if(!nodeStack.empty()) {
BinaryNode<T> nextNode = nodeStack.pop();
System.out.println(nextNode.getData());
currentNode = nextNode.getRightChild();
}
}
}
public Iterator<T> getPreorderIterator() {
return new PreorderIterator();
}
public Iterator<T> getInorderIterator() {
return new InorderIterator();
}
private class PreorderIterator implements Iterator<T> {
private Stack<BinaryNode<T>> nodeStack;
public PreorderIterator() {
nodeStack = new Stack<BinaryNode<T>>();
if (root != null)
nodeStack.push(root);
} // end default constructor
public boolean hasNext() {
return !nodeStack.isEmpty();
} // end hasNext
public T next() {
BinaryNode<T> nextNode;
if (hasNext()) {
nextNode = nodeStack.pop();
BinaryNode<T> leftChild = nextNode.getLeftChild();
BinaryNode<T> rightChild = nextNode.getRightChild();
// push into stack in reverse order of recursive calls
if (rightChild != null)
nodeStack.push(rightChild);
if (leftChild != null)
nodeStack.push(leftChild);
}
else {
throw new NoSuchElementException();
}
return nextNode.getData();
} // end next
public void remove() {
throw new UnsupportedOperationException();
} // end remove
} // end PreorderIterator
private class InorderIterator implements Iterator < T >
{
private Stack< BinaryNode < T >> nodeStack;
private BinaryNode< T > currentNode;
public InorderIterator () {
nodeStack = new Stack < BinaryNode< T >> ();
currentNode = root;
} // end default constructor
public boolean hasNext () {
return !nodeStack.isEmpty () || (currentNode != null);
} // end hasNext
public T next ()
{
BinaryNode< T > nextNode = null;
// find leftmost node with no left child
while (currentNode != null) {
nodeStack.push (currentNode);
currentNode = currentNode.getLeftChild ();
} // end while
// get leftmost node, then move to its right subtree
if (!nodeStack.isEmpty ()) {
nextNode = nodeStack.pop ();
currentNode = nextNode.getRightChild ();
}
else
throw new NoSuchElementException ();
return nextNode.getData ();
} // end next
public void remove () {
throw new UnsupportedOperationException ();
} // end remove
} // end InorderIterator
} // end BinaryTree
----------------------------------------------------------------------------------------------------------------
import java.util.Iterator;
class Driver {
public static void iteratorTraversal() {
// Build the tree
// Leaves: d, e, g
BinaryTree<String> dTree = new BinaryTree<String>("d");
BinaryTree<String> eTree = new BinaryTree<String>("e");
BinaryTree<String> gTree = new BinaryTree<String>("g");
BinaryTree<String> bTree = new BinaryTree<String>("b",
dTree, eTree);
BinaryTree<String> fTree = new BinaryTree<String>("f",
null, gTree);
BinaryTree<String> cTree = new BinaryTree<String>("c",
fTree, null);
BinaryTree<String> aTree = new BinaryTree<String>("a",
bTree, cTree);
System.out.println("Inorder traversal of tree rooted at A
using Iterator");
Iterator<String> iter = aTree.getInorderIterator();
while(iter.hasNext()) {
String s = iter.next();
// Process s if needed
System.out.println("String: " + s);
}
System.out.println("Preorder traversal of tree rooted at
A using Iterator");
Iterator<String> iter2 = aTree.getPreorderIterator();
while(iter2.hasNext()) {
String s = iter2.next();
// Process s if needed
System.out.println("String: " + s);
}
}
public static void expressionTree() {
ExpressionTree aTree = new ExpressionTree("a");
ExpressionTree bTree = new ExpressionTree("b");
ExpressionTree cTree = new ExpressionTree("c");
ExpressionTree timesTree = new ExpressionTree();
timesTree.setTree("*",aTree, bTree);
ExpressionTree plusTree = new ExpressionTree();
plusTree.setTree("+", timesTree, cTree);
System.out.println(" (a*b) + c = " +
plusTree.evaluate());
}
import java.util.Iterator;
class Driver {
public static void iteratorTraversal() {
// Build the tree
// Leaves: d, e, g
BinaryTree<String> dTree = new BinaryTree<String>("d");
BinaryTree<String> eTree = new BinaryTree<String>("e");
BinaryTree<String> gTree = new BinaryTree<String>("g");
BinaryTree<String> bTree = new BinaryTree<String>("b",
dTree, eTree);
BinaryTree<String> fTree = new BinaryTree<String>("f",
null, gTree);
BinaryTree<String> cTree = new BinaryTree<String>("c",
fTree, null);
BinaryTree<String> aTree = new BinaryTree<String>("a",
bTree, cTree);
System.out.println("Inorder traversal of tree rooted at A
using Iterator");
Iterator<String> iter = aTree.getInorderIterator();
while(iter.hasNext()) {
String s = iter.next();
// Process s if needed
System.out.println("String: " + s);
}
System.out.println("Preorder traversal of tree rooted at
A using Iterator");
Iterator<String> iter2 = aTree.getPreorderIterator();
while(iter2.hasNext()) {
String s = iter2.next();
// Process s if needed
System.out.println("String: " + s);
}
}
public static void expressionTree() {
ExpressionTree aTree = new ExpressionTree("a");
ExpressionTree bTree = new ExpressionTree("b");
ExpressionTree cTree = new ExpressionTree("c");
ExpressionTree timesTree = new ExpressionTree();
timesTree.setTree("*",aTree, bTree);
ExpressionTree plusTree = new ExpressionTree();
plusTree.setTree("+", timesTree, cTree);
System.out.println(" (a*b) + c = " +
plusTree.evaluate());
}
public static void main(String [] args) {
// D, F, G and H are leaves
BinaryTree<String> dTree = new BinaryTree<String>("D");
BinaryTree<String> fTree = new BinaryTree<String>();
fTree.setTree("F");
BinaryTree<String> gTree = new BinaryTree<String>("G");
BinaryTree<String> hTree = new BinaryTree<String>("H");
BinaryTree<String> eTree = new BinaryTree<String>();
// E has F and G as left and right children
eTree.setTree("E", fTree, gTree);
// B has D and E as children
BinaryTree<String> bTree = new BinaryTree<String>("B",
dTree, eTree);
// C has H as right child
BinaryTreeInterface<String> cTree = new
BinaryTree<String>("C", null, hTree);
// A has B and C as children
BinaryTreeInterface<String> aTree = new
BinaryTree<String>();
aTree.setTree("A", bTree, cTree);
// display root, height, number of nodes
System.out.println("Tree rooted at A:");
System.out.println("Root of tree contains " +
aTree.getRootData());
System.out.println("Height of tree is " +
aTree.getHeight());
System.out.println("Tree has " + aTree.getNumberOfNodes()
+ " nodes");
System.out.println();
// display root, height, number of nodes
System.out.println("Tree rooted at B:");
System.out.println("Root of tree contains " +
bTree.getRootData());
System.out.println("Height of tree is " +
bTree.getHeight());
System.out.println("Tree has " + bTree.getNumberOfNodes()
+ " nodes");
// Inorder traversal of tree rooted at A
System.out.println("Inorder traversal of tree rooted at
A");
aTree.inorderTraversal();
iteratorTraversal();
expressionTree();
}
}
----------------------------------------------------------------------------------------------------------------
public class ExpressionTree extends BinaryTree<String> {
public ExpressionTree() {
} // end default constructor
public ExpressionTree(String data) {
super(data);
} // end default constructor
public double evaluate() {
return evaluate(root);
} // end evaluate
private double evaluate(BinaryNode<String> rootNode) {
double result;
if (rootNode == null)
result = 0;
else if (rootNode.isLeaf()) {
String variable = rootNode.getData();
result = getValueOf(variable);
}
else {
double firstOperand =
evaluate(rootNode.getLeftChild());
double secondOperand =
evaluate(rootNode.getRightChild());
String operator = rootNode.getData();
result = compute(operator, firstOperand,
secondOperand);
} // end if
return result;
} // end evaluate
private double getValueOf(String variable) { // strings allow
multicharacter variables
double result = 0;
if (variable.equals("a"))
result = 1;
else if (variable.equals("b"))
result = 2;
else if (variable.equals("c"))
result = 3;
else if (variable.equals("d"))
result = 4;
else if (variable.equals("e"))
result = 5;
return result;
} // end getValueOf
private double compute(String operator, double firstOperand, double
secondOperand)
{
double result = 0;
if (operator.equals("+"))
result = firstOperand + secondOperand;
else if (operator.equals("-"))
result = firstOperand - secondOperand;
else if (operator.equals("*"))
result = firstOperand * secondOperand;
else if (operator.equals("/"))
result = firstOperand / secondOperand;
return result;
} // end compute
} // end ExpressionTree
----------------------------------------------------------------------------------------------------------------
Explanation / Answer
ANS:-
PROGRAM:-
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.