#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <string.h>



typedef struct _DLTree{

	char symbol; // key

	struct _DLTree *next;

	int kind; // 0-leaf; 1-branch

	union{

		char *infoptr; //Pointer to the data

		struct _DLTree *first;

	};

}DLTree;



void *SearchDLTree(DLTree *T, char *keys, DLTree **f, int *idx)

{

	int i = 0;

	DLTree *p = T->first;

	int n = strlen(keys);

	*f = T;

	*idx = i;

	while(p && i< n ){

		while(p && p->symbol != keys[i]){

			p = p->next;

		}

		if(p && i<n-1 ){

			*f = p;

			*idx = i+1;

			p = p->first;

		}

		i++;

	}



	if(!p){

		return NULL;

	}else{

		return p->infoptr;

	}

}



void InsertDLTree(DLTree *T, char *keys)

{

	DLTree *F;

	DLTree *p;

	int ret = 0;

	int i;

	int n = strlen(keys);



	while( !SearchDLTree(T, keys, &F, &i) ){

		p = (DLTree *)malloc(sizeof(DLTree));

		p->symbol = keys[i]; 

		p->next = NULL;

		if(i==n-1){

			p->kind = 0;

			p->infoptr = keys;

		}else{

			p->kind = 1;

			p->first = NULL;

		}

		if(!F->first){

			F->first = p;

		}else{

			F = F->first;

			while(F->next){

				F = F->next;

			}

			F->next = p;

		}

	}

}



void main()

{

	char seq1[] = "aboutge$"; 

	char seq2[] = "hello$"; 

	char seq3[] = "world$"; 

	char seq4[] = "again$"; 

	char seq5[] = "help$"; 

	int i;

	DLTree *F;

	DLTree T;



	T.next = NULL;

	T.kind = 1;

	T.symbol = 0;

	T.first = NULL;



	printf("log.anycle.com\n\n");

	printf("Original data:\n");

	printf("%s", seq1);

	printf("%s", seq2);

	printf("%s", seq3);

	printf("%s", seq4);

	printf("%s", seq5);

	printf("\n");



	printf("Insert double links tree:\n");

	InsertDLTree(&T, seq1);

	InsertDLTree(&T, seq2);

	InsertDLTree(&T, seq3);

	InsertDLTree(&T, seq4);

	InsertDLTree(&T, seq5);



	printf("Print the tree:\n");

	printf("%s", (char *)SearchDLTree(&T, seq2, &F, &i) );

	printf("\n");

}