字符串前缀问题：Trie树
Trie树主要是解决字符串前缀的搜索问题，例如最短前缀、某个前缀所含的字符串数等等。这是一种为解决一类字符串问题的树，与用于查找的树结构不同的是，Trie树需要在树的边上保存数据，这样组织一棵Trie树就需要有边节点和顶点节点。
一个Trie树是多叉树，根结点为空，树的边表示一个字母，顶点保存字符串状态数据，最简单的字符串的状态就是到此顶点是否有字符串完结。例如给出两个单词car与cartoon。从根结点开始，插入一个新结点，根结点到这个结点的边表示字母c，然后再新建结点，由上一个结点到这个新结点的边为a，然后再新增一个结点，由上一个结点到这个结点的边为字母r，由于单词car后续已经结束，所以这个新结点的字符串状态应表示为"有字符串完结"，对于cartoon，由于前3个字母car已经可以沿着树的边找到，所以不需要再新增结点，只需要对后4个字母新增结点并设置相应的边即可。
基本的Trie树包括插入（建树）和搜索。这类问题一般是将一系列的数据逐个插入到树中，建立起这一组数据的前缀信息，然后查询或者搜索相应的前缀。
具体而言，使用这样的结构作为边和顶点：
struct EdgeNode
{
char letter;
int ToVertex;
};
struct VertexNode
{
std::vector<EdgeNode> childs;
bool EndHere;
int tollStation;
};
std::vector<VertexNode> Tree;
这里的VertexNode使用vector<EdgeNode> 表示顶点所连的边，Endhere表示是否有字符串在这里终止，tollStation（收费站）来记录有多少个字符串经过了这个结点。Edge保存了它所表示的字母letter和它指向的结点编号ToVertex。
整个Trie树使用std::vector<VertexNode> Tree表示，首先将一个空VertexNode结点插入到Tree中，作为树根Tree[0]。插入操作为：对于待插入字符串的每一个字符，首先将它经过的结点的tollStation加一，然后再检查它是否存在相应路径能对应到这个字符，如果存在就将树继续向之后的顶点进行检查，如果顶点的所有边都不存在相应字符，则新建一个顶点，新建一条边指向这个新顶点，使这条边的字符是字符串上相应位置的字符。直到字符串读到末尾，将边的“EndHere”状态置为1.
void insertWord(char* msg)
{
int vid = Tree.size();
// start to root
int currId = 0;
for(int i=0;msg[i];i++)
{
bool needMakeNewNode = true;
Tree[currId].tollStation ++;
VertexNode currVertexNode = Tree[currId];
// all edge of this vertex
for(int ei = 0;
needMakeNewNode && ei<currVertexNode.childs.size();
ei++)
{
// if the letter of this edge == msg[i]
// move vertex to this edge pointing.
if(msg[i] == currVertexNode.childs[ei].letter)
{
currId = currVertexNode.childs[ei].ToVertex;
needMakeNewNode = false;
break;
}
}
// if no letters of edges equal the msg[i]
// then, make a new edge and new vertex
if(needMakeNewNode)
{
EdgeNode e;
e.letter = msg[i];
e.ToVertex = vid;
Tree[currId].childs.push_back(e);
VertexNode v;
v.EndHere = false;
v.tollStation = 0;
Tree.push_back(v);
currId = vid;
vid++;
}
}
// msg read over, set end = true;
Tree[currId].tollStation ++;
Tree[currId].EndHere = true;
}另一项操作为搜索，给出一个字符串，判断以它作为前缀的单词数量。有些情况下要考虑这个前缀并不存在树中。如果给出的前缀字符串能在树中找到，我们输出它的tollStation值即可，如果不在树中则输出0.
int search(char* msg)
{
int currId = 0;
int InTree = true;
int ei;
for(int i=0; InTree && msg[i];i++)
{
VertexNode currVertexNode = Tree[currId];
for(ei = 0;
ei<currVertexNode.childs.size();
ei++)
{
EdgeNode e = currVertexNode.childs[ei];
if(e.letter==msg[i])
{
currId = e.ToVertex;
break;
}
}
if(ei==currVertexNode.childs.size())
{
InTree = false;
}
}
if(InTree)
{
return Tree[currId].tollStation;
}
else
{
return 0;
}
}
与Trie树相关的两题：