Consider a rooted binary tree where each internal intermedia

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)

c. Guarded if, guarded do statements, commands

Solution

#include<stdio.h>

#include<stdlib.h>

  

/* This is to create a binary tree node which has data, pointer to left child and a pointer to right child */

struct node

{

   int data;

   struct node* left;

   struct node* right;

};

void toprintPathsRecursive(struct node* node, int path[], int pathLength);

void toprinttheArray(int ints[], int length);

/*This is the function which is used print out all root-to-leaf

paths, one per line. It uses a recursive function.

void toprintPaths(struct node* node)

{

  int path[1000];

  toprintPathsRecursive(node, path, 0);

}

/* This function is used to print out all the root-leaf paths.*/

void toprintPathsRecursive(struct node* node, int path[], int pathLength)

{

  if (node==NULL)

    return;

  /* Now we will append this node to the path array */

  path[pathLength] = node->data;

  pathLength++;

  /*If it\'s a leaf then we willprint the path that led to here */

  if (node->left==NULL && node->right==NULL)

  {

    toprinttheArray(path, pathLength);

  }

  else

  {

    /*otherwise we will try both subtrees */

    toprintPathsRecursive(node->left, path, pathLength);

    toprintPathsRecursive(node->right, path, pathLength);

  }

}

/*This fuction is used to print out an array on a line. */

void toprinttheArray(int integers[], int length)

{

  int i;

  for (i=0; i<length; i++)

  {

    printf(\"%d \", integers[i]);

  }

  printf(\"\ \");

}   

/* This is used to allocatea a new node with given data and NULL left and right pointers. */  

struct node* newnode(int data)

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

  

  return(node);

}

  

/* Finally we have the driver program to test above functions*/

int main()

{

  

  

  struct node *createroot = newnode(15);

  createroot->left        = newnode(10);

  createroot->right       = newnode(12);

  createroot->left->left = newnode(7);

  createroot->left->right = newnode(4);

  reateroot->right->left = newnode(1);

  

  toprintPaths(createroot);

  

  getchar();

  return 0;

}