Trie树的解释参见：
http://blog.csdn.net/hguisu/article/details/8131559
下面是用C实现的代码
头文件：
#ifndef TRIE_H
#define TRIE_H
#define TRIE_SIZE_DEF 128
const int TRIE_SIZE = TRIE_SIZE_DEF;
union NODE_TYPE
{
COMPLETED;
UNCOMPLETED;
};
typedef struct Node_
{
union NODE_TYPE type;
char ch;
struct Node_ *child[TRIE_SIZE];
}trie_t;
trie_t * trie_init(void);
void trie_add(trie_t *trie, char *word);
void trie_delete(trie_t *trie, char *word);
int trie_exists(trie_t *trie, char *word);
#endif // TRIE_H
源文件：
#include <stdio.h>
#include <stdlib.h>
#include "trie.h"
static trie_t * createNewNode(char ch)
{
trie_t *newNode = (trie_t *) malloc(sizeof(trie_t));
newNode->ch = ch;
newNode->type = UNCOMPLETED;
int i;
for (i = 0; i < TRIE_SIZE; i++)
{
newNode->child[i] = NULL;
}
return newNode;
}
static int char2int(char ch)
{
return ch - 'a';
}
trie_t * trie_init(void)
{
return createNewNode('');
}
void trie_add(trie_t *trie, char *word)
{
char ch;
while ((ch = *word++) != '\0')
{
if (trie->child[char2int(ch)] == NULL)
trie->child[char2int(ch)] = createNewNode(ch);
trie = trie->child[char2int(ch)];
}
trie->type =COMPLETED;
}
void trie_delete(trie_t *trie, char *word)
{
char ch;
while ((ch = *word++) != '\0')
{
if (trie->child[char2int(ch)] == NULL)
return;
trie = trie->child[char2int(ch)];
}
trie->type = UNCOMPLETED;
}
int trie_exists(trie_t *trie, char *word)
{
char ch;
while ((ch = *word++) != '\0')
{
if (trie->child[char2int(ch)] == NULL)
return 0;
trie = trie->child[char2int(ch)];
}
return (trie->tpye == COMPLETED) ? 1 : 0;
}
