什么是trie树（字典树）？
trie树是一种用于快速检索的多叉树结构。和二叉查找树不同，在trie树中，每个结点上并非存储一个元素。
trie树把要查找的关键词看作一个字符序列。并根据构成关键词字符的先后顺序构造用于检索的树结构。在trie树上进行检索类似于查阅英语词典。 一棵m度的trie树或者为空，或者由m
棵m度的trie树构成。 例如，电子英文词典，为了方便用户快速检索英语单词，可以建立一棵trie树。例如词典由下面的单词构成：a、b、c、aa、ab、ac、ba、ca、aba、abc、baa
bab、bac、cab、abba、baba、caba、abaca、caaba.
下图形象的展示下trie树：
例如在上面图中的trie树中查找单词 aba的流程：
(1)在trie树上进行检索总是始于根结点。
(2)取得要查找关键词的第一个字母（例如 a ），并根据该字母选择对应的子树并转到该子树继续进行检索。
(3)在相应的子树上，取得要查找关键词的第二个字母（例如 b），并进一步选择对应的子树进行检索。
(4) ...
(5)在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。
我的实现代码如下：
#include <iostream>
#include <cstdlib>
#include <cstdio> #define null NULL
const int num_chars = ; /*普通的树结点*/
template <typename Entry>
class tree_node
{
public:
Entry data;
tree_node* first_child;
tree_node* next_sibling;
tree_node():first_child(null),next_sibling(null){}
tree_node(const Entry& x):data(x),first_child(null),next_sibling(null){}
}; /*trie树,是一种用于快速检索的多叉树结构。*/ //trie树的实现
class trie
{
protected:
class trie_node //定义trie树的结点
{
char* data;
trie_node* branch[num_chars]; //常量num_chars = 26
trie_node();
};
trie_node* root; //根节点
public:
trie(); //无参数构造函数
trie(trie& tr); //复制构造函数
virtual ~trie(); //析构函数
int trie_search(const char* word,char* entry) const; //查找操作
int insert(const char* word,const char* entry); //插入操作
int remove(const char* word,char* entry); //删除操作 }; //trie_node的构造函数
trie::trie_node::trie_node()
{
data = null;
for(int i=;i<num_chars;i++)
branch[i] = null;
} //trie的构造函数
trie::trie()
{
root = null;
} //trie的检索,查找在某个字符路径结点上的存放的值，并将其放在entry中。比如找对应"abc"的结点上的值并且存放在entry中。
int trie::trie_search(const char* word,char* entry) const
{
int position = ;
char char_code;
trie_node* loaction = root;
while(location != null && *word != null)
{
if(*word >= 'A' && *word < 'Z') char_code = *word - 'A';
else if(*word >= 'a' && *word <= 'z') char_code = *word - 'a';
else return ;
location = location->branch[char_code];
position++;
word++;
}
if(location != null && location->data != null)
{
strcpy(entry,location->data);
return ;
}
else return ;
} //插入操作,此时是往指定的字符串的结点上存放指定的字符串。比如在"abc"位置上防"jeaven"。
int trie::insert(const char* word,const char* entry)
{
int result = ;
int position = ;
if(root == NULL) root = new tire_node();
char char_code;
tire_node* location = root;
while(location != null && *word != null)
{
if(*word >= 'a' && *word <= 'z') char_code = *word - 'a';
else if(*word >= 'A' && *word <= 'Z') char_code = *word - 'A';
else return ;
if(location->branch[char_code] == null)
location->branch[char_code] = new trie_node();
location = location->branch[char_code];
position++;
word++;
} if(location->branch[char_code] != null) result = ;
else
{
location->data = new char[strlen(entry)+];
strcpy(location->data,entry);
}
return result;
} //删除操作，删除在某字符串路径上的结点存放的值，并且将其放到entry中
int trie::remove(const char* word,char* entry)
{
if(root == null) return ;
trie_node* cur = root;
char char_code;
while(*word != null)
{
if(*word >= 'a' && *word <= 'z') char_code = *word - 'a';
else if(*word >= 'A' && *word <= 'Z') char_code = *word - 'A';
else return ;
if(cur->branch[char_code] != null) cur = cur->branch[char_code];
}
*entry = cur->data;
delete cur;
return ;
}