先看个例子，存储字符串abc、ab、abm、abcde、pm可以利用以下方式存储
上边就是Trie树的基本原理：利用字串的公共前缀来节省存储空间，最大限度的减少无谓的字串比较。
应用
Trie树又称单词查找树，典型的应用是用于统计，排序和保存大量的字符串（不仅用于字符串），所以经常被搜索引擎系统用于文本词频的统计。
设计
trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
结点可以设计成这样：
class trieNode
{
public:
trieNode() : terminableSize(0), nodeSize(0) { for(int i = 0; i < Size; ++i) children[i] = NULL; }
~trieNode()
{
for(int i = 0; i < Size; ++i)
{
delete children[i];
children[i] = NULL;
}
}
public:
int terminableSize; //存储以此结点为结尾的字串的个数
int nodeSize; //记录此结点孩子的个数
trieNode* children[Size]; //该数组记录指向孩子的指针
};
树设计成这样：
template
class trie
{
public:
typedef trieNode Node;
typedef trieNode* pNode;
trie() : root(new Node) {}
template
void insert(Iterator beg, Iterator end);
void insert(const char *str);
template
bool find(Iterator beg, Iterator end);
bool find(const char *str);
template
bool downNodeAlone(Iterator beg);
template
bool erase(Iterator beg, Iterator end);
bool erase(const char *str);
int sizeAll(pNode);
int sizeNoneRedundant(pNode);
public:
pNode root;
private:
Type index;
};
index字串索引利用（char % 26） 得到，这样'a' % 26 = 19, 'b' % 26 = 20
实现
插入
以插入abc、ab为例
删除
删除结点，首先查找此字串是否在树中，如果在树中，再查找此结点以下的部分是不是都是只有一个孩子，并且每个结点只有叶子结点是结束结点，如果不是继续往下重复上边过程。
统计字串个数
分两种情况
计算重复的字串的个数：是结束结点，此时加的是terminabel的个数
计算不重复的字串的个数：是结束结点，此时加的是1(当terminabel>0）的个数
#include
#include
using namespace std;
template
class trieNode
{
public:
trieNode() : terminableSize(0), nodeSize(0) { for(int i = 0; i < Size; ++i) children[i] = NULL; }
~trieNode()
{
for(int i = 0; i < Size; ++i)
{
delete children[i];
children[i] = NULL;
}
}
public:
int terminableSize;
int nodeSize;
trieNode* children[Size];
};
template
class trie
{
public:
typedef trieNode Node;
typedef trieNode* pNode;
trie() : root(new Node) {}
template
void insert(Iterator beg, Iterator end);
void insert(const char *str);
template
bool find(Iterator beg, Iterator end);
bool find(const char *str);
template
bool downNodeAlone(Iterator beg);
template
bool erase(Iterator beg, Iterator end);
bool erase(const char *str);
int sizeAll(pNode);
int sizeNoneRedundant(pNode);
public:
pNode root;
private:
Type index;
};
template
template
void trie::insert(Iterator beg, Iterator end)
{
pNode cur = root;
pNode pre;
for(; beg != end; ++beg)
{
if(!cur->children[index[*beg]])
{
cur->children[index[*beg]] = new(Node);
++cur->nodeSize;
}
pre = cur;
cur = cur->children[index[*beg]];