Python 字典树的数据结构设计与封装
字典树，又称前缀树或 Trie 树，是一种多叉树结构，常用于快速匹配字符串。本文将设计并封装一个 Python 版本的字典树数据结构，并提供使用示例。
- 设计思路
字典树的节点通常包含两个重要属性：一个字符值 char 和一个子节点列表 children。为了实现更快的字符串匹配，我们还需要在节点上记录一个标志 is_end，表示从根节点到当前节点的路径是否是一个完整的单词。
在 Python 中，我们可以通过类来实现字典树节点的定义：
class TrieNode:
def init(self):
self.children = {} # 子节点列表
self.is_end = False # 是否是单词末尾
在字典树类中，我们需要维护根节点 root。
class Trie:
def init(self):
self.root = TrieNode()
接下来，我们可以定义三个基本操作：插入单词、查找单词、查找前缀。
- 插入单词
当我们要往字典树中插入一个单词时，需要从根节点开始遍历每个字符，对于不存在的字符，我们需要新建一个节点。在遍历到单词的最后一个字符时，将节点的 is_end 标志设置为 True，表示这是一个完整的单词。
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 = 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
- 查找前缀
查找前缀与查找单词的差别在于，前缀可以只匹配字典树上的一部分字符。如果遍历到某个节点时 is_end 标志为 True，则说明这一部分路径可以匹配一个单词前缀。
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
- 完整示例
下面是一个完整的 Python 字典树实现代码，并提供了使用示例：
class TrieNode:
def init(self):
self.children = {}
self.is_end = False
class 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 = 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
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
使用示例
trie = Trie()
trie.insert("pidancode.com")
trie.insert("皮蛋编程")
print(trie.search("pidancode.com")) # True
print(trie.startsWith("pidan")) # True
print(trie.search("pi")) # False
相关文章