Result is “cat”
------------------------------------------------------------------------------
#include <stdio.h> #include <algorithm> #include <string> #include <iostream> using namespace std; const int sonnum=26,base=‘a‘; class Trie { public: int num;//to remember how many word can reach here,that is to say,prefix bool terminal;//If terminal==true ,the current point has no following point Trie *son[sonnum];//the following point Trie(bool terminal = true, int num = 0):terminal(terminal), num(num){ for (int i = 0; i < sonnum; ++i) son[i] = NULL; } }; Trie* BuildTrie()// create a new node { Trie *root=new Trie(true, 0); root->terminal = false; return root; } void Insert(Trie* root, string& s)// insert a new word to Trie tree { for(int i=0; i<s.length(); ++i) { if(root->son[s[i]-base] == NULL) root->son[s[i]-base]=new Trie(); else root->son[s[i]-base]->num++; root->terminal = false; root=root->son[s[i]-base]; } root->terminal=true; } void Delete(Trie *root)// delete the whole tree { if(root!=NULL) { for(int i=0;i<sonnum;++i) if(root->son[i]!=NULL) Delete(root->son[i]); delete root; root=NULL; } } Trie* Find(Trie *root,string& s)//trie to find the current word { for(int i=0;i<s.length();++i) if(root->son[s[i]-base]!=NULL) root=root->son[s[i]-base]; else return NULL; return root; } void ListAll(Trie *root,string& cur) { if (root->terminal) { cout << cur; return; } else { for (int i = 0; i < sonnum; ++i) if (root->son[i]) { string tmp = "a"; tmp[0] += i; string next = cur + tmp; ListAll(root->son[i], next); } } } int main() { Trie* trie = BuildTrie(); string str[] = {"abc", "ab", "ade", "ace"}; for (int i = 0; i < 4; ++i) Insert(trie, str[i]); string s = "a"; Trie *searchWord = Find(trie, s); ListAll(searchWord, s); return 0; }
原文:http://blog.csdn.net/taoqick/article/details/19841165