Python Trie: comment le parcourir pour construire la liste de tous les mots?

Question

J'ai créé un arbre de Trie comme python d'apprentissage im, voici la sortie de Trie

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

Je ne peux pas énumérer tous les mots arrière de la structure arborescente, je suis évidemment ne pas comprendre quelque chose de simple, ci-dessous est mon code pour créer le trie et ajouter à la trie ainsi que vérifier si les mots sont présents dans le trie. La liste des méthodes est ma piètre tentative de lister les mots, c'est seulement obtenir la première lettre de chaque mot pour le moment. Tout conseil serait 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') 

La sortie attendue je voudrais une liste de mots présents dans la structure arborescente comme si

content = [ 'bonjour', 'abc', 'baz', 'bar', « barz « ]

Answer 1

Vous devriez écrire une fonction récursive qui recherche l'arbre

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 

exemple sortie

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