#include <conio.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct int_n
{
	int l;
	struct int_n *a[27];
	char  key[20];
}intern_nod;
void regasire(intern_nod *rad,char new_key[20])
{
intern_nod *next,*index,*data;
int i;
next=rad;
if(next==NULL)
{
	printf("\n inregistrare lipsa");
	exit(1);
}
else index=next;
i=0;
while((index->l==1)&&(index->a[new_key[i]-'a']!=NULL))
{
	next=index->a[new_key[i]-'a'];
	index=next;
	i++;
}
if(next==NULL)
printf("\n inregistrare lipsa");
else
{
	data=next;
	if(!strcmp(data->key,new_key))
		printf("\n inregistrare=%s\n",data->key);
	else 
		if(!strcmp(data->a[26]->key,new_key))
			printf("\n inregistrare=%s\n",data->a[26]->key);
			else
			printf("\n inregistrare lipsa");
}
}
intern_nod *NewFrunza(char n_key[20])
{
intern_nod *p;
int i;
p=new intern_nod;
for(i=0;i<=27;i++)
 p->a[i]=NULL;
p->l=0;
strcpy(p->key,n_key);
return p;
}
intern_nod *NewIntern()
{
intern_nod *p;
int i;
p=new intern_nod;
for(i=0;i<=27;i++)
p->a[i]=NULL;
p->l=1;
return p;
}
intern_nod *insert(intern_nod *rad,char new_key[20])
{
intern_nod *next,*index,*parent;
intern_nod *new_leaf,*data;
intern_nod *new_index;
intern_nod *salv1,*salv2;
intern_nod *at;
int i,j;
next=rad;
if(next==NULL)
{
	rad=NewIntern();
	new_leaf=NewFrunza(new_key);
	rad->a[new_key[0]-'a']=new_leaf;
	return rad;
}
else
 index=next;
i=0;
while((index->l==1)&&(index->a[new_key[i]-'a']!=NULL))
{
	parent=next;
	next=index->a[new_key[i]-'a'];
	index=next;
	i++;
}
if((index->a[new_key[i]-'a']==NULL)&&(index->l==1))
{
	new_index=NewFrunza(new_key);
	index->a[new_key[i]-'a']=new_index;
	return rad;
}
else
  data=next;
if(!strcmp(data->key,new_key))
  printf("\n inregistrarea exista!");
else
{
	salv1=parent->a[new_key[i-1]-'a'];
	salv2=NewFrunza(new_key);
	j=strlen(new_key);
	if(strlen(data->key)<j)
		j=strlen(data->key);
}
while((i<=j)&&(data->key[i-1]==new_key[i-1]))
{
	at=NewIntern();
	parent->a[new_key[i-1]-'a']=at;
	parent->l=1;
	parent=at;
	i++;
}
i--;
if((i!=j)||((i==j)&&(strlen(new_key)==strlen(data->key))))
{
	parent->a[data->key[i]-'a']=salv1;
	parent->a[new_key[i]-'a']=salv2;
}
else
if(strlen(data->key)<=j)
{
	parent->a[26]=salv1;
	parent->a[new_key[j]-'a']=salv2;
}
else
{
	parent->a[26]=salv2;
	parent->a[new_key[j]-'a']=salv1;
}
return rad;
}
void afisare_arb(intern_nod *rad,int nivel)
{
	int i;
	if (rad!=0)
		if(rad->l==0)
		{ for(int j=0;j<nivel;j++)
		  printf(" ");
		printf("%s",rad->key);
		}
		else
		
			for (i=26;i>=0;i--)
				afisare_arb(rad->a[i],nivel+1);
}		

void main()
{
intern_nod *rad;
char ch[20],c;
rad=NULL;
do
{
	printf("\n introduceti cuv de inserat:");
	gets(ch);
    rad=insert(rad,ch);
	regasire(rad,ch);
	printf("\n continuati?");
	c=getch();
}while(c!='n');
do
{
	printf("\n 1Inserare, 2Cautare, 3Afisare sau 4 Exit?");
	c=getch();
	
	switch(c)
	{
	case'1':printf("\n dati cuv de inserat:");
		 gets(ch);
		 insert(rad,ch);
		 break;
	case '2':printf("\n introd cuv de cautat:");
		     gets(ch);
			 regasire(rad,ch);
			 break;
	case'3':printf("\n");
		afisare_arb(rad,0);break;
    case '4':exit(1);
	default:printf("\n eroare!!!");
	}
}while(c!='4');
}