前言

leetcode在3.28的每日一题：820.单词的压缩编码中有一种解法涉及到了字典树这种数据结构，我也是第一次接触到这种数据结构，因此也想借此机会学习和总结下字典树这种数据结构

概念

字典树又称单词查找树，Trie树，是一种树形结构，也是一种哈希树的变种。是一种用于快速检索的多叉树结构。它的优点是可以最大限度地减少无谓的字符串比较，查询效率比哈希表高。字典树的核心思想是空间换时间，字典树利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。但字典树的核心思想也正正是它的缺点，字典树的内存消耗非常大。字典树常用于字符串检索，词频统计，搜索引擎的热门查询等地方

基本特性

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

字典树示意图

具体实现

(假设字典树存储英文单词并且单词均由小写字母组成）
字典树和其他数据结构一样，支持查找、插入以及删除等操作。字典树和其他查找树一样也是由各节点链接组成的数据结构，这些节点可以为空，也可以指向其他节点。节点实现如下：

struct TreeNode
{
    bool isLast;
    int passNum;
    vector<TreeNode*> sonNodes;
    TreeNode() : isLast(false),
                 sonNodes(26, NULL),
                 passNum(0)
    {
    };
}

节点只存储了两个变量，isLast是表示节点是不是一个字符串的结束，而sonNodes也不用多说，字如其名是用于存储子节点的一个数组。这里也可以看出字典树的缺点，每个节点都需要申请一定的空间，并且所有的非空的节点都需要申请这么多的空间。这样边导致了字典树有较高的空间复杂度。
字典树由一个根节点引出所有界点，且根部不存储任何的属性。从根节点到某一节点，路径上经过的字符链接起来便是该节点存储起来的字符串。

查找操作

查找操作比较简单，从根节点开始查找单词的第一个字符，若能单词的第一个字符若能找到，则从查找到的节点开始检索下一层是否能找到第二个字符，以此类推直至找到最后一个字符。若中途只能查找到空节点或最后节点的isLast为false，则查找失败，否则查找成功。具体代码如下

bool find(string word)
{
    TreeNode* node = root;
    for(int i = 0; i < word.size(); i++)
    {
        int pos = word[i] - 'a';
        if(node->sonNodes[pos] == NULL)
        {
                return false;
        }
        node = node->sonNodes[pos];
    }
    if(!node->isLast) return false;
    return true;
}

插入操作

插入操作和查找类似，从根节点开始向下检索要插入单词的字符，若遇到空节点，则生成一个新节点。以此类推，直至单词最后一个字符，并将最后一个字符的isLast标记为true;

void insert(string word）
{
    TreeNode* node = root;
    for(int i = 0; i < word.size(); i++)
    {
        int pos = word[i] - 'a';
        if(node->sonNodes[pos] == NULL)
        {
            node->sonNodes[pos] = new TreeNode();
        }
        node = node->sonNodes[pos];
        node->passNum++;
    }
    node->isLast = true;
}

删除操作

删除操作与查找操作类似，从根节点向下逐个检索单词字符，若检索到该节点为空或passNum自减后为0，则将其删除。

void delete(string word)
{
    TreeNode* node = root;
    for(int i = 0; i < word.size(); i++)
    {
        int pos = word[i] - ' a';
        if(node->sonNodes[pos] == NULL)
        {
              return;
        }
        node->passNum--;
        if(node->passNum == 0)
        {
              delete node->sonNode[pos];
              node->sonNode = NULL;
        }
        node = node->sonNode[pos];
    }
    node->isLast = false;
}

字典树（Trie树）