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

Question

我在学习时创建了一个 trie 树 python，这是 trie 输出

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

我无法从 trie 中列出所有单词，我显然不理解一些简单的东西，下面是我创建 trie 并添加到 trie 以及检查单词是否存在的代码特里。方法列表是我列出单词的糟糕尝试，目前它只获取每个单词的第一个字母。任何建议都会很棒。

# 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 中存在的单词列表像这样

内容=['hello','abc','baz','bar','barz']

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']

Answer 2

万一这对某人有用，这里有一个 python 实现，如果你有一个基于 class 的 trie，它可以生成一个 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 = []

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

Python Trie: how to traverse it to build list of all words?

python

algorithm

python-3.x

traversal

trie