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
|
1 2 3 4 5 6 7 |
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 :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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
|
1 2 3 4 5 6 7 8 9 10 11 |
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)] |
