Part 3 implement the following method, which allows us to compare trees: public
ID: 668496 • Letter: P
Question
Part 3 implement the following method, which allows us to compare trees:
public int compareTo(Tree<E> other) // compare the tree with another tree //
check the structure and values of the trees: // check the positions lefttoright, 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
Here is the outline for :-
import java.util.List;
import interfaces.Tree;
import interfaces.TreeArithmetic;
import interfaces.TreeProperties;
import interfaces.TreeTraversals;
import simpletree.SimpleTree;
public class MyTree<E extends Comparable<E>> extends SimpleTree<E> implements
TreeTraversals<E>,
TreeProperties,
Comparable<Tree<E>>,
TreeArithmetic
{
//constructor
public MyTree() {
super(); //call the constructor of SimpleTree with no arguments
}
}
}
Explanation / Answer
BalanceBST.java
//package interfaces;
public interface BalancedBST<E> {
public boolean add(E value);
// if value is already in the balanced BST, do nothing and return false
// otherwise, add value to the balanced binary search tree (BST) and return true
// use the algorithm shown in the week 6 lecture - the BST must remain balanced
public boolean remove(E value);
// if value is in the balanced BST, remove it and return true
// otherwise, do nothing and return false
// implement the algorithm shown in the week 6 lecture to ensure that the BST remains balanced
}
MyTree.java
import java.util.ArrayList;
import java.util.List;
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)
//BalancedBST<E>, //PART 3 (only if enrolled in INFO1905)
TreeArithmetic
//PART 4
{
//constructor
public MyTree() {
super(); //call the constructor of SimpleTree with no arguments
}
//ANDREW SECTION BELOW
public List<E> preOrder() {
return preOrder(this.root());
}
/*Used in preOrder
* Computes the preOrder of the subtree with this root
*/
//TODO null pointer exception for empty trees
private List<E> preOrder(Position<E> currentPosition) {
ArrayList<E> tempList = new ArrayList<E>();//Create a list to store the elements
//Add the current element (before checking children)
tempList.add(currentPosition.getElement());
//Loop through the children and add them to the list
for (Position<E> tempPos : currentPosition.getChildren()){ //Uses the properties of iterators to loop
tempList.addAll(preOrder(tempPos)); //add all the elements that are in the child tree.
}
//Return the list now that all the subtrees have been explored
return tempList;
}
public List<E> postOrder() {
return postOrder(this.root());
}
private List<E> postOrder(Position<E> currentPosition) {
ArrayList<E> tempList = new ArrayList<E>();//Create a list to store the elements
//Loop through the children and add them to the list
//If there are no elements in the children then it will skip the loop.
for (Position<E> tempPos : currentPosition.getChildren()){
tempList.addAll(postOrder(tempPos)); //add all the elements that are in the child tree.
}
//Add the current element (before adding children)
tempList.add(currentPosition.getElement());
//Return the list now that all the subtrees have been explored
return tempList;
}
public List<E> inOrder() {
return inOrder(this.root());
}
private List<E> inOrder(Position<E> currentPosition) {
List<Position<E>> currentChildren=currentPosition.getChildren();
ArrayList<E> tempList = new ArrayList<E>();//Create a list to store the elements
int childSize=currentChildren.size();
if (childSize==0){
tempList.add(currentPosition.getElement());
return tempList;
} else if (childSize!=2){
throw new UnsupportedOperationException();
}
//There are 2 children so we add the left and right subtrees.
tempList.addAll(inOrder(currentChildren.get(0)));
tempList.add(currentPosition.getElement());
tempList.addAll(inOrder(currentChildren.get(1)));
return tempList;
}
//JEMMA SECTION BELOW
//@Override
public int height() {
if (this.root() == null){
return -1; //empty tree = -1
}
System.out.printf("height of this tree: %d ", height(this.root()));
return height(this.root())-1; //actually its is defined as what you would think it is -1
}
//used for height
private int height(Position<E> p){
//if its a leaf its height is 1
if (numChildren(p) == 0){
return 1;
}
//if its not a leaf find its deepest child
int max = 0;
List<Position<E>>children = children(p);
for(Position<E> child : children){
int h = height(child);
if (h > max){
max = h;
}
}
return max+1;
}
//used for height(max depth)
private int height(Position<E> p, int deepest){
//if its a leaf its height is 1
if (numChildren(p) == 0){
return 1;
}
//if its not a leaf find its deepest child
int max = 0;
List<Position<E>>children = children(p);
for(Position<E> child : children){
int h = height(child);
if (h >= max){
max = h;
}
if (h==deepest){
return deepest;
}
}
return max+1;
}
//@Override
public int height(int deepest) {
if (this.root() == null){
return -1; //empty tree = -1
}
return height(this.root(), deepest)-1;
}
//get the number of leaves in the tree
//@Override
public int numLeaves() {
if (this.root() == null){
return 0;
}
else{
return numLeaves(this.root());
}
}
//used for numLeaves
private int numLeaves(Position<E> p) {
int temp=numChildren(p);
if (numChildren(p)==0){
return 1;
}
List<Position<E>> children = p.getChildren();
int total = 0;
for (Position<E> c : children){
total += numLeaves(c);
}
return total;
}
//get the depth of a node
private int depth(Position<E> p){
if (p == null){
return -1; //above root? is depth -1?
}
int depth = 0; //if it is the root depth 0
while (p != this.root()){
p = p.getParent();
depth++;
}
return depth;
}
//get the leaves at certain depth that are rooted at said position
//used in numLeaves(depth)
private int leavesRooted(Position<E> p, int depth){
if (numChildren(p)==0 && depth(p) == depth){ //when its a leaf at the right depth
return 1;
}
else if (depth(p)==depth){//when its not a leaf at the right depth
return 0;
}
else if (depth(p)<depth){ //when its still above the right depth
//only get children if at less than depth
int count = 0;
List<Position<E>> children = this.root().getChildren();
//add the number of leaves at depth rooted at each of its children to the total
for (Position<E> c : children){
count += leavesRooted(c, depth);
}
return count; //return the total number of leaves at depth rooted at p
}
else{
return 0; //a leaf above depth
}
}
//get the number of leaves at exactly depth
//root has depth 0
@Override
public int numLeaves(int depth) {
if (this.root() == null){
return 0; //no leaves if there's no root!
}
else {
return leavesRooted(this.root(), depth);
}
}
//get the leaves at certain depth that are rooted at said position
//used in numLeaves(depth)
private int positionsRooted(Position<E> p, int depth){
if (depth(p)==depth){//when it is at the right depth
return 1;
}
else if (depth(p)<depth){ //when its still above the right depth
int count = 0; //1 position if only this position
List<Position<E>> children = this.root().getChildren();
//add the number of positions at depth rooted at each of its children to the total
for (Position<E> c : children){
count += leavesRooted(c, depth);
}
return count; //return the total number of positions at depth rooted at p.
}
else{
return 0; //ends above depth
}
}
//@Override
public int numPositions(int depth) {
if (this.root() == null){
return 0; //no positions if theres no root
}
else {
return positionsRooted(this.root(), depth);//positionsRooted calls recursively
}
}
//used in isBinary
private boolean subtreeBinary(Position<E> p){
if (numChildren(p)>2){
return false;
}
else {
//get a list of its children
List<Position<E>> children = p.getChildren();
for (Position<E> c : children){
if (!subtreeBinary(c)){ //check whether each child is the root of a binaryTree
return false; //if its not return false imediately
}
}
return true; //otherwise keep going
}
}
//@Override
public boolean isBinary() {
if (this.root() == null){
return true;
}
else {
return subtreeBinary(this.root());
}
}
//used in isProperBinary
private boolean subtreeProperBinary(Position<E> p){
if (numChildren(p)==1 || numChildren(p)>2){
return false;
}
else {
//get a list of its children
List<Position<E>> children = p.getChildren();
for (Position<E> c : children){
if (!subtreeBinary(c)){ //check whether each child is the root of a ProperBinaryTree
return false; //if its not return false imediately
}
}
return true; //otherwise keep going
}
}
//@Override
public boolean isProperBinary() {
if (this.root() == null){
return true; //if the tree is empty its proper
}
else {
return subtreeProperBinary(this.root());
}
}
//@Override
public boolean isComplete() {
// TODO Auto-generated method stub
return false;
}
/*
//used in isComplete
private boolean isCompleteSub(Position<E> root, int index, int totalPositions){
if (root == null){ //if its empty its complete
return true;
}
//incomplete if index>totalPositions http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/
if (index >= totalPositions){
return false;
}
//otherwise check subtrees
boolean left = isCompleteSub(root.left(), 2*index+1, totalPositions);
boolean right = isCompleteSub(root.right(), 2*index+2, totalPositions);
return (left && right);
}
//used in isComplete
private int allPositions(Position<E> p){
if (this.root() == null){
return 0;
}
if (numChildren(p) == 0){
return 1;
}
//make a list of all the children and count how many positions in that subtree
List<Position<E>> children = p.getChildren();
int count = 1; //count starts at 1 for the position p
for (Position<E> c : children){
count += allPositions(c);
}
return count;
}
//@Override
public boolean isComplete() {
if (!isBinary()){
return false;
}
else {
return isCompleteSub(this.root(), 1, allPositions(this.root()));
}
}
*/
private boolean isBalancedRooted(Position<E> p, int maxHeight){
if (p == null){
return true;
}
if (numChildren(p)==0){
//if its a leaf at the right height return true
if (height(p) == maxHeight || height(p)==maxHeight-1){
return true;
}
else { //if its a leaf at the wrong height return false
return false;
}
}
else { //if its not a leaf
//ensure that all the subtrees rooted as its children are balanced
List<Position<E>> children = p.getChildren();
for (Position<E> child : children){
if (!isBalancedRooted(child, maxHeight)){
return false; //if any of the subtrees have an unbalanced leaf return false
}
}
return true; //if they are return true
}
}
//@Override
public boolean isBalanced() {
//depth of the tree is depth of the deepest leaf
//TODO unless this is out by one!?
if (this.root() == null){
return true;
}
int maxHeight = height()+1; //because just a root height = 0
//go through each position and make sure leaves at height or height-1
return isBalancedRooted(this.root(), maxHeight);
}
//used in isHeap()
private boolean isSubHeap(Position<E> p, boolean min){
if (this.root() == null){
return true;
}
if (p.getParent() == null){
//do nothing
}
else if (min){ //min heap
if (!(p.getElement().compareTo(p.getParent().getElement())<0)){ //not p<parent
return false; //false if current element is greater or equal to parent
}
}
else { //max heap
if (!(p.getElement().compareTo(p.getParent().getElement())>0)){//not p>parent
return false; //false if current element is less or equal to parent
}
}
//if it gets to here current position and all above it in the tree satisfy heap
//check all its children satisfy heap conditions
List<Position<E>> children = p.getChildren();
for (Position<E> child : children){
if (!isSubHeap(child, min)){
return false; //false if any of its children are false
}
}
return true; //only true if all its children are true
}
//@Override
public boolean isHeap(boolean min) {
if (!isComplete()){
return false; //must be complete
}
return isSubHeap(this.root(), min);
}
/*
//used in isBinarySearchTree
private boolean subBinarySearch(Position<E> p){
if (p == null){
return true; //true for an empty tree
}
if (p.getParent() == null){
return true; //true for the root
}
boolean leftGood;
boolean rightGood;
//check the left element is < parent
if (p.left.getElement().compareTo(p) < 0){
leftGood = true;
}
else {
leftGood = false;
}
//check the right element is > parent
if (p.right.getElement().compareTo(p)>0){
rightGood = true;
}
else {
rightGood = false;
}
if (leftGood && rightGood){
return false; //this current position fails, return false
}
//otherwise check all the children
List<Position<E>> children = p.getChildren();
for (Position<E> child : children){
if (!subBinarySearch(child)){
return false;
}
}
return true; //only gets here if all children are true;
}
//@Override
public boolean isBinarySearchTree() {
if (!isBinary()){
return false; ///must be binary
}
return subBinarySearch(this.root());
}
*/
//@Override
public boolean isBinarySearchTree() {
// TODO Auto-generated method stub
return false;
}
//@Override
public boolean isArithmetic() {
if (this.root()==null){
return false;
} else if (!this.isProperBinary()){
return false;
} else {
return isArithmeticPos(this.root());
}
}
public boolean isArithmeticPos(Position<E> currentPosition) {
/*
* If this has 2 children;
* check that it is a valid operator
* check the children are valid
*
* If there are no children;
* check that the current position contains a valid number
*/
List<Position<E>> currentChildren=currentPosition.getChildren();
String currentStr=(String) currentPosition.getElement();
if (currentChildren.size()==0){
try { //Try catch block from http://stackoverflow.com/questions/1102891/how-to-check-if-a-string-is-a-numeric-type-in-java
//@SuppressWarnings("unused")
double d = Double.parseDouble(currentStr);
} catch(NumberFormatException nfe){
//The leafs string does not contain a number so the tree is not arithmetic
return false;
}
//The number is valid, so we can return true
return true;
} else {
//The currentPosition has 2 children
//currentStrhecurrentStrk currentStrurrentStr is an operator
if (currentStr.length()!=1){
return false;
}
Character c = currentStr.charAt(0);
if(c == '+' || c == '-' || c == '/' || c == '*') {
boolean tree1=isArithmeticPos(currentChildren.get(0));
boolean tree2=isArithmeticPos(currentChildren.get(1));
return tree1&&tree2;
}
return false;
}
}
//@Override
public double evaluateArithmetic() {
// Valid operators +-*/
/* Start at the top
* if just a number
* return the number
* else
* return the operation on the evaluate of the children
*
*/
if (!isArithmetic()){
return 0;
}
return evaluatePosition(this.root());
}
public double evaluatePosition(Position<E> currentPosition) {
//Store the children
List<Position<E>> currentChildren=currentPosition.getChildren();
int childSize=currentChildren.size();
String currentStr=(String) currentPosition.getElement();
if (childSize==0){ //This is a leaf
return Double.parseDouble(currentStr);
}
double firstNum=evaluatePosition(currentChildren.get(0));
double secondNum=evaluatePosition(currentChildren.get(1));
Character c=currentStr.charAt(0);
if(c == '+'){
return firstNum+secondNum;
} else if (c == '-'){
return firstNum-secondNum;
} else if (c == '*'){
return firstNum*secondNum;
} else if (c == '/'){
return firstNum/secondNum;
}
return 0;
}
public String getArithmeticString() {
if (this.isArithmetic()){
return inOrderString(this.root());
} else {
return "";
}
}
private String inOrderString(Position<E> currentPosition) {
//Store the children
List<Position<E>> currentChildren=currentPosition.getChildren();
int childSize=currentChildren.size();
if (childSize==0){ //This is a leaf
return (String) currentPosition.getElement();
} else if (childSize!=2){ //This is not a valid arithmetic tree
throw new UnsupportedOperationException();
}
String storageString="("; //Create a string to store the elements
//There are 2 children so we add the left and right subtrees.
storageString+=inOrderString(currentChildren.get(0));
storageString+=(String) currentPosition.getElement(); //Operator
storageString+=inOrderString(currentChildren.get(1));
storageString+=")";
return storageString;
}
}
Position.java
//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);
}
SimpleTree.java
//package simpletree;
import java.util.List;
public class SimpleTree<E> implements Tree<E> {
private Position<E> root;
//constructor
public SimpleTree() {
this.root = null;
}
//returns the number of positions in the tree
//@Override
public int size() {
//handle edge case: empty tree
if(root == null) {
return 0;
}
//otherwise return the size of the subtree rooted at the root
return size(root);
}
//return the size of the subtree rooted at position
public int size(Position<E> position) {
//keep a running total of the size, initially 1 (for the position itself)
int size = 1;
//for each child, recursively calculate its size and add it to the total
for(Position<E> child : position.getChildren()) {
size += size(child);
}
return size;
}
//@Override
public boolean isEmpty() {
//the tree is empty if and only if the root is null
return root == null;
}
//@Override
public Position<E> root() {
return root;
}
//@Override
public void setRoot(Position<E> root) {
this.root = root;
}
//@Override
public Position<E> parent(Position<E> position) {
return position.getParent();
}
//@Override
public List<Position<E>> children(Position<E> position) {
return position.getChildren();
}
//@Override
public int numChildren(Position<E> position) {
return position.getChildren().size();
}
//insert the position 'child' under the position 'parent'
//@Override
public void insert(Position<E> parent, Position<E> child) {
parent.addChild(child);
child.setParent(parent);
}
//remove the position from the tree
//@Override
public void remove(Position<E> position) {
//if we needed to do anything extra when removing each node, such as
//keeping track of the size of the tree, then we would need to
//recursively call remove on all the child nodes first, like this:
//for(Position<E> child : position.getChildren()) {
// remove(child);
//}
//handle edge case: removing the root
if(position.equals(root)) {
root = null;
}
//if the position has a parent, remove it from the parent
Position<E> parent = position.getParent();
if(parent != null) {
parent.removeChild(position);
position.setParent(null);
}
}
}
Tree.java
//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);
}
TreeArithmetic
//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)
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 it?s 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
}
TreeProperties.java
//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.
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 isComplete();
// is the tree complete?
// a complete tree is one where:
// 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 isBalanced();
// is the tree balanced?
// a balanced tree is one where the depth of any two leaves differs by no more than one.
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.
}
TreeTraversals.java
//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.
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.