代码之家 › 专栏 › 技术社区 › Brett

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

trie traversal python-3.x algorithm python

Brett · 技术社区 · 10 年前

我在学习python时创建了一个trie树,下面是trie输出

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

我无法列出trie中的所有单词,我显然不理解一些简单的东西,下面是我创建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中出现的单词列表像这样

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

2 回复 | 直到 10 年前

Francesco 10 年前

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

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

Nic Scozzaro 6 年前

如果这对某人有用,这里有一个python实现,如果您有一个基于类的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 = []