Trie树 单词查找树 键树

转自：http://zh.wikipedia.org/wiki/%E7%B4%A2%E5%9B%9E%E6%A0%91

Trie ，又称单词查找树 或键树 ，是一种树 形结构，是一种哈希 树的变种。典型应用是用于统计和排序大量的字符串 （但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表 高。

性质

它有3个基本性质：

1. 根节点 不包含字符 ，除根节点外每一个节点都只包含一个字符 。
2. 从根节点 到某一节点 ，路径 上经过的字符 连接起来，为该节点 对应的字符串 。
3. 每个节点 的所有子节点 包含的字符 都不相同。

图示

这是一个Trie结构的例子：

在这个Trie结构中，保存了A、to、tea、ted、ten、i、in、inn这8个字符串，仅占用8个字节 （不包括指针 占用的空间）。

实例

这是一个用于词频统计的程序范例，因使用了getline(3)，所以需要glibc 才能链接成功，没有glibc 的话可以自行改写。代码由User: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 (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;
                }
                if (word[i] == '\0') {
                        break;
                }
                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);
}