前缀（字典）树总结

什么是前缀树（Trie）

In computer science, a trie, also called digital tree or prefix tree, is a type of search tree, a tree) data structure used for locating specific keys from within a set. These keys are most often strings), with links between nodes defined not by the entire key, but by individual characters). - wikepidea

前缀树（又叫做字典树）是一种特殊类型的多叉树，每条边代表一个一个字母，每个节点代表一个字符串（前缀），该字符串由从根节点到当前节点路径字母组成，由于节点间的父子关系，父节点字符串就相当于子节点字符串的前缀，因此称为前缀树。

需要特殊注意的是前缀树的根节点由于没有父节点，代表空字符串

前缀树结构

假设给定字符串中只有小写字母，则每个节点可能有26种类型边指向孩子节点，数据结构定义如下：

class TrieTreeNode{
    # 长度为26的子节点数组
    TrieTreeNode[] children;
    # 当前节点是否为一个单词（还能够存储以当前前缀为前缀的单词数量）
    boolean isWord;
}

重点在于孩子节点数组的定义，其他属性可以根据具体问题设计

常用操作

• insert 向前缀树中插入一个单词

  public void inert(String word){
      // 临时的初始节点
      TrieTreeNode curNode = root;
      //将word转换成从根节点到(非)叶子节点的一条路
      for(int i = 0;i < word.length();i++){
          //如果不存在当前前缀，添加
          if(curNode.children[word.charAt(i) - 'a'] == null){
              curNode.children[word.charAt(i) - 'a']； = new TrieTreeNode();
          }
          curNode = curNode.children[word.charAt(i) - 'a']；
      }
      //标示当前词语
      curNode.isWord = true;
  }

• search 在前缀树中查找一个单词或者前缀

  public boolean search(String word){
      //从根节点搜索
      TrieTreeNode curNode = root;
      for(int i = 0;i < word.length();i++){
          //不包含当前字母
          if(curNode.children[word.charAt(i)] == null){
              return false;
          }
          curNode = curNode.children[word.charAt(i)];
      }
      //如果是前缀,可以直接返回
      return true;
      //如果是找单词，需要查看节点标识符
      return curNode.isWord;
  }

几个典型例题

1. lc:211. 添加与搜索单词 - 数据结构设计
   • 前缀树结构练习题