字典树 Trie树

什么是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

上一篇：【割点】【割边】tarjan

下一篇：【转】二分图的一大坨定理

---

模板 trie树