数据结构与算法-前缀树（字典树）

**前缀树（字典树）**

前缀树，也称为字典树，是一种特殊的 Trie 结构，它可以用于存储和检索字符串中的前缀。前缀是指一个字符串的前几个字符组成的序列。

**定义**

前缀树是一棵多叉树，每个结点代表一个字符串的前缀。每个结点包含以下信息：

* `char`:该结点所代表的字符。
* `children`:该结点的子结点，存储在一个哈希表中，以便快速查找和插入。
* `is_end_of_word`: 表示该结点是否是某个单词的最后一个结点。

**构建前缀树**

构建前缀树的过程如下：

1. 初始化一个空的 Trie 结构。
2. 遍历所有待插入的字符串，并将每个字符串中的字符逐一插入到 Trie 结构中。
3. 每次插入一个字符时，首先检查该结点是否已经存在。如果不存在，则创建一个新结点并将其添加到 Trie 结构中。
4. 如果结点已经存在，则继续向下查找直到找到一个空的结点或找到一个已经结束的单词。

**示例代码**

class TrieNode:
 def __init__(self):
 self.children = {}
 self.is_end_of_word = Falseclass Trie:
 def __init__(self):
 self.root = TrieNode()

 def insert(self, word: str) -> None:
 node = self.root for char in word:
 if char not in node.children:
 node.children[char] = TrieNode()
 node = node.children[char]
 node.is_end_of_word = True def search(self, word: str) -> bool:
 node = self.root for char in word:
 if char not in node.children:
 return False node = node.children[char]
 return node.is_end_of_word# 测试代码trie = Trie()
words = ["apple", "banana", "orange"]
for word in words:
 trie.insert(word)

print(trie.search("apple")) # Trueprint(trie.search("banana")) # Trueprint(trie.search("orange")) # Trueprint(trie.search("grape")) # False