c++实现字典树

昵称10504424 2013-12-30
展开全文
  1 #ifndef _TRIE_TREE_H_
  2 #define _TRIE_TREE_H_
  3 
  4 #include <vector>
  5 #include <utility>
  6 #include <memory>
  7 #include <string>
  8 #include <map>
  9 #include <iostream>
 10 
 11 namespace zstd
 12 {
 13     class trie_tree
 14     {
 15     private:
 16         struct trie_node
 17         {
 18             char data;
 19             bool is_a_word;
 20             std::map<char, std::shared_ptr<trie_node>> map_childs;
 21         };
 22     private:
 23         trie_node *data;
 24     private:
 25         trie_node* get_root()
 26         {
 27             return data;
 28         }
 29         void _print_all_word(const std::string& prefix, std::shared_ptr<trie_node> sp, 
 30             const std::string& real_prefix);
 31         void __print_all_word(std::shared_ptr<trie_node> sp, std::string& word, const std::string& prefix);
 32         void _print_tree(std::shared_ptr<trie_node> sp, std::string word);
 33         bool _insert(const std::string& word, std::shared_ptr<trie_node> sp);
 34         bool _is_existed(const std::string& word, std::shared_ptr<trie_node> sp);
 35     public:
 36         void print_all_word(const std::string& prefix);
 37         void print_tree();
 38         bool insert(const std::string& word);
 39         bool is_existed(const std::string& word);
 40 
 41         trie_tree()
 42         {
 43             data = new trie_node;
 44             data->is_a_word = false;
 45             data->map_childs.clear();
 46         }
 47         ~trie_tree()
 48         {
 49             if (data)
 50             {
 51                 data->map_childs.clear();
 52                 delete data;
 53             }
 54         }
 55         trie_tree(const trie_tree&) = delete;
 56         trie_tree& operator = (const trie_tree&) = delete;
 57     };// end of trie_tree
 58 
 59     bool trie_tree::is_existed(const std::string& word)
 60     {
 61         if(word.size() == 0)
 62             return false;
 63         auto root = get_root();
 64         auto res = root->map_childs.find(word[0]);
 65         if(res == root->map_childs.end())//not found
 66             return false;
 67         else
 68         {
 69             return _is_existed(word, res->second);
 70         }
 71     }
 72     bool trie_tree::_is_existed(const std::string& word, std::shared_ptr<trie_node> sp)
 73     {
 74         if(word.size() == 1)
 75             return sp->is_a_word;
 76         char ch = word[1];
 77         auto res = sp->map_childs.find(ch);
 78         if(res == sp->map_childs.end())//not found
 79             return false;
 80         else
 81         {
 82             std::string tmp_word(word.substr(1));
 83             return _is_existed(tmp_word, res->second);
 84         }
 85     }
 86     bool trie_tree::insert(const std::string& word)
 87     {
 88         if(is_existed(word))
 89             return true;
 90         if(word.size() == 0)
 91             return false;
 92         char ch = word[0];
 93         auto root = get_root();
 94         auto res = root->map_childs.find(ch);//res = pair<const char, std::shared_ptr<trie_node>>
 95         if(res != root->map_childs.end())
 96         {
 97             std::string tmp_word(word.substr(1));
 98             return _insert(tmp_word, res->second);
 99         }
100         else
101         {
102             auto new_sp = std::make_shared<trie_node>();
103             new_sp->data = ch;
104             if(word.size() == 1)
105                 new_sp->is_a_word = true;
106             else
107                 new_sp->is_a_word = false;
108             root->map_childs[ch] = new_sp;
109             std::string tmp_word(word.substr(1));
110             return _insert(tmp_word, new_sp);
111         }
112     }
113     bool trie_tree::_insert(const std::string& word, std::shared_ptr<trie_node> sp) 
114     {
115         if(word.size() == 0)
116         {
117             sp->is_a_word = true;
118             return true;
119         }
120 
121         char ch = word[0];
122         auto res = sp->map_childs.find(ch);
123         if(res != sp->map_childs.end())
124         {
125             std::string tmp_word(word.substr(1));
126             return _insert(tmp_word, res->second);
127         }
128         else
129         {
130             auto new_sp = std::make_shared<trie_node>();
131             new_sp->data = ch;
132             if(word.size() == 1)
133                 new_sp->is_a_word = true;
134             else
135                 new_sp->is_a_word = false;
136             sp->map_childs[ch] = new_sp;
137             std::string tmp_word(word.substr(1));
138             return _insert(tmp_word, new_sp); 
139         }
140     }
141     void trie_tree::print_tree()
142     {
143         auto root = get_root();
144         if(root == NULL)
145             std::cerr<<"the trie_tree is empty!"<<std::endl;
146         for(auto cit = root->map_childs.cbegin(); cit != root->map_childs.cend(); ++cit)
147         {
148             _print_tree(cit->second, std::string());
149         }
150     }
151     void trie_tree::_print_tree(std::shared_ptr<trie_node> sp, std::string word)
152     {
153         word += sp->data;
154         if(sp->is_a_word)
155             std::cout<<word<<std::endl;
156         std::string tmp_word;
157         for(auto cit = sp->map_childs.cbegin(); cit != sp->map_childs.cend(); ++cit)
158         {
159             tmp_word = word;
160             _print_tree(cit->second, tmp_word);
161         }
162     }
163     void trie_tree::print_all_word(const std::string& prefix)
164     {
165         auto root = get_root();
166         if(root == NULL)
167             std::cerr<<"the trie_tree is empty!"<<std::endl;
168         if(prefix.size() == 0)
169         {
170             std::cout<<"prefix is empty!"<<std::endl;
171             return ;
172         }
173         char ch = prefix[0];
174         auto res = root->map_childs.find(ch);
175         if(res == root->map_childs.end())
176         {
177             std::cout<<"no such prefix!"<<std::endl;
178             return ;
179         }
180         else
181         {
182             _print_all_word(prefix, res->second, prefix);
183         }
184     }
185     void trie_tree::_print_all_word(const std::string& prefix, std::shared_ptr<trie_node> sp, 
186         const std::string& real_prefix)
187     {
188         if(prefix.size() == 1)
189         {
190             for(auto cit = sp->map_childs.cbegin(); cit != sp->map_childs.cend(); ++cit)
191             {
192                 __print_all_word(cit->second, std::string(), real_prefix);
193             }
194         }
195         else
196         {
197             char ch = prefix[1];
198             auto res = sp->map_childs.find(ch);
199             if(res == sp->map_childs.end())
200             {
201                 std::cout<<"no such prefix!"<<std::endl;
202                 return ;
203             }
204             else
205             {
206                 std::string tmp_word(prefix.substr(1));
207                 _print_all_word(tmp_word, res->second, real_prefix);
208             }
209         }
210     }
211     void trie_tree::__print_all_word(std::shared_ptr<trie_node> sp, std::string& word, const std::string& prefix)
212     {
213         word += sp->data;
214         if(sp->is_a_word)
215             std::cout<<prefix + word<<std::endl;
216         std::string tmp_word;
217         for(auto cit = sp->map_childs.cbegin(); cit != sp->map_childs.cend(); ++cit)
218         {
219             tmp_word = word;
220             __print_all_word(cit->second, tmp_word, prefix);
221         }
222     }
223 }//end of namespace zstd 
224 
225 #endif