/* Example to use pointers to construct a 4 level tree with a 4 digit
code to locate nodes within the tree*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct
{
   int no_child, h_code[4];
   char nodename[30];
   struct node *parent, *child[10]; 
} node;

int main (void)
{

  int i;
  node *rootnode,*newnode;

  void initialise_node(node *n)
  /* a procedure for intialising nodes */
  {
     int j;   /* local variable */
     for (j=0; j<4; ++j) n->h_code[j] = 0;  
     for (j=0; j<10; ++j) n->child[j] = 0; /* point children to null */
     n->no_child = 0;
  }

  void print_nodes(node *n)
  /* a recursive procedure for printing out node data */
  {
     int i,j;
     node *tp;
     printf("Node code = ");
     for (j=0; j<4; ++j) printf("%i ",n->h_code[j]); 
     printf("\n");
     if (n->no_child > 0) 
     { 
       for (i=0; i < n->no_child; i++) 
       {
          tp = n->child[i]; /* needed to avoid incompatible pointer error ?!? */
          print_nodes(tp); /* print_nodes(n->child[i]) gets compile errors!! */
       }
     }
     else
     {
         printf("Node code: ");
         for (i=0; i<4; ++i) printf("%i ",n->h_code[i]);
         printf("\n");
     }
  }


  void create_node(node *parent)
  {
     int i,j,k;
     printf("How many children does node ");
     for (k=0; k<4; ++k) printf("%i ",parent->h_code[k]);
     printf("have?\n");
     scanf("%i",&parent->no_child); 
     if (parent->no_child > 0)  
        for (i=0; i<parent->no_child; ++i)
        { 
           newnode = (node *) malloc (sizeof (node));
           initialise_node(newnode);
           newnode->parent = parent;
           parent->child[i] = newnode;
            
           /* copy the parent's code number */ 
           k = 0;        
           while ((k<4) && (parent->h_code[k] != 0))
           { 
              newnode->h_code[k] = parent->h_code[k];
              k = k + 1;
           }  
           if (k < 4) /*add the child's code number to the next h_code element */
           {
              if (parent->h_code[0] == 0) newnode->h_code[k] = i+1;
              else   newnode->h_code[k] = i+1; 
              if (k < 3) create_node(newnode); /*leaf nodes */
           }
           else newnode->no_child = 0;
        } 
  }

  rootnode = (node *) malloc (sizeof (node));
  initialise_node(rootnode);
  create_node(rootnode);
  print_nodes(rootnode);
 }