什么是Trie树？
形如
其中从根节点到红色节点的路径上的字母所连成的字符串即为一个Trie树上所存的字符串。
比如，这个trie树上有ab，abc，bd，dda这些字符串。
至于怎么构建和查找或添加。
简单的一批，看代码就能看懂。
不过Trie树所占的空间很大，有一些优化，暂时还没学。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdio> 4 5 using namespace std; 6 7 #define idx(x) x 'a' 8 const int maxn = 10000; 9 struct trie 10 tree[maxn]; 14 15 int nex, T;//nex表示tree中下标 16 char str[maxn]; 17 18 void Insert(char *s)//插入 19 27 tree[rt].val = 1; 28 } 29 30 bool Find(char *s)//查找 31 39 if(tree[rt].val) return 1; 40 return 0; 41 } 42 43 int main() 44 51 while(scanf("%s", str)) 52 if(Find(str)) printf("Yes\n"); 53 else printf("No\n"); 54 return 0; 55 }View Code
上一篇：NOIP2013D1T3货车运输（最大生成树+倍增lca）
下一篇：Hadoop完全分布式集群安装
模板 trie树
