trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。
前缀树
百科内容来自于：
应用
实现
trie树实际上是一个DFA，通常用转移矩阵表示。行表示状态，列表示输入字符，(行, 列)位置表示转移状态。这种方式的查询效率很高，但由于稀疏的现象严重，空间利用效率很低。也可以采用压缩的存储方式即链表来表示状态转移，但由于要线性查询，会造成效率低下。
于是人们提出了下面两种结构。
三数组Trie
三数组Trie(Tripple-Array Trie)结构包括三个数组：base,next和check.
二数组Trie
二数组Trie(Double-Array Trie)包含base和check两个数组。base数组的每个元素表示一个Trie节点，即一个状态；check数组表示某个状态的前驱状态。
实例
这是一个用于词频统计的程序范例，因使用了getline(3)，所以需要glibc才能链接成功，没有glibc的话可以自行改写。代码由“JohnBull”捐献，遵从GPL版权声明。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TREE_WIDTH 256
#define WORDLENMAX 128
struct trie_node_st {
int count;
struct trie_node_st *next[TREE_WIDTH];
};
static struct trie_node_st root={0, {NULL}};
static char *spaces=" \t\n/.\"\'()";
static int
insert(const char *word)
{
int i;
struct trie_node_st *curr, *newnode;
if (word[0]=='\0') {
return 0;
}
curr = &root;
for (i=0; ; ++i) {
if (word[i] == '\0') {
break;
}
if (curr->next[ word[i] ] == NULL) {
newnode=(struct trie_node_st*)malloc(sizeof(struct trie_node_st));
memset(newnode, 0, sizeof(struct trie_node_st));
curr->next[ word[i] ] = newnode;
}
curr = curr->next[ word[i] ];
}
curr->count ++;
return 0;
}
static void
printword(const char *str, int n)
{
printf("%s\t%d\n", str, n);
}
static int
do_travel(struct trie_node_st *rootp)
{
static char worddump[WORDLENMAX+1];
static int pos=0;
int i;
if (rootp == NULL) {
return 0;
}
if (rootp->count) {
worddump[pos]='\0';
printword(worddump, rootp->count);
}
for (i=0;i<TREE_WIDTH;++i) {
worddump[pos++]=i;
do_travel(rootp->next[i]);
pos--;
}
return 0;
}
int
main(void)
{
char *linebuf=NULL, *line, *word;
size_t bufsize=0;
int ret;
while (1) {
ret=getline(&linebuf, &bufsize, stdin);
if (ret==-1) {
break;
}
line=linebuf;
while (1) {
word = strsep(&line, spaces);
if (word==NULL) {
break;
}
if (word[0]=='\0') {
continue;
}
insert(word);
}
}
/* free(linebuf); */
do_travel(&root);
exit(0);
}
$firstVoiceSent
- 来自原声例句