手写字典树实现 包括查询和插入方法

发布于 2023-07-14 10:00:08 字数 1473 浏览 29 评论 0

字典树是一种树形数据结构,用于高效地存储和查找字符串集合。字典树的每个节点都代表一个字符串(或字符串的前缀),而每个节点的子节点代表字符串的下一个字符。

在字典树中插入一个字符串的过程,就是从根节点开始,依次将字符串中的每个字符插入到字典树中。插入完毕后,最后一个节点被标记为单词结尾节点。

在字典树中查找一个字符串的过程,就是从根节点开始,依次查找字符串中的每个字符,判断是否有对应的子节点。如果没有则说明字典树中不存在该字符串,如果最后一个字符对应的节点被标记为单词结尾节点,则说明字典树中存在该字符串。

示例代码:

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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据

关于作者

仅冇旳回忆

暂无简介

0 文章
0 评论
22 人气
更多

推荐作者

金兰素衣

文章 0 评论 0

ゃ人海孤独症

文章 0 评论 0

一枫情书

文章 0 评论 0

清晰传感

文章 0 评论 0

mb_XvqQsWhl

文章 0 评论 0

    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文