Comment construire efficacement une structure arborescente à partir d'un tableau de chaînes de chemins représentant une hiérarchie de système de fichiers ?

Comment construire une structure arborescente à partir d'un tableau de chaînes de chemin

Introduction :
Étant donné un tableau de chaînes représentant les chemins de fichiers, nous visons à construire une structure de données arborescente reflétant la hiérarchie des répertoires. Chaque chaîne du tableau représente un chemin complet depuis le répertoire racine vers un fichier ou un répertoire spécifique.

Approche récursive avec liste d'enfants :
Pour construire l'arborescence de manière récursive, nous devons parcourez les chaînes de chemin de gauche à droite, en les divisant en composants. Nous pouvons représenter l'arborescence en utilisant une structure Node avec un nom et une tranche de nœuds enfants.

<code class="go">type Node struct {
    Name     string
    Children []Node
}</code>

L'idée clé est d'opérer sur une liste de nœuds plutôt que sur les enfants d'un seul nœud. Cela nous permet de gérer plusieurs arbres avec des nœuds racines différents.

<code class="go">func AddToTree(root []Node, names []string) []Node {
    if len(names) > 0 {
        var i int
        for i = 0; i < len(root); i++ {
            if root[i].Name == names[0] { //already in tree
                break
            }
        }
        if i == len(root) {
            root = append(root, Node{Name: names[0]})
        }
        root[i].Children = AddToTree(root[i].Children, names[1:])
    }
    return root
}</code>

1. Vérifiez si le premier composant (noms[0]) existe dans la liste actuelle des nœuds (racine).
2. Sinon, ajoutez un nœud portant ce nom à la liste.
3. Appelez récursivement AddToTree sur la liste mise à jour, en passant les composants restants du chemin.

Exemple :
Pour les chaînes du chemin d'entrée :

<code class="go">s := [...]string{"a/b/c", "a/b/g", "a/d"}</code>

La fonction AddToTree produit la structure arborescente suivante :

<code class="json">{
 "name": "a",
 "children": [
     {
      "name": "b",
      "children": [
        {
         "name": "c"
        },
        {
         "name": "g"
        }
      ]
    },
    {
     "name": "d",
     "children": []
    }
  ]
}</code>

Avantages par rapport à l'approche originale :

1. Fonctionne sur une liste de nœuds, permettant la création de plusieurs arbres avec différents nœuds racines.
2. Crée de nouveaux nœuds au lieu de réutiliser le nœud d'entrée, garantissant que chaque niveau de l'arborescence est distinct.
3. Recherche dans l'arborescence pour éviter la duplication des nœuds.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!