Write a general program for growing a binary tree and use it

Write a general program for growing a binary tree and use it to train a tree fully using the data from the three categories in the table, using an entropy impurity. Use the (unpruned) tree to classify the following patterns: {A, E, I, L, N}, {D, E, J, K, N}, {B, F, J, K, M}, and {C, D, J, L, N}. Prune one pair of leafs, increasing the entropy impurity as little as possible. Modify your program to allow for non-binary splits, where the branching ratio B as is determined at each node during training. Train a new tree fully using a gain ratio impurity and then classify the points in (a).

Solution

# include<stdio.h>
# include<malloc.h>

struct NODE
{
   char Info;
   struct NODE *Left_Child;
   struct NODE *Right_Child;
};

int flag = 0;
struct NODE *Binary_Tree (char *, int, int);
void Output(struct NODE *, int );
int Search_Node(struct NODE *, char);

/* Function to create an binary tree */

struct NODE * Binary_Tree (char *List, int Lower, int Upper)
{
   struct NODE *Node;
   int Mid = (Lower + Upper)/2;
   Node = (struct NODE*) malloc(sizeof(struct NODE));

   Node->Info = List [Mid];
   if ( Lower>= Upper)
   {
       Node->Left_Child = NULL;
       Node->Right_Child = NULL;
       return (Node);
   }
   if (Lower <= Mid - 1)
       Node->Left_Child = Binary_Tree (List, Lower, Mid - 1);
   else
       Node->Left_Child = NULL;
   if (Mid + 1 <= Upper)
       Node->Right_Child = Binary_Tree (List, Mid + 1, Upper);
   else
       Node->Right_Child = NULL;
   return(Node);
}

/* Output function */

void Output(struct NODE *T, int Level)
{
   int i;
   if (T)
   {
       Output(T->Right_Child, Level+1);
       printf(\"\ \");
       for (i = 0; i < Level; i++)
           printf(\" \");
       printf(\"%c\", T->Info);
       Output(T->Left_Child, Level+1);
   }
}

/* Insert a node in the tree */

int Search_Node(struct NODE *Node, char Info)
{
   while (Node != NULL)
   {
       if (Node->Info == Info)
       {
           flag = 1;
           return(flag);
       }
       else
           if(Info < Node->Info)
           {
               Node = Node->Left_Child;
           }
           else
           {
               Node = Node->Right_Child;
           }
   }
   return(flag);
}

/* Function main */

void main()
{
   int flag;
   char List[100];
   int Number = 0;
   char Info ;
   char choice;
   struct NODE *T = (struct NODE *) malloc(sizeof(struct NODE));
   T = NULL;
   printf(\"\ Insert Nodes in binary tree\");
   choice = getchar();
   while(choice != \'b\')
   {
       fflush(stdin);
       printf(\"\ Input information of the node: \");
       scanf(\"%c\", &Info);
       List[Number++] = Info;
       fflush(stdin);
       printf(\"\ Input choice \'b\' to break otherwise continue to insert:\");
       choice = getchar();
   }
   Number --;
   printf(\"\ Number of elements in the list is %d\", Number+1);
   T = Binary_Tree(List, 0, Number);
   printf(\"\ Tree is \ \");
   Output(T, 1);
   fflush(stdin);
   printf(\"\ Input the information of the node to which want to search: \");
   scanf(\"%c\", &Info);
   flag = Search_Node(T, Info);
   if (flag)
   {
       printf(\"\ Search is successful \ \");
   }
   else
       printf(\"Search unsuccessful\");
}