手写字典树实现 包括查询和插入方法
字典树是一种树形数据结构,用于高效地存储和查找字符串集合。字典树的每个节点都代表一个字符串(或字符串的前缀),而每个节点的子节点代表字符串的下一个字符。
在字典树中插入一个字符串的过程,就是从根节点开始,依次将字符串中的每个字符插入到字典树中。插入完毕后,最后一个节点被标记为单词结尾节点。
在字典树中查找一个字符串的过程,就是从根节点开始,依次查找字符串中的每个字符,判断是否有对应的子节点。如果没有则说明字典树中不存在该字符串,如果最后一个字符对应的节点被标记为单词结尾节点,则说明字典树中存在该字符串。
示例代码:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = 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_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
在这个示例代码中,我们定义了 TrieNode 类表示字典树的节点,其中包含了字典树节点的子节点和单词结尾标志 is_end_of_word。
我们同时定义了 Trie 类表示整个字典树,包含了插入和查找字符串的方法。在 insert 方法中,我们首先从根节点开始,依次遍历字符串中的每个字符,当遍历到的字符对应的子节点不存在时,我们就创建一个新的 TrieNode 节点,然后令这个节点作为下一个字符的父节点,直到字符串的所有字符都被插入完毕。最终,我们将最后一个节点标记为单词结尾节点。
在 search 方法中,我们同样从根节点开始遍历字符串中的每个字符,如果在某个节点下找不到对应的子节点,则说明该字符串在字典树中不存在,我们直接返回 False。否则,我们就将遍历的节点修改为对应的子节点,并继续往下遍历,直到遍历到字符串的最后一个字符。如果最后一个字符对应的节点被标记为单词结尾节点,说明该字符串在字典树中存在,我们返回 True;否则,说明该字符串只是某个字符串的前缀,不是一个完整的单词,我们同样返回 False。
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
上一篇: 二叉树中序非递归遍历
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论