RADIX TREE

/* This is a program to implement RADIX tree. For more details on radix tree please refer to the link below -
http://en.wikipedia.org/wiki/Radix_tree

This program implements as shown in below figure. All the child nodes will be neighbors to first child

*/

NOTE: Please add the words in a file named dict,txt and keep in the same folder as the this program

/* program start*/

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

#define ALLOC_NODE (NODE *)malloc(sizeof(NODE))
#define ALLOC_CHAR(len) (char *) malloc(len+1)
#define ALLOC_LINK  (LINK*)malloc(sizeof(LINK))

typedef struct _node
{
char *str;
struct _node *nxt,*nbr;
}NODE;

typedef struct link
{
NODE *node;
struct link *prv;
}LINK;

void radix_create(NODE *node);
void radix_traverse(NODE *node, char *str);
NODE *radix_new_node(int len);
int radix_cmp(char *str1,char *str2);

NODE *radix_new_node(int len)
{
NODE *temp;
temp = ALLOC_NODE;
temp->nbr = NULL;
temp->nxt = NULL;
temp->str = ALLOC_CHAR(len+1);

return temp;
}


main()
{
NODE root;

root.nbr =NULL;
root.nxt = NULL;
root.str = NULL;
radix_create(&root);

return 0;
}

void radix_create(NODE *node)
{
FILE *fp;
char str[20];
NODE *tmp;

fp = fopen("dict.txt","r");
while(1)
{
if(EOF == fscanf(fp,"%s",str))
{
break;
}
else
{
if(node->nxt == NULL)
{
tmp = radix_new_node(strlen(str));
strcpy(tmp->str,str);
node->nxt = tmp;
}
else
{
radix_traverse(node->nxt,str);
}
}
}
return;
}

void radix_traverse( NODE *node, char *str)
{
NODE *temp1,*temp2;
int len,len1,len2;
char *tmp_str;

len = radix_cmp(node->str,str);
len1 = strlen(node->str);
len2 = strlen(str);
// already string is inserted
if(str[0]=='\0')
return;

if(len == 0)
{
// No match
if(node->nbr !=NULL)
{
radix_traverse(node->nbr,str);
}
else
{
temp1 = radix_new_node(len2);
strcpy(temp1->str,str);
node->nbr = temp1;
}
}
else if((len <len1) || (len == len1 && node->nxt == NULL))
{
// partial match or full match without leaves
temp1 = radix_new_node(len1-len);
temp2 = radix_new_node(len2-len);
memcpy(temp1->str,node->str+len,len1-len+1);
memcpy(temp2->str,str+len,len2-len+1);

temp1->nbr = temp2;
temp1->nxt = node->nxt;
node->nxt = temp1;

tmp_str = ALLOC_CHAR(len);
memcpy(tmp_str, node->str,len);
tmp_str[len] = '\0';
free(node->str);
node->str = tmp_str;
}
else
{
//full match
memcpy(str,str+len,len2-len+1);
radix_traverse(node->nxt,str);
}

return;
}

int radix_cmp(char *str1, char * str2)
{
int i=0;
while( str1[i] !='\0' && str2[i] != '\0' && str1[i] == str2[i])
{
i++;
}

return i;
}

/* END */