对字典中的每一个单词, 将这个单词转化为字典树的 "一根树枝", 及从根节点往下延伸, 按照顺序每个节点对应一个该单词中的字母.
例如 age,an
root
a
g n
e
建树:
- struct trie
- {
- trie *next[maxn];// 子节点数组
- bool last;// 记录此节点储存字母是否为一个单词的末尾字母
- trie()// 构造函数初始化赋值
- {
- memset(next,0,sizeof(next));
- last = false;
- }
- };
- trie *root;
- void init()// 为 root 分配空间
- {
- root = new trie;
- }
插入单词:
- void insert(char s[])
- {
- trie *p = root;
- for( int i = 0; i <(int)strlen(s); ++i )
- {
- if( !p->next[s[i]-'a'] )// 该字母对应节点不存在
- p->next[s[i]-'a'] = new trie;
- p = p->next[s[i]-'a'];// 转移, 向下继续搜索
- }
- p->last = true;// 节点末尾标记为真
- }
查询:
- bool query(char s[])
- {
- trie *p = root;
- for( int i = 0; i <(int)strlen(s); ++i )
- {
- if( !p->next[s[i]-'a'] )// 无节点对应该字母
- return false;
- p = p->next[s[i]-'a'];// 继续查找
- }
- if(p->last ) return true;// 该单词最后一个字母为树中储存单词的结尾, 并非前缀
- else return false;
- }
Trie 树
来源: http://www.bubuko.com/infodetail-3035989.html