#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#define MAX_LETTERS 27#define MAX_CHAR 30//字符串的长度typedef enum  {data,pointer}node_type;typedef struct trie_node *trie_pointer;struct trie_node{	int child;	node_type tag;	union{		char*key;		trie_pointer letters[MAX_LETTERS];	}u;};int get_index(char*key,int i);void insert(trie_pointer t,char*key,int i);void insert_two(trie_pointer t,char*key,trie_pointer oldkey,int i);trie_pointer newnode();trie_pointer newnodekey(char*);/*指针结构体*/trie_pointer search(trie_pointer t,char* key,int i);trie_pointer del(trie_pointer r,char* key,int i);void look(trie_pointer r,char*key);void main(){	trie_node root;	root.child=1;	root.tag=pointer;	for (int i = 0; i < MAX_LETTERS; ++i)		root.u.letters[i]=NULL;		insert(&root,"bluebird",0);	insert(&root,"bunting",0);	insert(&root,"bluejay",0);	insert(&root,"bobwhite",0);	insert(&root,"luebird",0);	insert(&root,"ting",0);	insert(&root,"lujay",0);	insert(&root,"bobwte",0);		insert(&root,"aluebird",0);	insert(&root,"ung",0);	insert(&root,"ejay",0);	insert(&root,"white",0);		insert(&root,"ebird",0);	insert(&root,"tig",0);	insert(&root,"bluejay",0);	insert(&root,"bobwh",0);    look(&root,"aaa");    look(&root,"bluebird");    look(&root,"bobwhite");	del(&root,"bobwhite",0);	look(&root,"bobwhite");	look(&root,"bunting");	del(&root,"bunting",0);	look(&root,"bunting");	del(&root,"aaaa",0);}void insert(trie_pointer t,char*key,int i){	int ki=get_index(key,i);	trie_pointer n=t->u.letters[ki];	if (n == NULL)	{		trie_pointer n=newnodekey(key);		t->u.letters[ki]=n;/*结构体加进去*/		++t->child;	}	else{/*这个区有东西*/		if (n->tag == pointer)/*u中是指针*/		{			insert(n,key,i+1);		}		else{/*u中是key*/			if(! strcmp(key,n->u.key)){				printf("已经存在%s\n",key );				return;			}			insert_two(t,key,t->u.letters[ki],i);		}	}}int get_index(char*key,int i){	if (key[i]==NULL)	  return 0;	return tolower(key[i]) - 'a'+1;}void insert_two(trie_pointer t,char*key,trie_pointer oldkey,int i){	trie_pointer n;	do{				n= newnode();/*未处理新申请的*/				t->u.letters[get_index(key,i)]=n;/* 放入原始区，所以不用i+1 */		t=n;		++i;			}while(key[i] == oldkey->u.key[i]);	t->u.letters[get_index(oldkey->u.key,i)]=oldkey;/*原来的值*/    n=newnodekey(key);	t->u.letters[get_index(key,i)]=n;/*新的值*/	++t->child;}trie_pointer newnode(){/*指针结构体*/	trie_pointer n;	n= (trie_pointer)malloc(sizeof(struct trie_node));/*处理新申请的*/	for (int i = 0; i < MAX_LETTERS; ++i)	n->u.letters[i]=NULL;	n->tag=pointer;  return n;}trie_pointer newnodekey(char* charkey){/*值结构体*/	char *c=(char*)malloc(sizeof(char)* (strlen(charkey)+1) );/*注意释放*/	strcpy(c,charkey);	trie_pointer n= (trie_pointer)malloc(sizeof(struct trie_node));	n->u.key=c;	n->tag=data;/*新值的标配*/	n->child=1;	return n;}trie_pointer search(trie_pointer t,char* key,int i){	if (!t)return NULL;	if (t->tag==data)		return (strcmp(t->u.key,key))?NULL:t;	return search(t->u.letters[get_index(key,i)],key,i+1);}void look(trie_pointer r,char*key){	trie_pointer k;	if (k=search(r,key,0)){			printf("存在%s\n",k->u.key);	}	else{		printf("不存在%s\n",key);	}}trie_pointer del(trie_pointer r,char* key,int i){     trie_pointer t=r->u.letters[get_index(key,i)];    trie_pointer re=NULL;	if(!t){		 printf("不存在要删除的值");		 return NULL;	}	if (t->tag==data)	{		if (!strcmp(t->u.key,key))/*定位ok，即可删除*/		{			free(t->u.key);			free(t);			--r->child;/*减一*/			r->u.letters[get_index(key,i)]=NULL;/*置为NULL*/			if (r->child==1){/*只是剩下一个值了*/				for (int i = 0; i < MAX_LETTERS; ++i)					if(r->u.letters[i]!=NULL)						return r->u.letters[i];			}			return NULL;		}		else{/*是值了，但是不相同*/		 printf("不存在要删除的值");		 return NULL;		}	}re=del(t,key,i+1);	if( re!=NULL)/*返回非NULL。执行*/	{		free(r->u.letters[get_index(key,i)]);		if (r->child == 1)			return re;		else{			r->u.letters[get_index(key,i)]=re;			return NULL;		}	}return NULL;}

检索树