please implement these interfaces in the bottom part where it says public class!
ID: 668380 • Letter: P
Question
please implement these interfaces in the bottom part where it says public class!
package interfaces;
import java.util.List;
public interface TreeTraversals<E> {
/**
* PART 1
*
* Implement the following methods, which output some useful traversals
* of the trees. In all cases, the children of a node should be visited
* in the same order in which they appear in the underlying data structure
* (do not consider the value contained in the node when deciding the order.)
*/
public List<E> preOrder();
// Output the values of a pre-order traversal of the tree
public List<E> postOrder();
// Output the values of a post-order traversal of the tree
public List<E> inOrder();
// Output the values of a in-order traversal of the tree
// This operation should only be performed if the tree is a proper binary tree.
// If it is not, then throw an UnsupportedOperationException instead of returning a value
// Otherwise, perform the traversal with child 0 on the left, and child 1 on the right.
}
-------------------------------------------------------------------------------------------------------------------
package interfaces;
public interface TreeProperties {
/**
* PART 2
*
* Implement the following methods, which test or output certain properties
* that the tree might have.
*/
public int height();
// calculate the height of the tree (the maximum depth of any position in the tree.)
// a tree with only one position has height 0.
// a tree where the root has children, but no grandchildren has height 1.
// a tree where the root has grandchildren, but no great-grandchildren has height 2.
// we will define an empty tree to have height -1.
public int height(int maxDepth);
// calculate the height of the tree, but do not descend deeper than 'depth' edges into the tree
// do not visit any nodes deeper than maxDepth while calculating this
// do not call your height() method
// (some trees are very, very, very big!)
public int numLeaves();
// calculate the number of leaves of the tree (positions with no children)
public int numLeaves(int depth);
// calculate the number of leaves of the tree at exactly depth depth.
// the root is at depth 0. The children of the root are at depth 1.
public int numPositions(int depth);
// calculate the number of positions at exactly depth depth.
public boolean isBinary();
// is the tree a binary tree?
// every position in a binary tree has no more than 2 children
public boolean isProperBinary();
// is the tree a proper binary tree?
// every position in a proper binary tree has either zero or two children
public boolean isCompleteBinary();
// is the tree a complete binary tree?
// 1) all the levels except the last must be full
// 2) all leaves in the last level are filled from left to right (no gaps)
public boolean isBalancedBinary();
// is the tree a balanced binary tree?
// a balanced tree is one where for every position in the tree, the
// subtrees rooted at each of the children of the that position have
// heights that differ by no more than one.
// NOTE: if a node has only one child, the other child is considered to be a subtree of height -1
public boolean isHeap(boolean min);
// is the tree a min-heap (if min is True), or is the tree a max-heap (if min is False)
// heaps are trees which are both complete and have the heap property:
// in a min-heap, the value of a node is less than or equal to the value of each of its children
// similarly, in a max-heap the value of a node is greater than or equal to the value of each child
public boolean isBinarySearchTree();
// is the tree a binary search tree?
// a binary search tree is a binary tree such that for any node with value v:
// - if there is a left child (child 0 is not null), it contains a value strictly less than v.
// - if there is a right child (child 1 is not null), it contains a value strictly greater than v.
// if there is only one child, you may assume that it is a left child.
}
-----------------------------------------------------------------------------------------------------------
package interfaces;
public interface TreeArithmetic {
/**
* PART 4
*
* Implement an Arithmetic Expression display and evaluator.
*
* For all methods except isArithmetic, you may assume that the input is
* valid arithmetic
*/
public boolean isArithmetic();
// is this tree a valid arithmetic tree
// every leaf in an arithmetic tree is a numeric value, for example: "1", "2.5", or "-0.234"
// every internal node is a binary operation: "+", "-", "*", "/"
// binary operations must act on exactly two sub-expressions (i.e. two children)
// note: all the values and operations are stored as String objects
public double evaluateArithmetic();
// evaluate an arithmetic tree to get the solution
// if a position is a numeric value, then it has that value
// if a position is a binary operation, then apply that operation on the value of its children
// use floating point maths for all calculations, not integer maths
// if a position contains "/", its left subtree evaluated to 1.0, and the right to 2.0, then it is 0.5
public String getArithmeticString();
// Output a String showing the expression in normal (infix) mathematical notation
// For example: "(1+2)+3"
// You must put brackets around every binary expression
// You may omit the brackets from the outermost binary expression
}
-----------------------------------------------------------------------------------------------
import java.util.List;
import interfaces.Tree;
import interfaces.TreeArithmetic;
import interfaces.TreeProperties;
import interfaces.TreeTraversals;
import simpletree.SimpleTree;
/**
*
*
* It should remain in the (default package)
*
* Implement as many of the required methods as you can.
*/
public class MyTree<E extends Comparable<E>> extends SimpleTree<E> implements
TreeTraversals<E>, //PART 1
TreeProperties, //PART 2
Comparable<Tree<E>>, //PART 3 (only if enrolled in INFO1105)
TreeArithmetic //PART 4
{
//constructor
public MyTree() {
super(); //call the constructor of SimpleTree with no arguments
}
@Override
public int compareTo(Tree<E> other) {
//TODO: implement this method if enrolled in INFO1105
// compare the tree with another tree
// check the structure and values of the trees:
// check the positions left-to-right, top to bottom (i.e. root, then depth 1, then depth 2, etc.)
// - If this tree has a position that the other tree does not, return 1.
// - If the other tree has a position that this one does not, return -1.
// - If the position is in both trees, then compare the values (if they are different, return the difference)
// If the two trees are identical, return 0
return 0;
}
@Override
public boolean isArithmetic() {
// TODO Auto-generated method stub
return false;
}
@Override
public double evaluateArithmetic() {
// TODO Auto-generated method stub
return 0;
}
@Override
public String getArithmeticString() {
// TODO Auto-generated method stub
return null;
}
@Override
public int height() {
// TODO Auto-generated method stub
return 0;
}
@Override
public int height(int maxDepth) {
// TODO Auto-generated method stub
return 0;
}
@Override
public int numLeaves() {
// TODO Auto-generated method stub
return 0;
}
@Override
public int numLeaves(int depth) {
// TODO Auto-generated method stub
return 0;
}
@Override
public int numPositions(int depth) {
// TODO Auto-generated method stub
return 0;
}
@Override
public boolean isBinary() {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean isProperBinary() {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean isCompleteBinary() {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean isBalancedBinary() {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean isHeap(boolean min) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean isBinarySearchTree() {
// TODO Auto-generated method stub
return false;
}
@Override
public List<E> preOrder() {
// TODO Auto-generated method stub
return null;
}
@Override
public List<E> postOrder() {
// TODO Auto-generated method stub
return null;
}
@Override
public List<E> inOrder() {
// TODO Auto-generated method stub
return null;
}
}
Explanation / Answer
import interfaces.TreeArithmetic;
import interfaces.TreeProperties;
import interfaces.TreeTraversals;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import simpletree.Node;
public class MyTree<E extends Comparable<E>> implements TreeArithmetic<E>,
TreeProperties<E>, TreeTraversals<E> {
private Node root;
// constructor
public MyTree(Node root) {
super(); // call the constructor of SimpleTree with no arguments
this.root = root;
}
@Override
public boolean isArithmetic() {
// TODO Auto-generated method stub
return false;
}
@Override
public double evaluateArithmetic() {
// TODO Auto-generated method stub
return 0;
}
@Override
public String getArithmeticString() {
// TODO Auto-generated method stub
return null;
}
@Override
public int height() {
return 0;
}
@Override
public int height(int maxDepth) {
// TODO Auto-generated method stub
return 0;
}
@Override
public int numLeaves() {
// TODO Auto-generated method stub
return 0;
}
@Override
public int numLeaves(int depth) {
// TODO Auto-generated method stub
return 0;
}
@Override
public int numPositions(int depth) {
// TODO Auto-generated method stub
return 0;
}
@Override
public boolean isBinary() {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean isProperBinary() {
return false;
}
@Override
public boolean isCompleteBinary() {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean isBalancedBinary() {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean isHeap(boolean min) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean isBinarySearchTree() {
// TODO Auto-generated method stub
return false;
}
@Override
public List<E> preOrder() {
List<E> preOrderList = new ArrayList<>();
if (isProperBinary()) {
LinkedList<Node> stack = new LinkedList<Node>();
stack.push(root);
while (!stack.isEmpty()) {
Node temp = stack.pop();
preOrderList.add((E) temp);
if (temp.getRightNode() != null)
stack.push(temp.getRightNode());
if (temp.getLeftNode() != null)
stack.push(temp.getLeftNode());
}
} else {
throw new UnsupportedOperationException(
"The tree is not a proper tree");
}
return preOrderList;
}
@Override
public List<E> postOrder() {
List<E> postOrder = new ArrayList<>();
LinkedList<Node> stack = new LinkedList<Node>();
while (true) {
if (root != null) {
stack.push(root);
root = root.getLeftNode();
} else {
if (stack.isEmpty()) {
return postOrder;
} else if (stack.peek().getRightNode() == null) {
root = stack.pop();
postOrder.add((E) root);
if (root == stack.peek().getRightNode()) {
postOrder.add((E) root);
root = stack.pop();
if (!stack.isEmpty() && root == stack.peek().getRightNode())
postOrder.add((E) root);
}
}
if (!stack.isEmpty()) {
root = stack.peek().getRightNode();
} else {
root = null;
}
}
}
}
@Override
public List<E> inOrder() {
List<E> inOrderList = new ArrayList<>();
if (isProperBinary()) {
LinkedList<Node> stack = new LinkedList<Node>();
Node temp = root;
while (temp != null || !stack.isEmpty()) {
if (temp != null) {
stack.push(temp);
temp = temp.getLeftNode();
} else {
inOrderList.add((E) stack.pop());
temp = temp.getRightNode();
}
}
} else {
throw new UnsupportedOperationException(
"The tree is not a proper tree");
}
return inOrderList;
}
}
---------------------------------------------------------------------------------------------------------------------------------------------------------
I have implementd in order, preorder, post order traversals.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.