Python递归实现字典树数据结构
字典树（Trie树）是一种特殊的树形数据结构，用于快速检索字符串。在字典树中，每个节点代表一个字符，从根节点到叶子节点的路径表示一个字符串。字典树的基本操作包括插入字符串、查找字符串和查找前缀。下面我们来实现一个基于Python的字典树数据结构。
定义字典树节点类：
class TrieNode: def __init__(self): self.children = {} # 子节点 self.is_word = False # 标记是否为单词结尾
定义字典树类：
class Trie: def __init__(self): self.root = TrieNode() # 根节点 def insert(self, word: str) -> None: node = self.root for c in word: if c not in node.children: node.children[c] = TrieNode() node = node.children[c] node.is_word = True def search(self, word: str) -> bool: node = self.root for c in word: if c not in node.children: return False # 未匹配到 node = node.children[c] return node.is_word # 判断是否为单词结尾 def startsWith(self, prefix: str) -> bool: node = self.root for c in prefix: if c not in node.children: return False # 未匹配到 node = node.children[c] return True
以上是基于递归实现的字典树。实现过程中，我们使用了TrieNode类来表示每个节点，其包含两个属性：children和is_word。children保存了子节点，is_word标记当前节点是否为单词结尾。Trie类则包含了插入字符串、查找字符串和查找前缀三个方法，利用递归实现。具体操作如下：
-
插入字符串操作：从根节点开始，将字符串中的每个字符作为一个节点插入字典树中。最后，将最后一个节点标记为单词结尾。
-
查找字符串操作：从根节点开始，依次匹配字符串中的每个字符，如果未能匹配到某个字符，则返回False。如果最后一个字符匹配成功，且最后一个节点标记为单词结尾，则返回True。
-
查找前缀操作：从根节点开始，依次匹配前缀中的每个字符，如果未能匹配到某个字符，则返回False。
我们可以使用下面的代码对字典树进行测试：
t = Trie() t.insert("pidancode") t.insert("python") t.insert("皮蛋编程") print(t.search("pidancode")) # True print(t.search("python")) # True print(t.search("编程")) # False print(t.startsWith("皮蛋")) # True
代码输出结果如下：
True True False True
由此可见，我们的字典树实现是正确的。
相关文章