package interfaces; import java.util.List; public interface TreeTraversals<E> {
ID: 668372 • Letter: P
Question
package interfaces;
import java.util.List;
public interface TreeTraversals<E> {
/**
*
*
* 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 {
/**
*
*
* 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
}
-------------------------------------------------------------------------------------------------------------------------------
package interfaces;
import java.util.List;
public interface Tree<E> {
public int size();
public boolean isEmpty();
public Position<E> root();
public Position<E> parent(Position<E> position);
public List<Position<E>> children(Position<E> position);
public int numChildren(Position<E> position);
// some additional methods (not specified in the original tree ADT)
// which provide some ways to modify the tree
public void setRoot(Position<E> root);
public void insert(Position<E> parent, Position<E> child);
public void remove(Position<E> position);
}
----------------------------------------------------------------------------------------------------------------------
package interfaces;
import java.util.List;
public interface Position<E> {
public E getElement();
public void setElement(E element);
public Position<E> getParent();
public void setParent(Position<E> parent);
public List<Position<E>> getChildren();
public void addChild(Position<E> child);
public void removeChild(Position<E> child);
}
---------------------------------------------------------------------------------------------------------------------
import java.util.List;
import interfaces.Tree;
import interfaces.TreeArithmetic;
import interfaces.TreeProperties;
import interfaces.TreeTraversals;
import simpletree.SimpleTree;
/**
*
* This class, MyTree, should be your solution to the assignment
* It should remain in the (default package)
*
* Implement as many of the required methods as you can.
*/
public class MyTreeUnimplemented<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;
}
}
Explanation / Answer
import static org.junit.Assert.assertEquals;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import org.junit.Test;
public class BST
{
public TreeNode root = null;
public TreeNode get(int element)
{
if(root == null)
{
return null;
}
TreeNode runner = root;
while (true)
{
if(runner.data > element)
{
if(runner.leftNode == null)
{
return null;
}
runner = runner.leftNode;
}
else if(runner.data < element)
{
if(runner.rightNode == null)
{
return null;
}
runner = runner.rightNode;
}
else
{
return runner;
}
}
}
public void insert(int element)
{
if(root == null)
{
root = new TreeNode(element);
return;
}
TreeNode runner = root;
while (runner.data != element)
{
if(runner.data > element)
{
if(runner.leftNode == null)
{
runner.leftNode = new TreeNode(element);
return;
}
runner = runner.leftNode;
}
else
{
if(runner.rightNode == null)
{
runner.rightNode = new TreeNode(element);
return;
}
runner = runner.rightNode;
}
}
}
public static void breathFirstSearch(TreeNode root)
{
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
TreeNode runner = root;
while(!queue.isEmpty())
{
runner = (TreeNode)queue.remove();
if(runner.leftNode != null)
{
queue.add(runner.leftNode);
}
if(runner.rightNode != null)
{
queue.add(runner.rightNode);
}
System.out.println("visited node " + runner.data);
}
}
public static void depthFirstSearch(TreeNode root)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root == null)
{
return;
}
TreeNode runner = null;
stack.add(root);
while(!stack.empty())
{
runner = stack.peek();
if(runner.leftNode != null && !runner.leftNode.visited)
{
stack.add(runner.leftNode);
continue;
}
if(runner.rightNode != null && !runner.rightNode.visited)
{
stack.add(runner.rightNode);
continue;
}
stack.pop();
runner.visited = true;
System.out.println("visited node " + runner.data);
}
}
public static void preOrderTraversal(TreeNode root)
{
if(root == null)
{
return;
}
System.out.print(root.data + " ");
preOrderTraversal(root.leftNode);
preOrderTraversal(root.rightNode);
}
public static void inOrderTraversal(TreeNode root)
{
if(root == null)
{
return ;
}
inOrderTraversal(root.leftNode);
System.out.print(root.data + " ");
inOrderTraversal(root.rightNode);
}
private class TreeNode
{
public int data;
public TreeNode leftNode;
public TreeNode rightNode;
public boolean visited;
TreeNode(int data)
{
this.data = data;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.