Arbre et récursivité

Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions d’instances plus petites du même problème (source Wikipédia).

Ce type d’algorithme se prête tout particulièrement à la manipulation de structures complexes, et notamment les arbres.

Structure arborescente des systèmes de fichiers

La plupart des systèmes de fichiers sont présentés sous la forme d’une structure arborescente.

Exemples

Explorateur Windows …

image

Dans la suite de l’article,

• nous utiliserons l’arborescence de ce dossier (à télécharger, et dézipper)
• nous utiliserons le langage Python avec le module os  et plus particulièrement les fonctions :
  • os.listdir(chemin_dossier)  : retourne la liste des noms de fichiers ou dossier contenus dans le dossier chemin_dossier
  • os.path.isfile(chemin)  : retourne True  si chemin  est un fichier, False  dans le cas contraire (dossier ou mauvais chemin)
  • os.path.isdir(chemin)  : retourne True  si chemin  est un dossier, False  dans le cas contraire (fichier ou mauvais chemin)
  • os.path.join(chemin_dossier, nom_fichier)  : retourne le chemin du fichier nom_fichier , relatif au chemin chemin_dossier

Affichage du contenu d’un dossier

def afficher_dossier(racine, parent = "", niveau = 0):
    # chemin absolu de la racine
    abspath = os.path.join(parent, racine)
    if os.path.isdir(abspath):
        for fd in os.listdir(abspath):
            print("   "*niveau+fd)                  # affichage du fichier/dossier, avec indentation
            afficher_dossier(fd, abspath, niveau+1) # on relance la fonction afficher() -- récursivité !

Structure arborescente personnalisée

Choix de la structure

Parmi les possibilités, on peut retenir une structure à base de dictionnaires et de listes :

arbre = [["dir1",
            ["dir1.1", ["fich1.1.1", "fich1.1.2"]],
            ["dir1.2", ["fich1.2.1", "fich1.2.2", "fich1.2.3"]],
            ["dir1.3", ["fich1.2.1", "fich1.2.2", "fich1.2.3",
                ["dir1.3.1", ["fich1.3.1.1", "fich1.3.1.2"]]]],
        ],
        ["dir2",
            ["dir2.1", ["fich2.1.1", "fich2.1.2"]],
            ["dir2.2", ["fich2.2.1", "fich2.2.2",
                ["dir2.2.1", ["fich2.2.1.1", "fich2.2.1.2"]],
                ["dir2.2.2", ["fich2.2.2.1", "fich2.2.2.2", "fich2.2.2.3"]]]],
        ],
        "fich1", "fich2", "fich3"
        ]

Construction

def construire(racine, parent = ""):
    """ Fonction de peuplement de l'arbre
        renvoie une liste structurée comme tree
        à partir de la racine spécifiée
    """
    # chemin absolu de la racine
    abspath = os.path.join(parent, racine)
    if not os.path.isdir(abspath):
        # la racine est un fichier
        return
    return [[fd, construire(fd, abspath)] for fd in os.listdir(abspath)]

Affichage