Tree-Übungen - Rekursion

    • VB.NET
    • .NET (FX) 4.5–4.8

    Es gibt 1 Antwort in diesem Thema. Der letzte Beitrag () ist von ErfinderDesRades.

      Tree-Übungen - Rekursion

      Inhalt
      1. Definition, eigene Tree-Klasse
      2. Operationen auf Baumstrukturen - rekursiver Durchlauf (klassisch)
      3. Rekursion mit anonymer Methode
      4. Rekursiver Aufbau einer Baumstruktur
      5. Aufbau einer Baumstruktur aus flachen Daten (zB: Text-Datei) - verschiedene "Lese-Schreib-Formate"
        • Pfade
        • Leveled Nodes
        • Indented Nodes
        • Stepback-Nodes
        • Relational connected Nodes

      6. Addressierung via Pfad
      7. HierarchyIndex
      8. Henne oder Eier? (Input-Argumente rekursiver Methoden)
      9. BeispielAnwendung
      Definition
      Vereinfachend gesagt: Ein Node ist ein Objekt, was eine Liste von Children enthält, und der Datentyp der Children ist derselbe wie der Node.
      Typischstes Beispiel ist die Treenode-Klasse. Ist auch am anschaulichsten, weil es gibt ja das Treeview-Control zur Anzeige von Treenodes.


      Aber es gibt noch weitere Tree-Strukturen:
      Control hat eine Property Controls As ControlCollection, und deren Elemente sind auch vom Typ Control.
      DirectoryInfo hat eine Function .GetDirectories() As DirectoryInfo()
      XElement hat Function .Elements() As IEnumerable(Of XElement)
      Usw. Und das sind nur Tree-Struktur-klassen.
      In der Realität gibts natürlich auch Baum-Strukturen - das hat Programmierer ja erst auf die Idee gebracht, geeignete Klassen zu entwickeln, die solch modellieren:
      Etwa ein Baum mit seinen Ästen: jeder kann weitere Äste haben
      Oder ein Fluss mit all seinen Zuflüssen: Jeder kann weitere Zuflüsse haben
      Oder die DateiOrdner im Dateisystem: Jeder Ordner kann weitere Ordner enthalten
      Man kann mit Leichtigkeit auch selbst eine Baumstruktur-Klasse schaffen:

      VB.NET-Quellcode

      1. Public Class MyNode
      2. Public ReadOnly Children As New List(Of MyNode)
      3. Public Name As String
      4. End Class


      Operationen auf Baumstrukturen

      Rekursiver Durchlauf (alias "Traverse")
      Die meisten Operationen beruhen auf einem rekursiven Durchlauf durch den Baum.
      Eine naheliegende Operation wäre, die Nodes zählen zu wollen:

      VB.NET-Quellcode

      1. Private Shared Function CountChildren(nds As TreeNodeCollection) As Integer
      2. Dim cnt = nds.Count
      3. For Each nd As TreeNode In nds
      4. cnt += CountChildren(nd.Nodes) ' Selbst-Aufruf (alias Rekursion)
      5. Next
      6. Return cnt
      7. End Function
      Das ist jetzt eine klassische Rekursion - funktioniert auch gut, weil nur eine Zahl ermittelt werden soll.
      Will man die Nodes selbst einsammeln wird das schon ungemütlich, denn statt cnt += CountChildren(nd.Nodes) muss man nun Listen in Listen umfüllen, weil Listen kann man ja nicht addieren wie Integer
      Käme im besten Falle sowas raus:

      VB.NET-Quellcode

      1. Private Shared Function CollectChildren(nodes As TreeNodeCollection) As List(Of TreeNode)
      2. Dim lst = New List(Of TreeNode)
      3. For Each nd As TreeNode In nodes
      4. lst.Add(nd)
      5. lst.AddRange(CollectChildren(nd.Nodes))
      6. Next
      7. Return lst
      8. End Function
      Also ein klassischer rekursiver Durchlauf dieser Art würde massenhaft Listen erzeugen, umfüllen und verfallen lassen bis auf die eine letzte.

      Rekursion mit anonymer Methode
      Daher wird bei mir Rekursion prinzipiell immer in einer anonymen Methode durchgeführt:

      VB.NET-Quellcode

      1. Private Shared Function CountChildNodes(nodes As TreeNodeCollection) As Integer
      2. Dim cnt = 0
      3. Dim recurse As Action(Of TreeNodeCollection) = Sub(nds)
      4. cnt += nds.Count
      5. For Each nd As TreeNode In nds
      6. recurse(nd.Nodes)
      7. Next
      8. End Sub
      9. recurse(nodes)
      10. Return cnt
      11. End Function
      12. Private Shared Function CollectNodes(nodes As TreeNodeCollection) As List(Of TreeNode)
      13. Dim nodeList = New List(Of TreeNode)
      14. Dim recurse As Action(Of TreeNodeCollection) = Sub(nds)
      15. For Each nd As TreeNode In nds
      16. nodeList.Add(nd)
      17. recurse(nd.Nodes)
      18. Next
      19. End Sub
      20. recurse(nodes)
      21. Return nodeList
      22. End Function
      Das ist das Einfachste - glaubts mir. Das Grundschema aller rekursiven Operationen ist dabei immer dasselbe - notwendige Anpassungen an den jeweiligen Zweck fallen so am Geringsten aus.

      Nochmal zum CountChildNodes(): Wenn man ein CollectChilds() formuliert hat, kann man sich eine eigene Methode fürs Zählen eigentlich sparen:

      VB.NET-Quellcode

      1. Private Shared Function CountChildNodes2(nodes As TreeNodeCollection) As Integer
      2. Return CollectNodes(nodes).Count
      3. End Function
      (und das ist wieder so simpel, dass man es weglassen sollte).

      Rekursiver Aufbau
      Auslesen eines Datenbestandes ist eine Standard-Operation auf Bäumen. Aufbauen anderer Bäume eine andere.
      Klassisch etwa, einen Treeview aus dem Dateisystem zu befüllen. "Input-Baum" sind DirectoryInfos, mit Children abrufbar per .GetDirectories(). "Output-Baum" ist die TreenodeCollection mit ihren Elementen (die wiederum TreenodeCollections haben):

      VB.NET-Quellcode

      1. Private Shared Sub BuildTreeFromFilesystem(nodes As TreeNodeCollection, rootPath As String)
      2. Dim recurse As Action(Of TreeNodeCollection, DirectoryInfo()) =
      3. Sub(nds, dis)
      4. For Each di In dis
      5. Dim nd = New TreeNode(di.Name)
      6. nds.Add(nd)
      7. recurse(nd.Nodes, di.GetDirectories)
      8. Next
      9. End Sub
      10. recurse(nodes, {New DirectoryInfo(rootPath)})
      11. End Sub
      Die Signatur der anonymen rekursiven Methode ist angepasst: Statt nur einer bekommt sie jetzt zwei Listen übergeben: Die eine wird ausgelesen, und daraus werden Elemente erstellt, die der anderen hinzugefügt werden.
      Und die Kinder dieser Elemente gehen natürlich mit in die Rekursion - die wollen ja auch aufgebaut werden.

      Wie gesagt: Das ist ein Pattern.
      Wie ich den Tree aus dem Dateisystem aufbauen kann, kann ich ihn auch aus einem Menü aufbauen - ist ja auch eine Baum-Struktur:

      VB.NET-Quellcode

      1. Private Shared Sub BuildTreeFromMenu(nodes As TreeNodeCollection, menuItems As ToolStripItemCollection)
      2. Dim recurse As Action(Of TreeNodeCollection, IEnumerable(Of ToolStripDropDownItem)) =
      3. Sub(nds, itms)
      4. For Each itm In itms
      5. Dim nd = nds.Add(itm.Text)
      6. recurse(nd.Nodes, itm.DropDownItems.OfType(Of ToolStripDropDownItem))
      7. Next
      8. End Sub
      9. recurse(nodes, menuItems.OfType(Of ToolStripDropDownItem))
      10. End Sub
      Wie man sieht sieht man kaum einen Unterschied, und wenn ich XElemente hernehmen würde, würde es wieder so aussehen. (Und ich könnte auch XElemente aus dem Dateisystem bauen, oder einen Menü-Baum aus XElementen - würde alles diesem Pattern folgen.)

      Aufbau aus flachen Daten
      Oft ists aber kein Baum, aus dem der Baum erstellt werden soll, sondern es sind flache Daten. Meinetwegen ein Mathe-Parser bekommt eine List(Of Token) und soll daraus einen Expression-Tree erstellen.

      Einlesen aus Datei
      Aber am häufigsten ist wohl, man will eine Baumstruktur abspeichern und wieder herstellen. Das kann oft via Serialisierung gelingen - wenn die Nodes diese unterstützen (TreeNode etwa kann das). Wird Serialisierung jedoch nicht unterstützt, oder man hat Sonderwünsche, muss halt eine selbstgebastelte Persistierung her.
      Ich habe für die Demo-Anwendung übrigens nicht das Schreiben und Lesen in eine Datei implementiert. Sondern ich konvertiere meine Trees nur in eine (flache) List(Of String). Diese dann in eine Datei schubsen ist kein Act (Ansonsten kann man auch das inne Sources nachgucken).
      Jedenfalls beim "Flachklopfen" einer Baumstruktur muss man den Daten auch Hierarchie-Informationen hinzufügen. Sonst erhält man eine flache Liste von Nodes und kann nicht mehr rekonstruieren, welcher in welchem einzuhängen ist.
      Zum Persistieren dieser "Hierarchy-Hints" gibts viele Modelle - ich zeige mal vier:

      Pfade

      Quellcode

      1. Node0
      2. Node0\Node1
      3. Node0\Node2
      4. Node3
      5. Node3\Node4
      6. Node3\Node4\Node10
      7. Node3\Node4\Node11
      8. Node3\Node5
      9. Node3\Node6
      10. Node7
      11. Node7\Node8
      12. Node7\Node8\Node12
      13. Node7\Node8\Node12\Node14
      14. Node7\Node9
      Nachteil ist: es verbraucht ziemlich Platz. Vorteil: Die Reihenfolge der Einträge ist egal.
      Tatsächlich kann man jederzeit auch nachträglich einen einzelnen Eintrag gezielt an eine beliebige bestimmte Position im fertigen Baum plazieren, indem man so einen Pfad angibt.
      Das können die anderen Persistier-Formate nicht, sondern sind drauf angewiesen, dass alle Einträge auf einen Rutsch kommen und in richtiger Reihenfolge.
      Ich komme später dazu - Stichwort ApproachResult

      Leveled Nodes

      Quellcode

      1. 0 Node0
      2. 1 Node1
      3. 1 Node2
      4. 0 Node3
      5. 1 Node4
      6. 2 Node10
      7. 2 Node11
      8. 1 Node5
      9. 1 Node6
      10. 0 Node7
      11. 1 Node8
      12. 2 Node12
      13. 3 Node14
      14. 1 Node9
      Derselbe Tree wie zuvor, nur sind redundante Pfad-Anteile entfernt. Dafür muss man aber nun angeben, welchen Level der hinzuzufügende Node haben soll.
      Hier die Methode, wie man einem Baum durchläuft und so eine "Leveled NodeList" erzeugt:

      VB.NET-Quellcode

      1. Private Shared Function GetLeveledNodes(nodes As TreeNodeCollection) As List(Of String)
      2. ' zu jedem Node wird sein Level mit-notiert
      3. Dim level = 0
      4. Dim nodeList = New List(Of String)
      5. Dim recurse As Action(Of TreeNodeCollection) = Sub(nds)
      6. For Each nd As TreeNode In nds
      7. nodeList.Add($"{level} {nd.Text}")
      8. level += 1
      9. recurse(nd.Nodes)
      10. level -= 1
      11. Next
      12. End Sub
      13. recurse(nodes)
      14. Return nodeList
      15. End Function
      (Wie man sieht, folgt es dem oben erwähnten Pattern für Operationen auf Baumstrukturen.)

      Hier die Methode, die so eine NodeList liest und daraus den Baum baut:

      VB.NET-Quellcode

      1. Private Shared Sub ReadLeveledNodes(nodes As TreeNodeCollection, nodeList As IEnumerable(Of String))
      2. Dim stk = New Stack(Of TreeNodeCollection)({nodes})
      3. For Each line In nodeList
      4. Dim splts = line.Split({" "c}, 2)
      5. If splts.Length < 2 Then Continue For ' offensichtlich ungültige Zeilen ignorieren
      6. Dim level = Integer.Parse(splts(0))
      7. While stk.Count - 1 > level : stk.Pop() : End While
      8. dim nd = New TreeNode(splts(1))
      9. stk.Peek.Add(nd) ' nd in aktuelle NodeCollection einhängen
      10. stk.Push(nd.Nodes) ' nd-NodeCollection pushen
      11. Next
      12. End Sub
      Es ist eine Sub, denn sie muss nix returnen. Die Baumstruktur wird in der übergebenen NodeCollection aufgebaut.
      Pattern für's Baum-bauen aus flacher Liste:
      Zunächstmal: Keine Rekursion!. Sondern die flache Liste wird normal durchlaufen, und die daraus gebildeten Nodes werden in einem Stack(Of T) zwischen-verwaltet, nämlich wie folgt:
      Erst wird eine bestimmte Anzahl vom Stack runtergepoppt - die Anzahl kann auch 0 sein. (Weiter unten nenne ich diese Anzahl "Stepback, Rücksprung").
      Im obersten dann auf dem Stack verbliebenen Element (es ist eine NodeCollection) wird der neue Node eingehängt.
      Des neuen Nodes ChildCollection wird auf den Stack gepusht.
      Also kurz: (verschieden) viele runter-poppen, dann den neuen Node 1) in den obersten (.Peek()) einhängen, 2) drauf-pushen.

      Indented Nodes

      Quellcode

      1. Node0
      2. Node1
      3. Node2
      4. Node3
      5. Node4
      6. Node10
      7. Node11
      8. Node5
      9. Node6
      10. Node7
      11. Node8
      12. Node12
      13. Node14
      14. Node9
      Diese Darstellung ist intuitiver als das mit den leveled Nodes. Aber das Berechnen der Einrückungen (beim Schreiben) und das Auswerten derselben beim Einlesen sind bischen mehr Code, also für produktiv nehme man lieber leveled Nodes.

      Stepback

      Quellcode

      1. 0 Node0
      2. 0 Node1
      3. 1 Node2
      4. 2 Node3
      5. 0 Node4
      6. 0 Node10
      7. 1 Node11
      8. 2 Node5
      9. 1 Node6
      10. 2 Node7
      11. 0 Node8
      12. 0 Node12
      13. 0 Node14
      14. 3 Node9
      Beim Stepback-Format gibt man nicht den Node-Level an, sondern man gibt an, um wieviel der Node "zurückspringt". Die Idee folgt genau dem Baum-Bauprinzip: Erst keine oder viele runterpoppen, dann den neuen Node drauf-pushen.
      Was mit Vor- und Rück-Sprung gemeint ist, ist in der Indented-Node-Darstellung (s.o.) besonders anschaulich. Beachte auch, dass ein Node maximal 1 Vorsprung tun kann, aber Rücksprünge können bis zur Root-Ebene erfolgen (nochmal der Pattern: keinen bis viele runter-poppen, aber genau einen drauf-pushen).
      ("Vorsprung" ist übrigens auch nicht ganz richtig: ein "Vorsprung" entsteht bei Stepback=0, wenn also der neue Node gepusht wird, ohne zuvor was runterzupoppen.)
      Hier jdfs. der Stepback-Baumbuilder:

      VB.NET-Quellcode

      1. Private Shared Sub ReadStepbackNodes(nodes As TreeNodeCollection, nodeList As IEnumerable(Of String))
      2. Dim stk = New Stack(Of TreeNodeCollection)({nodes})
      3. For Each line In nodeList
      4. Dim splts = line.Split({" "c}, 2)
      5. If splts.Length < 2 Then Continue For ' offensichtlich ungültige Zeilen ignorieren
      6. Dim stepsBack = Integer.Parse(splts(0))
      7. For i = 0 To stepsBack - 1 : stk.Pop() : Next
      8. stk.Push(stk.Peek.Add(splts(1)).Nodes)
      9. Next
      10. End Sub
      Algorithmisch fast gleich der ReadLeveledNodes()-Methode - nur statt der While-Schleife zum Poppen haben wir jetzt eine Zähl-Schleife.
      Interessant an diesem Algo ist, dass dem auch ganz andere Lese-Vorgänge entsprechen:
      Etwa in FormelParser und ExpressionTree parse ich eine List(Of Token) zu einem Treeview, aber auch zu einem Expression-Tree.
      Die Token stellen Operatoren mathematischer Ausdrücke dar, in umgekehrt polnischer Notation.
      Und jeder Operator weiss die Anzahl seiner Operanden - und diees ist genau die Anzahl Stepbacks, die beim Aufbau des Expression-Trees vom Stack zu poppen ist.
      Also Umgekehrt Polnische Notation ist (unter anderem) eine Syntax zur Definition von Baumstrukturen im Stepback-Format.

      Relational connected Nodes
      Relationale Datenmodelle können natürlich auch Baumstrukturen abbilden.

      Quellcode

      1. ParentId Id Text
      2. -1 1 Node0
      3. 1 2 Node1
      4. 1 3 Node2
      5. -1 4 Node3
      6. 4 5 Node4
      7. 5 6 Node10
      8. 5 7 Node11
      9. 4 8 Node5
      10. 4 9 Node6
      11. -1 10 Node7
      12. 10 11 Node8
      13. 11 12 Node12
      14. 12 13 Node14
      15. 10 14 Node9
      Jeder Node hat eine Id, und ist über eine ParentId mit einem ParentNode verknüpft. Normalerweise liegen derlei Daten in speziellen Datenklassen und Datei-Formaten vor, sodass sie bereits durch das Einlesen (per Serialisierung, oder als Dataset.ReadXml()) eine hierarchische Struktur bilden.
      Aber ich hab mir mal ein abgebrochen, mir eine Baumstruktur-Klasse auszudenken, und aus einer TextDatei in obigem Format zu befüllen.
      Die Baumstruktur-Klasse ist die in Kapitel 1 als "eigene Tree-Klasse" vorgestellte, erweitert um die Ids:

      VB.NET-Quellcode

      1. Private Class MyNode
      2. Public ParentId, Id, Name As String
      3. Public ReadOnly Children As New List(Of MyNode)
      4. End Class


      Ich zeige mal den ganzen Sermon:

      VB.NET-Quellcode

      1. ''' <summary>befüllt die Childs entsprechend relationaler Verweise. returnt Liste derjenigen, die auf keinen Parent verweisen</summary>
      2. Private Shared Function MakeHierarchycal(myNodes As IEnumerable(Of MyNode)) As IEnumerable(Of MyNode)
      3. Dim lookup = myNodes.ToLookup(Function(x) x.Id) ' Lookup bilden, gruppiert nach Id
      4. 'ein Lookup ist ein Dictionary für Gruppen. Da die Id eindeutig ist enthalten unsere Gruppen je genau 1 Element
      5. For Each d In myNodes
      6. 'Lookup gibt bei nichtgefundenem Schlüssel eine leere Gruppe zurück - das kann man elegant durch den ?.-Operator abfangen.
      7. lookup(d.ParentId).FirstOrDefault?.Children.Add(d)
      8. Next
      9. 'Lookup ist gleichzeitig auch eine Auflistung von Gruppen - mit Linq abfragbar
      10. Return From l In lookup Where l.First.ParentId = "-1" Select l.First
      11. End Function
      12. Private Sub ReadRelationalNodes(nodes As TreeNodeCollection, rawData As IEnumerable(Of String))
      13. Dim myNodes = Aggregate s In rawData Let splits = s.Split(Tab)
      14. Select New MyNode With {.ParentId = splits(0), .Id = splits(1), .Name = splits(2)} Into ToList
      15. Dim topLevelMyNodes = MakeHierarchycal(myNodes)
      16. BuildTreeFromHierarchicalData(nodes, topLevelMyNodes)
      17. End Sub
      Es beginnt in ReadRelationalNodes() - da kommen die oben gezeigten Rohdaten rein.
      Die werden zunächstmal in eine List(Of MyNode) eingelesen (zeile#14).
      Nun haben wir eine flache Liste von MyNode-Objekten, und die Herausforderung ist, anhand von Id/ParentId herauszufinden, welcher MyNode in welchen Parent-MyNode einzuhängen ist.
      Einige dieser Nodes haben überhaupt keinen ParentNode - das sind die TopLevel-Nodes. Die erkennt man auch im Datenbestand an ihrer ParentId: -1.
      Also die Methode MakeHierarchycal() übernimmt diese Aufgabe, aus der flachen Liste eine hierarchische Struktur aufzubauen. Ihr Rückgabewert ist wieder eine List(Of MyNode) - die TopLevelNodes nämlich. Wie gesagt: Die TopLevel-Nodes sind daran zu erkennen, dass ihre ParentId auf keinen anderen Node verweist - in diesem Beispiel -1 ist.
      Haben wir die TopLevel-Nodes, so können wir einen rekursiven Durchlauf zum Aufbau einer Tree-Struktur durchführen - exakt nach dem in Kapitel 4 angegebenen Pattern (es wird langsam langweilig):

      VB.NET-Quellcode

      1. Private Shared Sub BuildTreeFromHierarchicalData(nodes As TreeNodeCollection, topLevels As IEnumerable(Of MyNode))
      2. Dim recurse As Action(Of TreeNodeCollection, IEnumerable(Of MyNode)) =
      3. Sub(nds, mynodes)
      4. For Each d In mynodes
      5. Dim nd = nds.Add(d.Name)
      6. recurse(nd.Nodes, d.Children)
      7. Next
      8. End Sub
      9. recurse(nodes, topLevels)
      10. End Sub


      Addressierung via Pfad
      Wieder ein ganz anderer Algorithmus.
      Einen Pfad in einem Baum suchen zeitigt auch verschiedenerlei Ergebnisse:
      Man kann entlang des Pfades voranschreiten und den durch den Pfad bezeichneten Node finden.
      Man kann ein Stück des Pfades finden, aber dann nicht weiter. Man findet also den Node, in dem der Pfad fehlt. Nicht der ganze Pfad fehlt, sondern nur der Rest des Pfades - ein Teil wurde ja erfolgreich abgeschritten.
      Grade dieser Node ist wichtig, in dem der Rest des Pfades fehlt, weil da kann man dann ja in einer weiteren Operation diesen Rest gschwind mal anlegen und einhängen in besagten Node.
      Um eine solch komplexe Ergebnislage festhalten zu können, habich die Klasse ApproachResult erfunden. Und die TreenodeExtension .Approach(path As String), die sich dem Ziel-Node "annähert" (engl: approach)

      VB.NET-Quellcode

      1. Public Class ApproachResult
      2. ''' <summary> der gesuchte Pfad, in Segmente zerteilt </summary>
      3. Public ReadOnly PathSegments As IList(Of String)
      4. ''' <summary> der Treenode, der dem Pfad am besten entspricht - im Idealfall entspricht er vollständig, schlimmstenfalls ist er Nothing - wenn nichtmal das Root-Segment matcht </summary>
      5. Public ReadOnly BestMatch As TreeNode
      6. ''' <summary> die Nodes, in die der Rest des Pfades ggfs. einzuhängen ist. Selbst wenn der Pfad ühaupt nicht matcht, sind diese Nodes gültig - dann sinds die Treeview.Nodes</summary>
      7. Public ReadOnly Nodes As TreeNodeCollection
      8. ''' <summary> die Anzahl schritte, die auf dem Pfad gangbar waren </summary>
      9. Public ReadOnly StepsDone As Integer
      10. ''' <summary> der Einfüge-Index, wo in Nodes der Rest-Pfad einzuhängen wäre </summary>
      11. Public ReadOnly InsertIndex As Integer
      12. Public Sub New(Nodes As TreeNodeCollection, Node As TreeNode, Segments As IList(Of String), StepsDone As Integer, InsertIndex As Integer)
      13. Me.Nodes = Nodes
      14. Me.BestMatch = Node
      15. Me.PathSegments = Segments
      16. Me.StepsDone = StepsDone
      17. Me.InsertIndex = InsertIndex
      18. End Sub
      19. ''' <summary> hängt den Rest des Pfades, der nicht mehr gematcht hat, an die richtige Position ein, und gibt den letzten eingehängten Node zurück. InvalidOperationException, wenn der Pfad restlos gematcht hat </summary>
      20. Public Function InsertRest() As TreeNode
      21. If IsFullMatch Then Throw New InvalidOperationException("Es gibt keinen Rest zu inserten!")
      22. Dim nd = Me.Nodes.Insert(InsertIndex, PathSegments(StepsDone))
      23. For i = StepsDone + 1 To PathSegments.Count - 1
      24. nd = nd.Nodes.Add(PathSegments(i))
      25. Next
      26. Return nd
      27. End Function
      28. Public ReadOnly Property IsFullMatch() As Boolean
      29. Get
      30. Return InsertIndex < 0
      31. End Get
      32. End Property
      33. End Class 'ApproachResult


      Insert via Pfad
      ja mit diesem Dingens nun kann man wie gesagt, einen Pfad im Baum finden bzw. anlegen, wenn nicht gefunden:

      VB.NET-Quellcode

      1. With TV.Nodes.Approach(pth.Split("\"c))
      2. If .IsFullMatch Then MessageBox.Show($"Pfad{Lf}{pth}{Lf}existiert bereits") Else .InsertRest() : TV.ExpandAll()
      3. End With


      HierarchyIndex
      Ein HierachyIndex gibt von allen Ebenen über dem Node den nullbasierten Index an - es ist also eine Liste von Indizees. Gugge Bildle: Der angewählte Node hat den HierachyIndex 1 0 1

      Der Zugriff mit sowas ist einfach und schnell, wenn man eine Baumstruktur verarbeitet - aber zum Abspeichern in eine Datei ists unhandlich: Was soll man eine Index-Liste mit hinschreiben, wo beim Leveled-Format eine einfache Zahl reicht?
      Auch ist ein HierachyIndex veränderlich: wird ein Node gelöscht oder zugefügt, so ändern sich alle HierachyIndicees der Folge-Nodes und derer Children.

      Zuerst die Henne oder die Eier?
      Wer genau die Codes beguckt hat, wird festgestellt haben, dass ich nie einzelne Elemente in die Rekursion gebe, sondern immer Listen.
      Etwa TreenodeCollection und DirectoryInfo() (es ist ein Array!!) gebe ich hinein. Man könnte die Rekursion auch so formulieren, dass man einen Root-Treenode hineingibt, und ein Root-DirectoryInfo - tu ich aber nicht.
      Gewissermassen setzen meine Rekursionen immer an den Eiern an, nicht an der Henne.
      Grund ist, dass oft kein Root-Node gegeben ist. Sieht man gleich beim Treeview: Es gibt keinen Root-TreeNode!
      Root ist der Treeview selbst.
      Und da kriegte ich bei einer Rekursion, die "bei der Henne ansetzt", ein Problem mit verschiedenen Datentypen, weil ein Treeview ist kein Treenode.
      Aber Treeview hat eine TreenodeCollection, und das ist derselbe Datentyp, den auch Treenodes Child-Liste hat.

      BeispielAnwendung

      Wie gesagt: Statt in eine Datei zu schreiben schreibt das Teil seinen Tree in die Textbox links (und gibt auch an, in welchem "Format"). Das Nette daran ist, man kann in der Textbox editieren und dann den manipulierten Tree wieder einlesen aus der Textbox.
      Aber er kann auch vom Dateisystem den Tree aufbauen, oder aus dem Menü - halt was hier im Tut erwähnt wurde.

      Ausgebuffte rekursive Methoden zur Dateisuche finden sich auch hier: Rekursive Dateisuche mit anonymer Methode
      Dateien
      • TreeTryals06.zip

        (24,04 kB, 143 mal heruntergeladen, zuletzt: )

      Dieser Beitrag wurde bereits 31 mal editiert, zuletzt von „ErfinderDesRades“ ()

      Baumstrukturen in Yaml

      Eigentlich hatten wir Yaml schon: nämlich wird eine Baumstruktur als indentedNodes gespeichert, so ists eine Yaml-Datei (*.yml).

      Nein, das ist nicht ganz richtig, Yaml hat auch eine richtige Syntax, sogar komplizierter als Json.
      Aber das für uns wesentliche ist, dass Yaml Verschachtelungen nicht mit Klammern darstellt ((), <>, [], {}), nicht mit Tags (<html></html>) und auch nicht mit Schlüsselworten (Sub End Sub, For Next, Using End Using).
      Heieieih - wie schön könnte vb.net sein, wenn man die End-Schlüsselworte weglassen könnte:

      VB.NET-Quellcode

      1. ' aus
      2. Friend Property Culture() As Global.System.Globalization.CultureInfo
      3. Get
      4. Return resourceCulture
      5. End Get
      6. Set
      7. resourceCulture = value
      8. End Set
      9. End Property
      10. 'würde:
      11. Friend Property Culture() As Global.System.Globalization.CultureInfo
      12. Get
      13. Return resourceCulture
      14. Set
      15. resourceCulture = value
      16. 'bzw mit line-break-operator kompakt wie c#:
      17. Friend Property Culture() As Global.System.Globalization.CultureInfo
      18. Get: Return resourceCulture
      19. Set: resourceCulture = value
      das reichte doch. Mit bischen intellenteren Editor wäre das auch nicht unsicherer.

      Egal - jdfs. Yaml macht das so, lässt den redundanten Kram weg und stellt Verschachtelung nur durch Einrückung dar.

      Und erfreulicherweise kann Notepad++ auch Yaml-Syntax, inklusive der Einrück-Logik.
      Ein als Yaml abgespeicherter Baum stellt sich in Nodepad++ auch als Baum dar: Man kann Nodes ein- und aus-klappen, sowie ganze Gliederungs-Ebenen (Menü View\Fold...)
      Damit hat man quasi einen Treeview geschenkgekriegt, wie man ihn selber kaum hinprogrammieren könnte.
      Ich hab damit mal ein "FileSize-Browser" gebastelt, mit dem man gucken kann, wo die Bytes auf Platte sind.

      Eine Solution ist expandiert, und darin aber der obj\-Ordner collapsed. Bemerkenswert, dass der verborgene .vs-Folder bei weitem am fettesten ist.
      Wie gesagt: Das ist kein Treeview von mir, sondern einfach eine TextDatei (*.yml), in np++ geöffnet.

      Ausserdem ist np++ ja auch ein Editor, mit Suche/Ersetzen etc. - also Möglichkeiten, die über die eines Treeviews enorm hinausgehen.
      Zu beachten ist einzig, dass np++ als Einrückung leider ausschliesslich genau 4 Spaces akzeptiert - keine Tabs, und auch keine andere Indentation.

      ps: der "FileSize-Browser" ist inne Sample-Solution mit drin in post #1

      Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „ErfinderDesRades“ ()