什么是字典树字典树是一种空间随时间变化的数据结构，又名Trie树、前缀树，是一种树结构（字典树是一种数据结构），典型的用用于计数、排序和保存大量字符串。因此，它经常被搜索引擎系统用于文本词频统计。其优点是：利用字符串的公共前缀减少查询时间，尽量减少不必要的字符串比较，查询效率高于哈希树。在大多数情况下，您可能很难凭直觉或有接触经验。您可能对前缀一无所知。做题的时候可能会遇到前缀问题，暴力匹配就能躲过一劫。如果字符串比较小，可能可以使用哈希表这样的结构。算了算了，但是如果字符串比较长，相同的前缀很多，那么使用字典树可以大大减少内存占用，提高效率。字典树的一个应用场景：当你在搜索框中输入一些词时，会出现一些与神灵相关的搜索内容。有时你会惊讶于你是如何做到的。这其实就是字典树的一种思想。对于字典树，有3个重要的性质：1：根节点不包含字符，除根节点外的每个节点只包含一个字符。根节点不包含字符。这样做的目的是能够包含所有字符串。2：从根节点到某个节点，经过字符串就是该节点对应的字符串。3：每个节点的子节点字符不同，即对应的词和字符是唯一的。字典树的设计与实现上面介绍了什么是字典树，下面我们就开始设计字典树吧！对于字典树，在不同的场景或者需求设计上可能会有一些细微的差别，但是一般来说，一般的字典树包括插入、查询（指定字符串）、查询（前缀）。我们先分析简单的情况，即所有字符串都是26个小写字母，可以以Trie树为模板进行实现。实现Trie类：Trie()初始化一个前缀树对象。voidinsert(Stringword)将字符串word插入到前缀树中。booleansearch(Stringword)如果字符串单词在前缀树中（即在检索之前被插入），则返回真；否则，返回false。booleanstartsWith(Stringprefix)如果先前插入的字符串单词的前缀之一是prefix，则返回true；否则，返回false。如何设计这个字典树？对于一个字典树Trie类，必然有一个根节点root，而这个节点类型TrieNode的设计方法有很多，这里为了简单放一个26大小的TrieNode类型数组，对应'a'-'z'字符，同时用一个boolean类型的变量isEnd来表示是否是字符串的结尾（如果为真）。类TrieNode{TrieNode子[];booleanisEnd;//结束标志publicTrieNode()//初始化{son=newTrieNode[26];}}如果字符多的话，使用数组可能会消耗一些内存空间，但是这里26个连续的字符是可以的，如果你把big,bit,bz加到一个字典树中，那么实际上是这样的：然后分析具体操作：插入操作：遍历字符串，从字典树的根节点开始遍历，找到每个字符对应的位置，先判断是否为空。如果为空，则需要创建一个新的Trie。比如插入big枚举的第一个b创建一个TrieNode，后面也是一样。但是重要的是在停止的TrieNode上设置isEnd为true表示这个节点是构成字符串的结束节点。这部分对应的关键代码是：TrieNoderoot;/**初始化*/publicTrie(){root=newTrieNode();}/**往trie中插入一个词。*/publicvoidinsert(Stringword){TrieNodenode=root;//临时节点用于枚举for(inti=0;i
