Wie kann man effizient eine baumartige Struktur aus einem Array von Pfadzeichenfolgen konstruieren, die eine Dateisystemhierarchie darstellen?

So konstruieren Sie eine baumartige Struktur aus einem Pfad-String-Array

Einführung:
Gegeben eine Mit einem Array von Zeichenfolgen, die Dateipfade darstellen, möchten wir eine baumartige Datenstruktur erstellen, die die Verzeichnishierarchie widerspiegelt. Jede Zeichenfolge im Array stellt einen vollständigen Pfad vom Stammverzeichnis zu einer bestimmten Datei oder einem bestimmten Verzeichnis dar.

Rekursiver Ansatz mit untergeordneter Liste:
Um den Baum rekursiv zu erstellen, müssen wir Folgendes tun Durchlaufen Sie die Pfadzeichenfolgen von links nach rechts und teilen Sie sie in Komponenten auf. Wir können den Baum mithilfe einer Node-Struktur mit einem Namen und einem Teil untergeordneter Knoten darstellen.

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

Die wichtigste Erkenntnis besteht darin, mit einer Liste von Knoten statt mit den untergeordneten Elementen eines einzelnen Knotens zu arbeiten. Dadurch können wir mehrere Bäume mit unterschiedlichen Wurzelknoten verarbeiten.

<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. Überprüfen Sie, ob die erste Komponente (Namen[0]) in der aktuellen Liste der Knoten (Wurzel) vorhanden ist.
2. Wenn nicht, fügen Sie der Liste einen Knoten mit diesem Namen hinzu.
3. Rekursiv AddToTree für die aktualisierte Liste aufrufen und dabei die verbleibenden Komponenten des Pfads übergeben.

Beispiel :
Für die Eingabepfadzeichenfolgen:

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

Die Funktion AddToTree erzeugt die folgende Baumstruktur:

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

Vorteile gegenüber dem ursprünglichen Ansatz:

1. Arbeitet auf einer Liste von Knoten und ermöglicht so mehrere Bäume mit unterschiedlichen Wurzelknoten.
2. Erstellt neue Knoten, anstatt den Eingabeknoten wiederzuverwenden, und stellt so sicher, dass jede Ebene des Baums ist eindeutig.
3. Durchsucht den Baum, um eine Duplizierung von Knoten zu verhindern.

Das obige ist der detaillierte Inhalt vonWie kann man effizient eine baumartige Struktur aus einem Array von Pfadzeichenfolgen konstruieren, die eine Dateisystemhierarchie darstellen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!