CareerCup Trie Prefix Tree

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;
}

CareerCup Trie Prefix Tree

原文：http://blog.csdn.net/taoqick/article/details/19841165