字典树Trie和三叉搜索树TernaryTree的学习总结

Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。

三叉搜索树是一种特殊的Trie树的数据结构，它是数字搜索树和二叉搜索树的混合体。它既有数字搜索树效率优点，又有二叉搜索树空间优点。

在接下来的博文中，我们将介绍Trie树和三叉搜索树的定义，实现和优缺点。

Trie树的定义

Trie树与二叉搜索树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀（prefix），也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie树可以利用字符串的公共前缀来节约存储空间，如下图所示，该Trie树用11个节点保存了8个字符串tea，ted，ten，to，A，i，in，inn。

图1Trie树

我们注意到Trie树中，字符串tea，ted和ten的相同的前缀（prefix）为“te”，如果我们要存储的字符串大部分都具有相同的前缀（prefix），那么该Trie树结构可以节省大量内存空间，因为Trie树中每个单词都是通过character by character方法进行存储，所以具有相同前缀单词是共享前缀节点的。

当然，如果Trie树中存在大量字符串，并且这些字符串基本上没有公共前缀，那么相应的Trie树将非常消耗内存空间，Trie的缺点是空指针耗费内存空间。

Trie树的基本性质可以归纳为：

（1）根节点不包含字符，除根节点外的每个节点只包含一个字符。

（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。

（3）每个节点的所有子节点包含的字符串不相同。