《征服数据结构》字典树(Trie树)

摘要：

1，字典树的介绍

2，字典树的插入

3，字典树的查询

4，字典树排序

5，字典树的删除

6，字典树的用途

1，字典树的介绍

字典树又称 Trie 树 ，单词查找树，前缀树，也是一种树状结构，就是在查询目标时，像字典一样按照一定顺序和步骤访问树的节点，它主要利用字符串的公共前缀来减少查询次数，最大限度地减少字符串比较。

比如要查找一个字符串是否存在，或者是否存在 xxx 开头的字符串。假设字符串只包含小写字母，那么我们可以把字典树看作是一棵每个节点最多有 26 个子节点的树。

字典树中根节点是不存储数据的，除了根节点以外，每个节点代表一个字符，从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

比如有 wang， yi ，bo ， yibo 等字符串，只需要把它添加到字典树中，然后在每个字符串末尾标记为一个完整的字符串即可，如图下图所示。

比如查找字符串 wan ，因为字符串的最后一个字符 n 在字典树中没有标记，所以 wan 不是一个完整的字符串。又比如查找字符串 yi ，因为字符串的最后一个字符 i 在字典树中标记了，所以 yi 是一个完整的字符串。

字典树中每个节点需要两个变量，一个是记录子节点的数组，一个是标记从根节点到当前节点是否是一个完整的字符串。

Java 代码：

// 节点类。
class TrieNode {
    boolean isEnd;  // 标记是否为完整字符串。
    TrieNode[] children; // 子节点数组。
 
    public TrieNode() {
        isEnd = false;// 默认不是完整字符串。
        // 默认每个节点最多有26个子节点，还可以使用map。
        children = new TrieNode[26];
    }
}

C++ 代码：

// 节点类。
class TrieNode {
public:
    bool isEnd = false;  // 标记是否为完整字符串。
    TrieNode *children[26];// 子节点数组。
};

这里我们规定只查询小写字母，如果包含其他字母的话可以使用 Map 。

Map map = new HashMap<>();// java
unordered_map<char, TrieNode> mp;// c++

字典树的 3 个基本性质：

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

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

3，每个节点的所有子节点包含的字符都不相同。

2，字典树的插入

先来看一下字典树的插入，实际上也是字典树的创建，它的步骤如下：

1，从根节点开始，依次读取字符串中的每个字符。