Python Language Exploration d'arbres avec récursion


Exemple

Disons que nous avons l'arbre suivant:

root
- A
  - AA
  - AB
- B
  - BA
  - BB
    - BBA

Maintenant, si nous souhaitons énumérer tous les noms des éléments, nous pourrions le faire avec un simple for-loop. Nous supposons qu'il y a une fonction get_name() pour retourner une chaîne du nom d'un noeud, une fonction get_children() pour renvoyer une liste de tous les sous-noeuds d'un noeud donné dans l'arborescence et une fonction get_root() pour obtenir le noeud racine.

root = get_root(tree)
for node in get_children(root):
    print(get_name(node))
    for child in get_children(node):
        print(get_name(child))
        for grand_child in get_children(child):
            print(get_name(grand_child))
# prints: A, AA, AB, B, BA, BB, BBA

Cela fonctionne bien et rapidement, mais que se passe-t-il si les sous-nœuds ont leurs propres sous-nœuds? Et ces sous-noeuds pourraient avoir plus de sous-noeuds ... Et si vous ne savez pas à l'avance combien il y en aura? Une méthode pour résoudre ce problème est l'utilisation de la récursivité.

def list_tree_names(node):
    for child in get_children(node):
        print(get_name(child))
        list_tree_names(node=child)

list_tree_names(node=get_root(tree))
# prints: A, AA, AB, B, BA, BB, BBA

Vous souhaitez peut-être ne pas imprimer, mais renvoyer une liste plate de tous les noms de nœuds. Cela peut être fait en passant une liste déroulante en paramètre.

def list_tree_names(node, lst=[]):
    for child in get_children(node):
        lst.append(get_name(child))
        list_tree_names(node=child, lst=lst)
    return lst

list_tree_names(node=get_root(tree))
# returns ['A', 'AA', 'AB', 'B', 'BA', 'BB', 'BBA']