In all cases, the children of a node should be visited in the same order in whic
ID: 668495 • Letter: I
Question
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 preorder traversal of the tree
public List<E> postOrder() // Output the values of a postorder traversal of the tree
public List<E> inOrder() // Output the values of a inorder 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.
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
}
}
}
Interface oultine for tree traversal :-
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.
}
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.