字典树——Trie树，又称为前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。
根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符互不相同。
通常在实现的时候，会在结点结构中设置一个标志，用来标记该节点处是否构成一个单词（关键字）。
可以看出，Trie树的关键字一般都是字符串，而且Trie树把每个关键字保存在一条路径上，而不是一个节点中。另外，有两个公共前缀的关键字，在Trie树种前缀部分的路径相同。所以Trie又称为前缀树。