Trie树的简单介绍和应用

简单介绍http://www.cnblogs.com/cherish_yimi/archive/2009/10/12/1581666.html
应用http://www.cnblogs.com/cherish_yimi/archive/2009/10/12/1581795.html
  1 #include <iostream>
  2 #include <string>
  3 #include <vector>
  4 #include <cstdlib>
  5 #include <map>
  6 #include <list>
  7 #include <algorithm>
  8 #include <cstring>
  9 #include <string.h>
 10 
 11 using namespace std;
 12 
 13 const int branchNum = 26; //声明常量
 14 int i;
 15 
 16 struct Trie_node {
 17     bool isStr; //记录此处是否构成一个串。
 18     Trie_node *next[branchNum]; //指向各个子树的指针,下标0-25代表26字符
 19     Trie_node() :
 20             isStr(false) {
 21         for (int i = 0; i < branchNum; i++)
 22             next[i] = NULL;
 23     }
 24 };
 25 
 26 class Trie {
 27 public:
 28     Trie();
 29     void insert(const char* word);
 30     bool search(char* word);
 31     void deleteTrie(Trie_node *root);
 32     bool pre_char(bool judge, Trie_node* top);
 33 public:
 34     Trie_node* root;
 35 };
 36 
 37 Trie::Trie() {
 38     root = new Trie_node();
 39 }
 40 
 41 void Trie::insert(const char* word) {
 42     Trie_node *location = root;
 43     while (*word) {
 44         if (location->next[*word - 'a'] == NULL) //不存在则建立
 45         {
 46             Trie_node *tmp = new Trie_node();
 47             location->next[*word - 'a'] = tmp;
 48         }
 49         location = location->next[*word - 'a']; //每插入一步，相当于有一个新串经过，指针要向下移动
 50         word++;
 51     }
 52     location->isStr = true; //到达尾部,标记一个串
 53 }
 54 
 55 bool Trie::search(char *word) {
 56     Trie_node *location = root;
 57     while (*word && location) {
 58         location = location->next[*word - 'a'];
 59         word++;
 60     }
 61     return (location != NULL && location->isStr);
 62 }
 63 
 64 void Trie::deleteTrie(Trie_node *root) {
 65     for (i = 0; i < branchNum; i++) {
 66         if (root->next[i] != NULL) {
 67             deleteTrie(root->next[i]);
 68         }
 69     }
 70     delete root;
 71 }
 72 
 73 bool Trie::pre_char(bool judge, Trie_node* top) {
 74     bool tmpjud, res;
 75     res = false;
 76     if (top->isStr && judge)
 77         return true;
 78     tmpjud = judge || top->isStr;
 79     for (int i = 0; i < branchNum; i++) {
 80         if (top->next[i] != NULL)
 81             res = res || pre_char(tmpjud, top->next[i]);
 82     }
 83     return res;
 84 }
 85 
 86 int main() //简单测试
 87 {
 88     Trie t;
 89     t.insert("a");
 90     t.insert("abandon");
 91     char * c = "abandoned";
 92     t.insert(c);
 93     t.insert("abashed");
 94     if (t.search("abashed"))
 95         cout << "true\n";
 96     if (t.pre_char(false, t.root))
 97         cout << "yes\n";
 98     else
 99         cout << "no\n";
100     return 0;
101 }