Consider a rooted binary tree, where each internal (intermediate) node has 2 chi
ID: 3775711 • Letter: C
Question
Consider a rooted binary tree, where each internal (intermediate) node has 2 children. Assume each node, in particular, the leaves, has a symbol or variable associated with it. For the edges from each node to its children, associate a value 1 to one edge, and a value 0 to the other edge. A special case of such trees is the Huffman tree, or Huffman coding tree. Another special case is binary decision trees. One goal is to determine the code or sequence of 0’s and 1’s that result when one traverses a path from the root to each leaf of the tree. Devise an algorithm, pseudo-code or source code to implement the generation of such root-toleaf codes, using each of the following approaches. (Hint: in case of difficulty handling the general case for arbitrary binary trees, try to first devise solutions for concrete examples of the weighted binary trees of depths 1, 2, 3, 4, 5, 6, 7, 8, and then try to tackle the general case). (Hint: use concepts and tools of procedures, functions and recursion to achieve modularity)
b. Case-switch statements, expressions
Explanation / Answer
//pseudo-code or source code to implement the generation of such root-toleaf codes, using concepts and tools of procedures, functions and recursion to achieve modularity
import java.util.Scanner;
public class RootToLeafTraversal {
Node root;
/*Given a binary tree, print out all of its root-to-leaf
paths, one per line.*/
void printPaths(Node node)
{
int path[] = new int[1000];
recursePrintPaths(node, path, 0);
}
/* Recursive helper function.*/
void recursePrintPaths(Node node, int path[], int pathLength)
{
if (node == null)
return;
/* append this node to the path array */
path[pathLength] = node.data;
pathLength++;
/* it's a leaf, so print the path that led to here */
if (node.left == null && node.right == null)
printRootToLeafPath(path, pathLength);
else
{
/*try left subtree */
recursePrintPaths(node.left, path, pathLength);
/*try right subtree */
recursePrintPaths(node.right, path, pathLength);
}
}
/* Utility function that prints out root to leaf path on a line. */
void printRootToLeafPath(int ints[], int len)
{
int i;
for (i = 0; i < len; i++)
{
System.out.print(ints[i] + " ");
}
System.out.println("");
}
public void insert(int id){
Node newNode = new Node(id);
if(root==null){
root = newNode;
return;
}
Node current = root;
Node parent = null;
while(true){
parent = current;
if(id<current.data){
current = current.left;
if(current==null){
parent.left = newNode;
return;
}
}else{
current = current.right;
if(current==null){
parent.right = newNode;
return;
}
}
}
}
public void display(Node root){
if(root!=null){
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
public static void main(String args[])
{
RootToLeafTraversal tree = new RootToLeafTraversal();
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of nodes of tree");
int nodeCount = scan.nextInt();
for (int i = 0; i < nodeCount; i++) {
System.out.println("Enter the " + (i+1) + "th nodeValue of tree");
tree.insert(scan.nextInt());
}
/* Printing InOrder traversal */
tree.printPaths(tree.root);
}
}
public class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}