Python Trie：如何遍历以构建所有单词列表？

Question

我正在学习Python，我创建了一棵trie树，在这里是trie输出：

{'a': {'b': {'c': {'_': '_'}}}, 'b': {'a': {'x': {'_': '_'}, 'r': {'_': '_', 'z': {'_': '_'}}, 'z': {'_': '_'}}}, 'h': {'e': {'l': {'l': {'o': {'_': '_'}}}}}}

我无法从 trie 中列出所有单词，显然我没有理解某些简单的东西。以下是我创建 trie 以及向 trie 添加内容以检查单词是否存在的代码。list 方法是我列出单词的努力，目前只获取每个单词的第一个字母。任何建议都将非常有用。

# Make My trie
def make_trie(*args):
    """
    Make a trie by given words.
    """
    trie = {}
    for word in args:
        if type(word) != str:
            raise TypeError("Trie only works on str!")
        temp_trie = trie
        for letter in word:
            temp_trie = temp_trie.setdefault(letter, {})
        temp_trie = temp_trie.setdefault('_', '_')
    return trie


# Is a word in the trie
def in_trie(trie, word):
    """
    Detect if word in trie.
    :param word:
    :param trie:
    """
    if type(word) != str:
        raise TypeError("Trie only works on str!")
    temp_trie = trie
    for letter in word:
        if letter not in temp_trie:
            return False
        temp_trie = temp_trie[letter]
    return True


# add to the trie
def add(trie, *args):
    for word in args:
        if type(word) != str:
            raise TypeError("Trie only works on str!")
        temp_trie = trie
        for letter in word:
            temp_trie = temp_trie.setdefault(letter, {})
        temp_trie = temp_trie.setdefault('_', '_')
    return trie


# My Attempt to list out words
def list(obj, text, words):
   str = ""
   temp_trie = obj
   for index, word in enumerate(temp_trie):
       print(temp_trie[word])



if __name__ == '__main__':
    trie = make_trie('hello', 'abc', 'baz', 'bar', 'barz')
    # print(trie)
    # get_file()
    words = []
    # list(trie, "", words)
    print(in_trie(trie, 'bar'))
    print(in_trie(trie, 'bab'))
    print(in_trie(trie, 'zzz'))
    add(trie, "bax")
    print(in_trie(trie, 'bax'))
    print(in_trie(trie, 'baz'))
    print(trie)
    list(trie, "", 'hello')

我希望您能够提供期望的输出——一个字典中包含Trie树中的单词，就像这样：

content = ['hello', 'abc', 'baz', 'bar', 'barz']

- Brett

---

输入的预期结果是什么？ - user5547025

预期结果将是一个包含所有单词的列表 '你好', 'abc', 'baz', 'bar', 'barz'在学习Python时，我创建了一棵trie树，以下是trie的输出{'a': {'b': {'c': {'': ''}}}, 'b': {'a': {'x': {'': ''}, 'r': {'': '', 'z': {'': ''}}, 'z': {'': ''}}}, 'h': {'e': {'l': {'l': {'o': {'': ''}}}}}}这是输入后的trie。 - Brett

请编辑您的问题并在其中放置预期输出。 - user5547025

Answer 1

你应该编写一个递归函数来搜索这棵树。

def list_words(trie):
    my_list = []
    for k,v in trie.items():
        if k != '_':
            for el in list_words(v):                
                my_list.append(k+el)
        else:
            my_list.append('')
    return my_list

示例输出

>>> trie = {'a': {'b': {'c': {'_': '_'}}}, 'b': {'a': {'x': {'_': '_'}, 'r': {'_': '_', 'z': {'_': '_'}}, 'z': {'_': '_'}}}, 'h': {'e': {'l': {'l': {'o': {'_': '_'}}}}}}
>>> print(list_words(trie))
['abc', 'hello', 'bax', 'barz', 'bar', 'baz']

- Francesco

Answer 2

如果对某人有用的话，这里有一个Python实现，可以生成基于类的Trie中的所有字符串。

def build_all(root):
    l = []
    if root:
        if root.children: 
            for node in root.children: 
                for s in build_all(node):
                    l.append(str(node.val) + s)
        else: 
            l.append('')
    return l

class node:
    def __init__(self, val):
        self.val = val
        self.children = []

- Nic Scozzaro