Implement a method to convert a tree to a string. Your HW8Tree<E> class must inc
ID: 3607491 • Letter: I
Question
Implement a method to convert a tree to a string.
Your HW8Tree<E> class must include the BinaryNode.java code.
Your HW8Tree<E> class must have an instance variable that refers to (points to) the root of a tree. This class must provide these recursive methods:
a public boolean add(E item, boolean[] left) method to add values to the tree. Starting from the root, at each node, the method must go down to the left if the corresponding position in the array is true, and otherwise must go down to the right. Once a null pointer is reached, the item must be added to the tree in place of the null pointer.
It is an error if the array of booleans is too short. In this case, the add method should throw a RuntimeException.
a public List<E> toList() method that stores in a list a reference to each of the objects in the tree, as visited in an in-order traversal. You can choose what kind of list to use, as long as it satisfies the List interface.
a public String toString() method that converts the tree to a string, in the same way that folders are printed: the root is first, followed by the children of the node indented 4 spaces, the grandchildren indented 8 spaces, and so on.
Each of these methods must use recursion to traverse the tree. In each case, the recursion may be in a helper method.
For example, consider a tree with root "hello". "hello" has two children, "foo" and "bar". "foo" has children "world", and "baz", and "bar" has children "bug" and "loop".
The toString method converts the tree to the following string:
The above example shows what the string looks like when it is printed. As a string, it actually looks like this:
As many of you already know, " " is the newline character in Java.
Calling toList should return a list with contents world, foo, baz, hello, bug, bar, loop. Only this order correctly reflects an in-order traversal.
To add the string "fum" below and to the right of "bug", we would call
__________________________________________________________________________________________________
==============================BinaryNode.java=================================
Not sure if this will help, but what I have previously:
import lab.solution.BinaryTree;
===============================Main.java===============================
public class Main {
/**
* Write the function in the BinaryTree class to determine whether or not a given binary tree is a max or min heap
*/
public static void main(String args[])
{
//True
BinaryTree bt = new BinaryTree();
bt.add(50);
bt.add(20);
bt.add(25);
bt.add(13);
bt.add(12);
bt.add(15);
bt.add(2);
System.out.println(bt.isMaxHeap());
//False
BinaryTree bt1 = new BinaryTree();
bt1.add(50);
bt1.add(20);
bt1.add(25);
bt1.add(26);
bt1.add(12);
bt1.add(15);
bt1.add(2);
System.out.println(bt1.isMaxHeap());
//False
BinaryTree bt2 = new BinaryTree();
bt2.add(50);
bt2.add(20);
bt2.add(25);
bt2.add(13);
bt2.add(12);
bt2.add(15);
bt2.add(51);
System.out.println(bt2.isMaxHeap());
//False
BinaryTree bt3 = new BinaryTree();
bt3.add(50);
bt3.add(20);
bt3.add(25);
bt3.add(31);
bt3.add(12);
bt3.add(15);
bt3.add(2);
System.out.println(bt3.isMaxHeap());
//What do you think this should return?? :)
//What if we made equal cases not allowed? (IE. A parent node 30 with child node 30 is wrong for a max heap)
BinaryTree bt4 = new BinaryTree();
bt4.add(50);
bt4.add(20);
bt4.add(25); //This parent
bt4.add(13);
bt4.add(12);
bt4.add(15);
bt4.add(25); //Has this child
System.out.println(bt4.isMaxHeap());
//Try writing a set of test cases for minHeap tests
BinaryTree bt5 = new BinaryTree();
bt5.add(2);
bt5.add(11);
bt5.add(13);
bt5.add(15);
bt5.add(25);
bt5.add(31);
bt5.add(50);
System.out.println(bt5.isMinHeap());
}
}
==================================BinaryTree.java===============================
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree {
private Node<Integer> root;
public BinaryTree()
{
this.root = null;
}
public BinaryTree(Node<Integer> root)
{
this.root = root;
}
/**
* Implement this function.
* @return true if if our tree is a Max Heap, false otherwise.
*/
public boolean isMaxHeap()
{
Node<Integer> temp = root;
if (temp.getLeft().getItem() < root.getItem()
&& temp.getRight().getItem() < root.getItem()) {
temp = temp.getLeft();
return true;
}
while(temp != null)
{
if (temp.getItem() > temp.getLeft().getItem())
{
//temp = temp.getLeft();
}
}
return false;
}
/**
* Implement this function.
* @return true if if our tree is a Min Heap, false otherwise.
*/
public boolean isMinHeap()
{
Node<Integer> temp = root;
if (temp.getLeft().getItem() > temp.getItem()
&& temp.getRight().getItem() > temp.getItem()) {
return true;
}
return false;
}
/**
* @return true if our tree is a Binary Tree, false if it's not a Binary Tree
* If root is null, return false
*/
public boolean isBST()
{
Node<Integer> temp = root;
if(temp == null)
{
//A null tree/empty tree is still a BST
return true;
}
else
{
Queue<Node<Integer>> q = new LinkedList<Node<Integer>>();
q.offer(root);
while(!q.isEmpty())
{
if(q.peek().getLeft() != null)
{
q.offer(q.peek().getLeft());
}
if(q.peek().getRight() != null)
{
q.offer(q.peek().getRight());
}
//The one instance where I cannot find an item that definitely exists in my tree
//using a BST "find" logic, then I know my tree is not a BST
if(!canFindItem(q.poll().getItem()))
return false;
}
}
return true;
}
public boolean canFindItem(int item)
{
if(root != null)
{
Node<Integer> temp = root;
while(temp != null)
{
if(temp.getItem() == item)
{
return true;
}
if(temp.getItem() > item)
{
temp = temp.getLeft();
}
else
{
temp = temp.getRight();
}
}
}
return false;
}
public void add(int item)
{
Node<Integer> temp = root;
Queue<Node<Integer>> q = new LinkedList<Node<Integer>>();
if(temp == null)
{
root = new Node<Integer>(item);
}
else
{
q.offer(temp);
while(!q.isEmpty())
{
//If there is no children, add left
if(q.peek().getLeft() == null && q.peek().getRight() == null)
{
temp = q.poll();
temp.setLeft(new Node<Integer>(item));
break;
}
//Left exists but right does not exist, add to the right
else if(q.peek().getLeft() != null && q.peek().getRight() == null)
{
temp = q.poll();
temp.setRight(new Node<Integer>(item));
break;
}
//Both not null, need to traverse both directions
else
{
q.offer(q.peek().getLeft());
q.offer(q.peek().getRight());
q.poll();
}
}
}
}
/**
* Gets the level that the item is on in the BST
* @param item -- Item to find the level of
* @return level the item is on in the BST, returns -1
*/
public int getLevel(int item)
{
int level = 0;
Node<Integer> temp = root;
while(temp != null && temp.getItem() != item)
{
if(temp.getItem() < item)
{
temp = temp.getRight();
}
else
{
temp = temp.getLeft();
}
level++;
}
return (temp == null) ? -1 : level;
}
public void printAsString()
{
if(root != null)
{
Queue<Node<Integer>> q = new LinkedList<Node<Integer>>();
q.offer(root);
while(!q.isEmpty())
{
if(q.peek().getLeft() != null)
{
q.offer(q.peek().getLeft());
}
if(q.peek().getRight() != null)
{
q.offer(q.peek().getRight());
}
System.out.println(q.poll().getItem());
}
}
}
}
==============================Node.java==============================
public class Node<E> {
private Node<E> left, right;
private E item;
public Node(E item)
{
this.item = item;
}
public void setItem(E item)
{
this.item = item;
}
public E getItem()
{
return this.item;
}
public void setLeft(Node<E> left)
{
this.left = left;
}
public Node<E> getLeft()
{
return this.left;
}
public void setRight(Node<E> right)
{
this.right = right;
}
public Node<E> getRight()
{
return this.right;
}
}
________________________________________________________________________________________________
RuntimeException: (http://docs.oracle.com/javase/8/docs/api/java/lang/RuntimeException.html)
List interface: (http://docs.oracle.com/javase/8/docs/api/java/util/List.html)
Please briefly comment what parts of the code does, Thanks.
Explanation / Answer
Given below is the code with output. Please don't forget to rate the answer if it helped.
Thank you.
To indent code in eclipse, select code by pressing Ctrl+A and then Ctrl+i
HW8Tree.java
import java.util.ArrayList;
import java.util.List;
public class HW8Tree<E> {
private static class BinaryNode<T> {
private T item;
private BinaryNode<T> left;
private BinaryNode<T> right;
/**
* constructor to build a node with no subtrees
* @param the value to be stored by this node
*/
private BinaryNode(T value) {
item = value;
left = null;
right = null;
}
/**
* constructor to build a node with a specified (perhaps null) subtrees
* @param the value to be stored by this node
* @param the left subtree for this node
* @param the right subtree for this node
*/
private BinaryNode(T value, BinaryNode<T> l, BinaryNode<T> r) {
item = value;
left = l;
right = r;
}
}
private BinaryNode<E> root;
public HW8Tree()
{
root = null;
}
private boolean add(BinaryNode<E> node, E item, boolean[] left, int index)
{
if(index == left.length-1) //reached the last entry in the array
{
if(left[index])
{
if(node.left != null)
throw new RuntimeException("The left array is shorter");
else
node.left = new BinaryNode<E>(item, null,null);
return true;
}
else
{
if(node.right != null)
throw new RuntimeException("The left array is shorter");
else
node.right = new BinaryNode<E>(item, null,null);
return true;
}
}
else
{
if(node == null) //the tree does not have any more nodes to go left or right
return false;
if(left[index]) //should go to left?
return add(node.left, item, left, index+1); //increment index and pass left child
else
return add(node.right, item, left, index+1); //increment index and pass left child
}
}
public boolean add(E item, boolean[] left)
{
if(root == null) //when tree is empty
{
root = new BinaryNode<E>(item, null, null);
return true;
}
else
{
return add(root, item, left, 0);
}
}
public List<E> toList()
{
ArrayList<E> list = new ArrayList<E>();
toList(root, list);
return list;
}
private void toList(BinaryNode<E> n, List<E> list) //helper method
{
if(n == null)
return;
else
{
toList(n.left, list);
list.add(n.item);
toList(n.right, list);
}
}
public String toString()
{
return toString(root, "");
}
private String toString(BinaryNode<E> n, String indent)
{
if(n == null)
return "";
else
{
String spaces = " " + " " + " " + " ";
String str = indent + n.item + " ";
str += toString(n.left, indent+spaces);
str += toString(n.right, indent+spaces);
return str;
}
}
}
=============================
HW8TreeTest.java
public class HW8TreeTest {
public static void main(String[] args) {
HW8Tree<String> t = new HW8Tree<String>();
t.add("hello", null);
t.add("foo", new boolean[]{true});
t.add("bar", new boolean[]{false});
System.out.println("Tree after adding hello, foo , bar");
System.out.println(t.toString());
t.add("world", new boolean[]{true, true});
t.add("baz", new boolean[]{true, false});
t.add("bug", new boolean[]{false, true});
t.add("loop", new boolean[]{false, false});
System.out.println("Tree after adding world baz bug loop");
System.out.println(t.toString());
System.out.println("toList() contains");
System.out.println(t.toList());
}
}
=====================
output
Tree after adding hello, foo , bar
hello
foo
bar
Tree after adding world baz bug loop
hello
foo
world
baz
bar
bug
loop
toList() contains
[world, foo, baz, hello, bug, bar, loop]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.