Please implement your solutions as static methods in the class TreeRebuilder sho
ID: 3644885 • Letter: P
Question
Please implement your solutions as static methods in the class TreeRebuilder shown below. The TreeNode type and some traversal examples are below.public class TreeRebuilder
{
// Returns the root of a tree whose preorder and inorder traversals
// match the given data
public static TreeNode<String> rebuildFromPreAndInorder(List<String>preorderData,
List<String> inorderData)
{
//TODO:your code for part(a)
return null;
}
// Returns the root of a tree whose breadth-first traversal and child
// counts match the given data
public static TreeNode<String> rebuildFromBFSList(List<String> bfsData,
List<Integer> childCounts)
{
// TODO: your code for part (b)
return null;
}
}
Note:
TREENODE CLASS
public class TreeNode<E>
{
protected TreeNode<E> left;
protected TreeNode<E> right;
protected E data;
public TreeNode(){}
public TreeNode(E data)
{
this(data, null, null);
}
public TreeNode(E data, TreeNode<E> left, TreeNode<E> right)
{
this.left = left;
this.right = right;
this.data = data;
}
public boolean isLeaf()
{
return left == null && right == null;
}
public TreeNode<E> left()
{
return left;
}
public void setLeft(TreeNode<E> left)
{
this.left = left;
}
public TreeNode<E> right()
{
return right;
}
public void setRight(TreeNode<E> right)
{
this.right = right;
}
public E data()
{
return data;
}
public void setData(E data)
{
this.data = data;
}
}
TRAVERSALEXAMPLES
import java.util.LinkedList;
import java.util.Queue;
public class TraversalExamples
{
/**
* @param args
*/
public static void main(String[] args)
{
// Creates the tree:
//
// A
// /
// B C
// /
// D E
// /
// F G
//
TreeNode<String> l1 = new TreeNode<String>("D");
TreeNode<String> l2 = new TreeNode<String>("F");
TreeNode<String> l3 = new TreeNode<String>("G");
TreeNode<String> l4 = new TreeNode<String>("C");
TreeNode<String> sub1 = new TreeNode<String>("E", l2, l3);
TreeNode<String> sub2 = new TreeNode<String>("B", l1, sub1);
TreeNode<String> root = new TreeNode<String>("A", sub2, l4);
// Try a traversal algorithm
traversePreorder(root);
}
public static void traversePreorder(TreeNode<?> node)
{
if (node == null) return;
System.out.print(node.data().toString() + " ");
traversePreorder(node.left());
traversePreorder(node.right());
}
public static void traversePostorder(TreeNode<?> node)
{
if (node == null) return;
traversePostorder(node.left());
traversePostorder(node.right());
System.out.print(node.data().toString() + " ");
}
public static void traverseInorder(TreeNode<?> node)
{
if (node == null) return;
traverseInorder(node.left());
System.out.print(node.data().toString() + " ");
traverseInorder(node.right());
}
public static int height(TreeNode<?> node)
{
if (node == null) return 0;
int leftHeight = height(node.left());
int rightHeight = height(node.right());
return 1 + Math.max(leftHeight, rightHeight);
}
public static int size(TreeNode<?> node)
{
if (node == null) return 0;
return 1 + size(node.left()) + size(node.right());
}
public static void traverseLevelorder(TreeNode<?> node)
{
Queue<TreeNode<?>> q = new LinkedList<TreeNode<?>>();
if (node != null)
{
q.add(node);
}
while (!q.isEmpty())
{
TreeNode<?> current = q.remove();
if (current.left() != null) q.add(current.left());
if (current.right() != null) q.add(current.right());
System.out.print(current.data().toString() + " ");
}
}
}
Explanation / Answer
Java Code:
public class BinaryTreeTest {
public static void main(String[] args) {
new BinaryTreeTest().run();
}
static class Node {
Node left;
Node right;
int value;
public Node(int value) {
this.value = value;
}
}
public void run() {
// build the simple tree from chapter 11.
Node root = new Node(5);
System.out.println("Binary Tree Example");
System.out.println("Building tree with root value " + root.value);
insert(root, 1);
insert(root, 8);
insert(root, 6);
insert(root, 3);
insert(root, 9);
System.out.println("Traversing tree in order");
printInOrder(root);
System.out.println("Traversing tree front-to-back from location 7");
printFrontToBack(root, 7);
}
public void insert(Node node, int value) {
if (value < node.value) {
if (node.left != null) {
insert(node.left, value);
} else {
System.out.println(" Inserted " + value + " to left of "
+ node.value);
node.left = new Node(value);
}
} else if (value > node.value) {
if (node.right != null) {
insert(node.right, value);
} else {
System.out.println(" Inserted " + value + " to right of "
+ node.value);
node.right = new Node(value);
}
}
}
public void printInOrder(Node node) {
if (node != null) {
printInOrder(node.left);
System.out.println(" Traversed " + node.value);
printInOrder(node.right);
}
}
/**
* uses in-order traversal when the origin is less than the node's value
*
* uses reverse-order traversal when the origin is greater than the node's
* order
*/
public void printFrontToBack(Node node, int camera) {
if (node == null)
return;
if (node.value > camera) {
// print in order
printFrontToBack(node.left, camera);
System.out.println(" Traversed " + node.value);
printFrontToBack(node.right, camera);
} else if (node.value < camera) {
// print reverse order
printFrontToBack(node.right, camera);
System.out.println(" Traversed " + node.value);
printFrontToBack(node.left, camera);
} else {
// order doesn't matter
printFrontToBack(node.left, camera);
printFrontToBack(node.right, camera);
}
}
}