Trie树

在hihocoder.com有一个Trie树的问题，两个月前自己曾经AC过，可两个月后，发现自己居然用了将近两个小时才编码调试正确，瞬间发现自己当初在这一问题上，没有足够用心的思考过，看来有必要来整理整理。

嗯，废话就不过说了，，

trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。

这是一个保存了 8 个键的 trie 结构，"A", "to", "tea", "ted", "ten", "i", "in", and "inn".

trie树大致就是这样。

我在实现的时候，针对具体问题，树中的节点Node的结构是这样设计的：

 1 struct Node{
 2     int count;
 3     Node *table[26];
 4     Node() : count(1)
 5     {
 6         for (int i = 0; i < 26; ++i)
 7         {
 8             table[i] = NULL;
 9         }
10     }
11 };

这里没有去存特定的字符char,而是把它与table数组对应起来，

其中两个关键的操作是：

 1 void insert(Node *root, string s)
 2 {
 3     Node* tmp = root;
 4     for (int i = 0; i<s.size(); ++i)
 5     {
 6         if (tmp->table[s[i] - 'a'] != NULL)
 7         {
 8             tmp->table[s[i] - 'a']->count += 1;
 9             tmp = tmp->table[s[i] - 'a'];
10             continue;
11         }
12         tmp->table[s[i] - 'a'] = new Node;
13         tmp = tmp->table[s[i] - 'a'];
14     }
15 }

 1 int find(Node* root, string s)
 2 {
 3     Node* tmp = root; int i;
 4     for ( i = 0; i < s.size(); ++i)
 5     {
 6         if (tmp->table[s[i] - 'a'] == NULL)
 7         {
 8             return 0;
 9         }
10         tmp = tmp->table[s[i] - 'a'];
11     }
12     return tmp->count;
13 }

一开始一直没有对，不是Crash就是查询错误，后来发现，Crash的原因是使用未初始化的指针。查询错误，则是代码内查询逻辑有Bug。

写代码真得思维逻辑要清晰，不然几乎是百分之一百的出错！