概述：

Trie是个简单但实用的数据结构，是一种树形结构，是一种哈希树的变种，相邻节点间的边代表一个字符，这样树的每条分支代表一则子串，而树的叶节点则代表完整的字符串。和普通树不同的地方是，相同的字符串前缀共享同一条分支。
例如：pool,prize,preview,prepare,produce,progress这些关键词的Tire树
字典树Tire - 图1

典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

基本性质：

  • 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
  • 每个节点的所有子节点包含的字符都不相同。

应用场景：

字典数查找效率很高，时间复杂度是O(m)，m是要查找的单词中包含的字母的个数，但是会浪费大量存放空指针的存储空间，属于以空间换时间的算法。

1、串快速检索

给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。

2、单词自动完成

编辑代码时，输入字符，自动提示可能的关键字、变量或函数等信息。

3、最长公共前缀

对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为最近公共祖先问题。

4、串排序方面的应用

给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

算法题目

在力扣上也有关于Tire树的题目

208. 实现 Trie (前缀树)

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert(“apple”);

trie.search(“apple”); // 返回 true

trie.search(“app”); // 返回 false

trie.startsWith(“app”); // 返回 true

trie.insert(“app”);

trie.search(“app”); // 返回 true

说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。

保证所有输入均为非空字符串。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

实现一：

  1. class Trie {
  2. public:
  3.     /** Initialize your data structure here. */
  4.     Trie() {
  6.     }
  8.     /** Inserts a word into the trie. */
  9.     void insert(string word) {
  10.         Trie* node = this;
  12.         for(auto ch : word)
  13.         {
  14.             if(!node->next.count(ch))
  15.                 node->next[ch] = new Trie();
  16.             node = node->next[ch];
  17.         }
  19.         node->is_word = true;
  20.     }
  22.     /** Returns if the word is in the trie. */
  23.     bool search(string word) {
  24.         Trie* node = this;
  26.         for(auto &ch : word)
  27.         {
  28.             if(!node->next.count(ch))
  29.                 return false;
  30.             node = node->next[ch];
  31.         }
  33.         return node->is_word;
  34.     }
  36.     /** Returns if there is any word in the trie that starts with the given prefix. */
  37.     bool startsWith(string prefix) {
  38.         Trie* node = this;
  40.         for(auto &ch : prefix)
  41.         {
  42.             if(!node->next.count(ch))
  43.                 return false;
  44.             node = node->next[ch];
  45.         }
  47.         return true;
  48.     }
  50. private:
  51.     bool is_word = false;
  52.     map<char, Trie*> next = {};
  53. };
  55. /**
  56.  * Your Trie object will be instantiated and called as such:
  57.  * Trie* obj = new Trie();
  58.  * obj->insert(word);
  59.  * bool param_2 = obj->search(word);
  60.  * bool param_3 = obj->startsWith(prefix);
  61.  */

实现二：该实现方法只是单纯为了解题，并不是实现出Tire这个数据结构

  1. class Trie {
  2. public:
  3.     struct tireNode {
  4.         char c;
  5.         map<char, tireNode*>next;
  6.         bool endword;
  7.         tireNode(char chr, bool happyend) : c(chr), endword(happyend){}
  8.     };
  10.     map<char, tireNode*>head;
  11.     /** Initialize your data structure here. */
  12.     Trie() {
  14.     }
  16.     /** Inserts a word into the trie. */
  17.     void insert(string word) {
  18.         if(word.size() == 0)
  19.             return;
  21.         char headchar = word[0];
  22.         tireNode* tmphead = NULL;
  24.         if(head.find(headchar) == head.end())
  25.         {
  26.             head[headchar] = new tireNode(headchar, false);   
  27.         }
  29.         tmphead = head[headchar];
  31.         for(int i = 1; i < word.size(); i++)
  32.         {
  33.             if(tmphead->next.find(word[i]) == tmphead->next.end())
  34.             {
  35.                 tmphead->next[word[i]] = new tireNode(word[i], false);   
  36.             }
  38.             tmphead = tmphead->next[word[i]];
  39.         }
  41.         tmphead->endword = true;
  43.         return;
  44.     }
  46.     /** Returns if the word is in the trie. */
  47.     bool search(string word) {
  48.         if(word.size() == 0)
  49.             return true;
  51.         char headchar = word[0];
  53.         if(head.find(headchar) == head.end())
  54.             return false;
  56.         tireNode *tmphead = head[headchar];
  58.         for(int i = 1; i < word.size(); i++)
  59.         {
  60.             if(tmphead->next.find(word[i]) == tmphead->next.end())
  61.                 return false;
  62.             tmphead = tmphead->next[word[i]];
  63.         }
  65.         if(tmphead->endword)
  66.             return true;
  67.         else
  68.             return false;
  69.     }
  71.     /** Returns if there is any word in the trie that starts with the given prefix. */
  72.     bool startsWith(string prefix) {
  73.         if(prefix.size() == 0)
  74.             return true;
  76.         char headchar = prefix[0];
  78.         if(head.find(headchar) == head.end())
  79.             return false;
  81.         tireNode *tmphead = head[headchar];
  83.         for(int i = 1; i < prefix.size(); i++)
  84.         {
  85.             if(tmphead->next.find(prefix[i]) == tmphead->next.end())
  86.                 return false;
  87.             tmphead = tmphead->next[prefix[i]];
  88.         }
  90.         return true;
  91.     }
  92. };
  94. /**
  95.  * Your Trie object will be instantiated and called as such:
  96.  * Trie* obj = new Trie();
  97.  * obj->insert(word);
  98.  * bool param_2 = obj->search(word);
  99.  * bool param_3 = obj->startsWith(prefix);
  100.  */

参考资料：

https://www.cnblogs.com/Quincy/p/4898348.html