#include <iostream>
#include <string>
using namespace std;
#define ALPHABET_SIZE 26
typedef struct trie_node
{
int count; // 记录该节点代表的单词的个数
trie_node *children[ALPHABET_SIZE]; // 各个子节点
}*trie;
trie_node* create_trie_node()
{
trie_node* pNode = new trie_node();
pNode->count = 0;
for(int i=0; i<ALPHABET_SIZE; ++i)
pNode->children[i] = NULL;
return pNode;
}
void trie_insert(trie root, char* key)
{
trie_node* node = root;
char* p = key;
while(*p)
{
if(node->children[*p-'a'] == NULL)
{
node->children[*p-'a'] = create_trie_node();
}
node = node->children[*p-'a'];
++p;
}
node->count += 1;
}
/**
* 查询：不存在返回0，存在返回出现的次数
*/
int trie_search(trie root, char* key)
{
trie_node* node = root;
char* p = key;
while(*p && node!=NULL)
{
node = node->children[*p-'a'];
++p;
}
if(node == NULL)
return 0;
else
return node->count;
}
int main()
{
// 关键字集合
char keys[][8] = {"the", "a", "there", "answer", "any", "by", "bye", "their"};
trie root = create_trie_node();
// 创建trie树
for(int i = 0; i < 8; i++)
trie_insert(root, keys[i]);
// 检索字符串
char s[][32] = {"Present in trie", "Not present in trie"};
printf("%s --- %s\n", "the", trie_search(root, "the")>0?s[0]:s[1]);
printf("%s --- %s\n", "these", trie_search(root, "these")>0?s[0]:s[1]);
printf("%s --- %s\n", "their", trie_search(root, "their")>0?s[0]:s[1]);
printf("%s --- %s\n", "thaw", trie_search(root, "thaw")>0?s[0]:s[1]);
return 0;
}
Trie树 模板
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Xamarin XAML语言教程构建ControlTemplate控件模板 控件模板ControlTemplate...
- 题意:每几个村庄都有连通的路,而每条路都有维修费,叫你找出能联通所有村庄的路的最小维修费. 思路:最小生成树的水题...
- 模板题 . UVA--- 11183传送 还有这道 POJ 3164 点这传送 举个例子：某个图的部分图中， 1...
