Inhalt
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
Aber es gibt noch weitere Tree-Strukturen:
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:
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:
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
Käme im besten Falle sowas raus:
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:
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
(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
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:
Wie man sieht sieht man kaum einen Unterschied, und wenn ich
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
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 (
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)
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
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
Leveled Nodes
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:
(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:
Es ist eine
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
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 (
Indented Nodes
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
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
Hier jdfs. der Stepback-Baumbuilder:
Algorithmisch fast gleich der
Interessant an diesem Algo ist, dass dem auch ganz andere Lese-Vorgänge entsprechen:
Etwa in FormelParser und ExpressionTree parse ich eine
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.
Jeder Node hat eine
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:
Ich zeige mal den ganzen Sermon:
Es beginnt in
Die werden zunächstmal in eine
Nun haben wir eine flache Liste von
Einige dieser Nodes haben überhaupt keinen ParentNode - das sind die TopLevel-Nodes. Die erkennt man auch im Datenbestand an ihrer ParentId:
Also die Methode
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):
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
Insert via Pfad
ja mit diesem Dingens nun kann man wie gesagt, einen Pfad im Baum finden bzw. anlegen, wenn nicht gefunden:
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
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
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
Root ist der
Und da kriegte ich bei einer Rekursion, die "bei der Henne ansetzt", ein Problem mit verschiedenen Datentypen, weil ein
Aber
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
- Definition, eigene Tree-Klasse
- Operationen auf Baumstrukturen - rekursiver Durchlauf (klassisch)
- Rekursion mit anonymer Methode
- Rekursiver Aufbau einer Baumstruktur
- Aufbau einer Baumstruktur aus flachen Daten (zB: Text-Datei) - verschiedene "Lese-Schreib-Formate"
- Pfade
- Leveled Nodes
- Indented Nodes
- Stepback-Nodes
- Relational connected Nodes
- Pfade
- Addressierung via Pfad
- HierarchyIndex
- Henne oder Eier? (Input-Argumente rekursiver Methoden)
- BeispielAnwendung
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:
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:
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:
Rekursion mit anonymer Methode
Daher wird bei mir Rekursion prinzipiell immer in einer anonymen Methode durchgeführt:
VB.NET-Quellcode
- Private Shared Function CountChildNodes(nodes As TreeNodeCollection) As Integer
- Dim cnt = 0
- Dim recurse As Action(Of TreeNodeCollection) = Sub(nds)
- cnt += nds.Count
- For Each nd As TreeNode In nds
- recurse(nd.Nodes)
- Next
- End Sub
- recurse(nodes)
- Return cnt
- End Function
- Private Shared Function CollectNodes(nodes As TreeNodeCollection) As List(Of TreeNode)
- Dim nodeList = New List(Of TreeNode)
- Dim recurse As Action(Of TreeNodeCollection) = Sub(nds)
- For Each nd As TreeNode In nds
- nodeList.Add(nd)
- recurse(nd.Nodes)
- Next
- End Sub
- recurse(nodes)
- Return nodeList
- End Function
Nochmal zum
CountChildNodes()
: Wenn man ein CollectChilds()
formuliert hat, kann man sich eine eigene Methode fürs Zählen eigentlich sparen: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 DirectoryInfo
s, mit Children abrufbar per .GetDirectories()
. "Output-Baum" ist die TreenodeCollection
mit ihren Elementen (die wiederum TreenodeCollection
s haben):VB.NET-Quellcode
- Private Shared Sub BuildTreeFromFilesystem(nodes As TreeNodeCollection, rootPath As String)
- Dim recurse As Action(Of TreeNodeCollection, DirectoryInfo()) =
- Sub(nds, dis)
- For Each di In dis
- Dim nd = New TreeNode(di.Name)
- nds.Add(nd)
- recurse(nd.Nodes, di.GetDirectories)
- Next
- End Sub
- recurse(nodes, {New DirectoryInfo(rootPath)})
- End Sub
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
- Private Shared Sub BuildTreeFromMenu(nodes As TreeNodeCollection, menuItems As ToolStripItemCollection)
- Dim recurse As Action(Of TreeNodeCollection, IEnumerable(Of ToolStripDropDownItem)) =
- Sub(nds, itms)
- For Each itm In itms
- Dim nd = nds.Add(itm.Text)
- recurse(nd.Nodes, itm.DropDownItems.OfType(Of ToolStripDropDownItem))
- Next
- End Sub
- recurse(nodes, menuItems.OfType(Of ToolStripDropDownItem))
- End Sub
XElement
e hernehmen würde, würde es wieder so aussehen. (Und ich könnte auch XElement
e aus dem Dateisystem bauen, oder einen Menü-Baum aus XElement
en - 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
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
Hier die Methode, wie man einem Baum durchläuft und so eine "Leveled NodeList" erzeugt:
VB.NET-Quellcode
- Private Shared Function GetLeveledNodes(nodes As TreeNodeCollection) As List(Of String)
- ' zu jedem Node wird sein Level mit-notiert
- Dim level = 0
- Dim nodeList = New List(Of String)
- Dim recurse As Action(Of TreeNodeCollection) = Sub(nds)
- For Each nd As TreeNode In nds
- nodeList.Add($"{level} {nd.Text}")
- level += 1
- recurse(nd.Nodes)
- level -= 1
- Next
- End Sub
- recurse(nodes)
- Return nodeList
- End Function
Hier die Methode, die so eine NodeList liest und daraus den Baum baut:
VB.NET-Quellcode
- Private Shared Sub ReadLeveledNodes(nodes As TreeNodeCollection, nodeList As IEnumerable(Of String))
- Dim stk = New Stack(Of TreeNodeCollection)({nodes})
- For Each line In nodeList
- Dim splts = line.Split({" "c}, 2)
- If splts.Length < 2 Then Continue For ' offensichtlich ungültige Zeilen ignorieren
- Dim level = Integer.Parse(splts(0))
- While stk.Count - 1 > level : stk.Pop() : End While
- dim nd = New TreeNode(splts(1))
- stk.Peek.Add(nd) ' nd in aktuelle NodeCollection einhängen
- stk.Push(nd.Nodes) ' nd-NodeCollection pushen
- Next
- End Sub
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
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
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
- Private Shared Sub ReadStepbackNodes(nodes As TreeNodeCollection, nodeList As IEnumerable(Of String))
- Dim stk = New Stack(Of TreeNodeCollection)({nodes})
- For Each line In nodeList
- Dim splts = line.Split({" "c}, 2)
- If splts.Length < 2 Then Continue For ' offensichtlich ungültige Zeilen ignorieren
- Dim stepsBack = Integer.Parse(splts(0))
- For i = 0 To stepsBack - 1 : stk.Pop() : Next
- stk.Push(stk.Peek.Add(splts(1)).Nodes)
- Next
- End Sub
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.
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:
Ich zeige mal den ganzen Sermon:
VB.NET-Quellcode
- ''' <summary>befüllt die Childs entsprechend relationaler Verweise. returnt Liste derjenigen, die auf keinen Parent verweisen</summary>
- Private Shared Function MakeHierarchycal(myNodes As IEnumerable(Of MyNode)) As IEnumerable(Of MyNode)
- Dim lookup = myNodes.ToLookup(Function(x) x.Id) ' Lookup bilden, gruppiert nach Id
- 'ein Lookup ist ein Dictionary für Gruppen. Da die Id eindeutig ist enthalten unsere Gruppen je genau 1 Element
- For Each d In myNodes
- 'Lookup gibt bei nichtgefundenem Schlüssel eine leere Gruppe zurück - das kann man elegant durch den ?.-Operator abfangen.
- lookup(d.ParentId).FirstOrDefault?.Children.Add(d)
- Next
- 'Lookup ist gleichzeitig auch eine Auflistung von Gruppen - mit Linq abfragbar
- Return From l In lookup Where l.First.ParentId = "-1" Select l.First
- End Function
- Private Sub ReadRelationalNodes(nodes As TreeNodeCollection, rawData As IEnumerable(Of String))
- Dim myNodes = Aggregate s In rawData Let splits = s.Split(Tab)
- Select New MyNode With {.ParentId = splits(0), .Id = splits(1), .Name = splits(2)} Into ToList
- Dim topLevelMyNodes = MakeHierarchycal(myNodes)
- BuildTreeFromHierarchicalData(nodes, topLevelMyNodes)
- End Sub
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
- Private Shared Sub BuildTreeFromHierarchicalData(nodes As TreeNodeCollection, topLevels As IEnumerable(Of MyNode))
- Dim recurse As Action(Of TreeNodeCollection, IEnumerable(Of MyNode)) =
- Sub(nds, mynodes)
- For Each d In mynodes
- Dim nd = nds.Add(d.Name)
- recurse(nd.Nodes, d.Children)
- Next
- End Sub
- recurse(nodes, topLevels)
- 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
- Public Class ApproachResult
- ''' <summary> der gesuchte Pfad, in Segmente zerteilt </summary>
- Public ReadOnly PathSegments As IList(Of String)
- ''' <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>
- Public ReadOnly BestMatch As TreeNode
- ''' <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>
- Public ReadOnly Nodes As TreeNodeCollection
- ''' <summary> die Anzahl schritte, die auf dem Pfad gangbar waren </summary>
- Public ReadOnly StepsDone As Integer
- ''' <summary> der Einfüge-Index, wo in Nodes der Rest-Pfad einzuhängen wäre </summary>
- Public ReadOnly InsertIndex As Integer
- Public Sub New(Nodes As TreeNodeCollection, Node As TreeNode, Segments As IList(Of String), StepsDone As Integer, InsertIndex As Integer)
- Me.Nodes = Nodes
- Me.BestMatch = Node
- Me.PathSegments = Segments
- Me.StepsDone = StepsDone
- Me.InsertIndex = InsertIndex
- End Sub
- ''' <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>
- Public Function InsertRest() As TreeNode
- If IsFullMatch Then Throw New InvalidOperationException("Es gibt keinen Rest zu inserten!")
- Dim nd = Me.Nodes.Insert(InsertIndex, PathSegments(StepsDone))
- For i = StepsDone + 1 To PathSegments.Count - 1
- nd = nd.Nodes.Add(PathSegments(i))
- Next
- Return nd
- End Function
- Public ReadOnly Property IsFullMatch() As Boolean
- Get
- Return InsertIndex < 0
- End Get
- End Property
- 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:
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 Treenode
s 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
Dieser Beitrag wurde bereits 31 mal editiert, zuletzt von „ErfinderDesRades“ ()