Python Trie：如何遍历它以构建所有单词的列表？ [英] Python Trie: how to traverse it to build list of all words?

问题描述

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

I have created a trie tree as im learning python, here is the trie output

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

我无法列出所有的单词，我显然不了解一些简单的东西，下面是我创建特里并添加到特里以及检查单词是否存在的代码特里。方法列表是我尝试列出单词的较差尝试，它目前仅获得每个单词的第一个字母。任何建议将是超级。

I am unable to list all the words back out of the trie, I'm obviously not understanding something simple, below is my code to create the trie and add to the trie as well as check if words are present in the trie. The method list is my poor attempt to list words, Its only getting the first letter of each word at the moment. Any advice would be super.

# 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')

我想要的预期输出是像这样的
中出现的单词列表

The expected output i would like is a list of words present in the trie like so

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

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

推荐答案

您应该编写一个搜索树的递归函数

You should write a recursive function that searches the tree

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

这篇关于Python Trie：如何遍历它以构建所有单词的列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！