Topic: Trees In this assignment, you implement a method to convert a tree to a s
ID: 3603442 • Letter: T
Question
Topic: Trees
In this assignment, you 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
You should also create a test class that lets you test your code. You do not need to turn in the test class. <<< Java Programming
====================================
Explanation / Answer
class Node
private static class BinaryNode<T> {
private T item;
private BinaryNode<T> left;
private BinaryNode<T> right;
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
// A utility function to check if a given node is leaf or not
boolean isLeaf(Node node)
{
if (node == null)
return false;
if (node.left == null && node.right == null)
return true;
return false;
}
// This function returns sum of all left leaves in a given
// binary tree
int leftLeavesSum(Node node)
{
// Initialize result
int res = 0;
// Update result if root is not NULL
if (node != null)
{
// If left of root is NULL, then add key of
// left child
if (isLeaf(node.left))
res += node.left.data;
else // Else recur for left child of root
res += leftLeavesSum(node.left);
// Recur for right child of root and update res
res += leftLeavesSum(node.right);
}
// return result
return res;
}
// Driver program
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(20);
tree.root.left = new Node(9);
tree.root.right = new Node(49);
tree.root.left.right = new Node(12);
tree.root.left.left = new Node(5);
tree.root.right.left = new Node(23);
tree.root.right.right = new Node(52);
tree.root.left.right.right = new Node(12);
tree.root.right.right.left = new Node(50);
System.out.println("The sum of leaves is " +
tree.leftLeavesSum(tree.root));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.