Laden...

[Tutorial] Bäume durchlaufen mit Rekursion (und Alternativen)

Erstellt von ErfinderDesRades vor 15 Jahren Letzter Beitrag vor 9 Jahren 47.259 Views
ErfinderDesRades Themenstarter:in
5.299 Beiträge seit 2008
vor 15 Jahren
[Tutorial] Bäume durchlaufen mit Rekursion (und Alternativen)

Gleich vorweg: dieses Tut hat kein nennenswertes wissenschaftliches Niveau. Ich will nur ein paar Tricks vorstellen, mit denen man den häufigsten Anwendungsfall von Rekursion, nämlich das Durchlaufen und Bearbeiten hierarchischer Datenstrukturen (Bäume) einigermaßen elegant implementieren kann.
Und auch da beschränke ich mich auf die gängigste Art Baum, nämlich Baum als Struktur von "Knoten", wo jeder Knoten eine Auflistung weiterer Knoten enthält - seine "Children" nämlich. (Es gibt auch Bäume mit fester Knoten-Kinderzahl, z.B. binäre Bäume, 2-3-4-Bäume, B-Bäume, und sicherlich weitere, mir unbekannte).
Beispiele für "meine" Art Baum sind: Die Ordner des DateiSystems, die Controls-Auflistung eines Windows.Forms, Xml-Dokumente, HTML, und auch die Nodes einer Treeview (deswegen heißt sie ja so 😉 ).
Ich werde auch nicht wirklich in die Theorie der Rekursion einsteigen, sondern einfach mit dem simpelsten Beispiel anfangen, und hoffen, daß der Code genügend selbsterklärend ist, das Prinzip "Selbst-Aufruf" selbst zu erklären:


   private void TraverseRoot(TreeNode nd) {
      Debug.WriteLine(nd.Text);
      foreach (TreeNode child in nd.Nodes) {
         TraverseRoot(child);
      }
   }

Das gibt zuerst den Node aus, und dann seine Children.
Aber nicht einfach die Children des Nodes hintereinander, nein: Nach jedem Child kommen erst die Children des Childs, bevor der nächste Child dran ist. Verwirrend? - naja, Rekursion eben.

Erst die Henne oder erst die Eier?
Obige Rekursion nenne ich "Root-Rekursion". Weil sie mit einem obersten Knoten beginnt, dem "Root".
Wenn wir damit eine ganze Treeview ausgeben wollen, stoßen wir gleich auf ein Problem: Es gibt kein Root! Oberstes Element ist die Treeview, und die kann nicht an unsere TraverseRoot(TreeNode nd) übergeben werden, die ja einen Treenode erwartet.
Da könnte man jetzt die Rekursion in eine Schleife packen, und auf jeden TopLevel-Treenode einzeln anwenden.
Oder eben "mit den Eiern" anfangen:


   private void TraverseCollection(TreeNodeCollection nodes) {
      foreach (TreeNode nd in nodes) {
         Debug.WriteLine(nd.Text);
         TraverseCollection(nd.Nodes);
      }
   }

(Aufzurufen mit: )

TraverseCollection(treeView1.Nodes);

Das nenne ich "Collection-Rekursion", und das ist meist das flexiblere Prinzip, eben, weil es ohne Root-Element auskommt.

TopDown oder BottomUp?
Angenommen, die Treenodes seien nach Bearbeitung aus der Treeview zu entfernen. Da wird die Rekursion, so wie sie ist ("TopDown" nämlich), keine guten Dienste leisten: Sie wird den ersten Node auffinden, bearbeiten und löschen. Und dann gehts nicht weiter, weil keine Nodes mehr da sind.
Es müssen also die Children zuerst bearbeitet werden, (und das ist mal wieder ganz einfach, wenn man weiß, wie):


   // BottomUp-RootRekursion
   private void TraverseRoot(TreeNode nd) {
      foreach (TreeNode child in nd.Nodes) {
         TraverseRoot(child);
      }
      Debug.WriteLine(nd.Text);
      nd.Delete();
   } 


   // BottomUp-CollectionRekursion
   private void TraverseCollection(TreeNodeCollection nodes) {
      foreach (TreeNode nd in nodes) {
         TraverseCollection(nd.Nodes);
         Debug.WriteLine(nd.Text);
         nd.Delete();
      }
   }

Es kommt also darauf an, ob die Bearbeitung vor dem Selbst-Aufruf durchgeführt wird, oder danach.
BottomUp ergibt auch eine ganz andere, eigentümlich anmutende Reihenfolge. Sieht einer TopDown-Reihenfolge rückwärts ähnlich, aber eben nicht ganz. Runterlader der Beispiel-Solution können sich davon überzeugen.

Struktur-Aufbau
Wichtiger und nicht immer ganz trivialer Anwendungsbereich von Rekursion ist der Aufbau eines Trees.
Dieses Beispiel baut eine Darstellung eines Directories im Treeview auf:


   private void CreateTreeNodes(TreeNodeCollection nodes, DirectoryInfo[] dirs) {
      foreach (DirectoryInfo di in dirs) {
         TreeNode nd = nodes.Add(di.Name);
         CreateTreeNodes(nd.Nodes, di.GetDirectories());
      }
   } 

Kein wirklich gutes Beispiel, man möchte doch das Root-Directory auch im Treeview sehen:


   private void CreateTreeNodes(TreeNodeCollection nodes, DirectoryInfo di) {
      TreeNode nd = nodes.Add(di.Name);
      foreach (DirectoryInfo child in di.GetDirectories()) {
         CreateTreeNodes(nd.Nodes, child);
      }
   } 

Sehr gutes Beispiel, weil es zeigt, wie mächtig Rekursion ist, aber auch, wie schnell es vertrackt werden kann. Die kleine Änderung hat aus der "Collection-Rekursion" eine Art "Misch-Rekursion" gemacht: Während die Directories als Root-Rekursion abgearbeitet werden, werden die TreeNodes als Collection-Rekursion aufgebaut.
Wer Lust hat, kann mal probieren, wie lange er braucht, um die Umkehrung zu schreiben, also die Funktion, die aus den Nodes einer Treeview Directories generiert (ca. 7 Zeilen). 😉

Akkumulator-Problem
Die Bearbeitung des einzelnen Knotens kann auch komplexer sein (wer hätte das gedacht? 😉 ).
Beispiel Directory-Information ermitteln: Es soll die Anzahl der Unterordner, der Files, und die Gesamtgröße eines Directories ausgegeben werden.
Das könnte man quick & dirty so lösen:


   private int _dirCount, _fileCount;
   private long _fullSize;

   private void TraverseDirectories(DirectoryInfo di) {
      _dirCount++;
      FileInfo[] fileInfos = di.GetFiles();
      _fileCount += fileInfos.Length;
      foreach (FileInfo fi in fileInfos) _fullSize += fi.Length;
      foreach (DirectoryInfo child in di.GetDirectories()) {
         TraverseDirectories(child);
      }
   }

   private void DirectorySummary() {
      //das dem aktuellen Directory 2 Ebenen übergeordnete Directory travertieren
      _dirCount = _fileCount = 0; _fullSize = 0;
      TraverseDirectories(new DirectoryInfo(Path.GetFullPath(@"..\..")));
      Debug.WriteLine(string.Concat(
         "_dirCount: ", _dirCount, ", _fileCount: ", _fileCount, ", _fullSize: ", _fullSize));
   }

Im User-Code einer Form hätte man nun die 3 Akkumulator-Variablen _dirCount, _fileCount und _fullSize "herumfahren", die eigentlich nur in DirectorySummary() gebraucht werden.
Böser Verstoß gegen das Prinzip der Kapselung - Noch ein paar weitere solcher "Lösungen", und das Form kommt in den "Keller" - den dunklen Bereich im Code einer Anwendung, in den man niemanden hineingucken läßt 😉.
Real würde man wohl immer noch lieber die Akkumulatoren als Referenz in die Rekursion hineingeben, und es erdulden, dass sie bei jedem Aufruf mitgeschleift werden:


   private void TraverseDirectories(DirectoryInfo di, ref int dirCount, ref int fileCount, ref long fullSize) { /*...*/ }

wahrlich keine Schönheit.
Dasselbe Problem hat man auch, wenn man in der Rekursion Bedingungen abprüfen will (z.B. nach Dateien mit bestimmter Extension suchen): Entweder muß man die Vergleichsvariable string toCompare = ".exe" durch jeden Aufruf durchschleifen, oder eine Klassen-Variable davon machen (und die Kapselung Kapselung sein lassen 😜 )

Lokale Rekursion mit anonymen Methoden
Soweit die Basics, jetzt wirds interessant. C# hat ja diese fabelhaften anonymen Methoden...
Damit kann man eine lokale Rekursion implementieren, und hat damit nicht nur die Kapselung auf die Spitze getrieben, sondern sogar die Extra-Traversions-Methode eingespart:


private void DirectorySummary() {
   //das dem aktuellen Directory 2 Ebenen übergeordnete Directory travertieren
   int dirCount = 0; int fileCount = 0; long sizeSum = 0L;
   Action<DirectoryInfo> traverseDirectories = null;
   traverseDirectories = delegate(DirectoryInfo di) {
      dirCount++;
      FileInfo[] fileInfos = di.GetFiles();
      fileCount += fileInfos.Length;
      foreach (FileInfo fi in fileInfos) sizeSum += fi.Length;
      foreach (DirectoryInfo child in di.GetDirectories()) {
         traverseDirectories(child);
      }
   };
   //Eintrittspunkt in die Rekursion
   traverseDirectories(new DirectoryInfo(Path.GetFullPath(@"..\.."))); 
   Debug.WriteLine(string.Concat(
      "dirCount: ", dirCount, ", fileCount: ", fileCount, ", sizeSum: ", sizeSum));
}

Etwas gewöhnungsbedürftig, aber man gewöhnt sich dran 😉 . Merkpunkte sind:*die lokale Methode muß deklariert und initialisiert sein (mit null vorzugsweise), danach erst implementiert. Andernfalls meldet der Compiler: "Use of unassigned local variable." *Der eigentliche Eintrittspunkt in die Rekursion liegt ziemlich weit unten, nämlich erst nach Deklaration und Implementation der Traversion.

Iterative Traversion
Eine alternative Lösung des Akkumulator-Problems stellt die Iteration dar.


   private void IterateDirectories() {
      //das dem aktuellen Directory 2 Ebenen übergeordnete Directory iterativ travertieren
      int dirCount = 0; int fileCount = 0; long fullSize = 0L;
      Queue<DirectoryInfo> todo = new Queue<DirectoryInfo>();
      todo.Enqueue(new DirectoryInfo(Path.GetFullPath(@"..\..")));
      while (todo.Count > 0) {
         DirectoryInfo di = todo.Dequeue();
         dirCount++;
         FileInfo[] fileInfos = di.GetFiles();
         fileCount += fileInfos.Length;
         foreach (FileInfo fi in fileInfos) fullSize += fi.Length;
         foreach (DirectoryInfo child in di.GetDirectories()) {
            todo.Enqueue(child);
         }
      }
      Debug.WriteLine(string.Concat(
         "dirCount: ", dirCount, ", fileCount: ", fileCount, ", fullSize: ", fullSize));
   }

Eigentlich erstaunlich, wie selten dieser Ansatz umgesetzt wird. Ist doch kaum komplizierter als die Rekursion. Merkpunkte sind hier:*Die Ausgabe-Reihenfolge ist nochmal anders. Nicht "TopDown" oder "BottomUp" - jetzt heißt es: "BreadthFirst" - die Knoten werden schichtweise, Ebene für Ebene, bearbeitet. *Der Zwischenspeicher todo kann ziemlich groß werden. Es befinden sich ja immer Teile 2er Ebenen darin: die restlichen Knoten der gerade in Abarbeitung befindlichen Ebene, und die neuen Knoten der darunter liegenden, im Aufbau befindlichen Ebene. *Rekursion ist "mächtiger". Das Bearbeiten und Löschen im selben Durchgang, wie es die BottomUp-Rekursion ermöglicht, ist bei der Iteration nicht möglich. Vor allem aber den Struktur-Aufbau kann nur die TopDown-Rekursion leisten. *Manche "Mikro-Optimierer" bevorzugen diesen Ansatz auch, weil er schneller ist. Das ist einerseits richtig, andererseits ohne Belang. Rekursive Traversionen sind schnell, und iterative noch schneller. Nur, daß in fast jedem Fall die eigentliche Bearbeitung des Knotens um ein vielfaches langsamer ist, mit Faktoren von 100 bis 10^wasweißich. Von daher ist, wie gesagt, eine Optimierung der Traversion ohne merkbaren Gewinn.

TreeEnumerable
Am Einfachsten wäre es aber immer noch, wenn man einen Tree mit foreach durchlaufen könnte, nicht wahr? Kann man auch, nämlich mit der generischen Klasse TreeEnumerable<T>, die ich mir ausgedacht hab (bescheiden zu boden blick).
Zum Iterieren braucht sie 2 Informationen:1.ein Root-Objekt bzw. eine Roots-Collection 1.einen Delegaten, der angibt, wie von einem Element auf seine Children zugegriffen wird.

Intern wird auf iterative Weise eine rekursive Traversion nachgebildet, optional auch BottomUp. Außerdem kann man über die Property .Depth die aktuelle "Rekursionstiefe" abrufen.
Nützlich auch die .SkipChildren()-Methode. Damit wird nachgebildet die Möglichkeit einer TopDown-Rekursion, nach Abprüfen einer Bedingung den rekursiven Aufruf auch mal auszusetzen, und so die Kinder des aktuellen Knotens eben nicht zu travertieren.
Struktur-Aufbau kann aber auch die TreeEnumerable<T> leider nicht.🙁
Dafür hat sie sogar einen gewissen Mächtigkeits-Vorteil gegenüber der lokalen Rekursion: Auf TreeEnumerable<T> können die fabelhaften Linq-Extensions für die IEnumerable<T> - Schnittstelle angewandt werden.
Implementations-Details lasse ich hier weg, weil, würde zu weit führen. Die Source liegt ja bei, und ich hab mir mit der Kommentierung Mühe gegeben.
Ich zeige nur ein paar Anwendungsbeispiele.
verwendete C#2008-Features
Die folgenden Code-Samples nutzen Features von C#2008, und des Frameworks 3.5, da sollte ich wohl ein paar Bemerkungen zu fallen lassen.
Z.B. gibt es neuerdings den "GoesTo" - Operator "=>" , welchselber ist eine Kurzschreibung des delegate - Schlüsselwortes. Der Ausdruck:

delegate(DirectoryInfo di) { return di.GetDirectories(); }

ist also eleganter schreibbar:

(di) => { di.GetDirectories() }

Und "Typ-Inference" bedeutet, daß der Compiler nun so schlau ist, daß er aus dem Zugewiesenen den Datentyp einer zu initialisierenden Variablen selbst ableiten kann. Beispiel:

DirectoryInfo diRoot = new DirectoryInfo();

eleganter:

var diRoot = new DirectoryInfo();

Extension-Functions wende ich auch an, sowohl selbstgeschriebene als auch welche aus dem neuen System.Linq - Namespace. Dieses (Extensions) oder jenes (Linq) hier zu erläutern würde den Rahmen sprengen, zumal die Thematik gut dokumentiert ist. Soviel sei gesagt: Es lohnt, sich schlau zu machen.

Jetzt aber meine TreeEnumerable<T>-Samples.
Das Akkumulator-Problem taucht bei einer foreach-Iteration natürlich erst gar nicht auf


   private void DirectorySummary() {
      var dirCount = 0; var fileCount = 0; var fullSize = 0L;
      var diRoot = new DirectoryInfo(Path.GetFullPath(@"..\..\.."));
      foreach (var di in TreeEnumerable.FromRoot(diRoot, di => di.GetDirectories())) {
         dirCount++;
         var fileInfos = di.GetFiles();
         fileCount += fileInfos.Length;
         foreach (var fi in fileInfos) { sizeSum += fi.Length; }
      }
      Debug.WriteLine(string.Concat(
         "dirCount: ", dirCount, ", fileCount: ", fileCount, ", fullSize: ", fullSize));
   }

TreeEnumerable.FromRoot() ist eine public static Function, die ein neues TreeEnumerable<T> zurückgibt. Praktischerweise wird dabei der generische Typ T durch Type-Inference ermittelt.

Dieses Beispiel delegiert die Akkumulation an Linq, und kann daher alle Controls eines Forms im (zugegebenermaßen recht langen) Einzeiler ausgeben:


   private void ListControls() {
      //Linq akkumulieren lassen
      Console.WriteLine(
         this.Controls.ToTree<Control>(c => c.Controls)
         .Aggregate("", (s, ctl) => s + ctl + "\n")
      );
   } 

TreeEnumerable<T> .ToTree<T>(Func<T, IEnumerable>) ist eine Extension der IEnumerable-Schnittstelle. Hier muß der generische Typ angegeben werden - einem IEnumerable - Objekt kann der Compiler den Datentyp der enthaltenen Elemente ja nicht ansehen.

Dieser Einzeiler kombiniert TreeEnumerable<Control> mit der Linq-Extension OfType<Label>():


   private void TextToAllLabels(string txt) {
      this.Controls.ToTree<Control>(c => c.Controls).OfType<Label>().ForEach(lb => lb.Text = txt);
   }

ForEach(Action<T>) ist übrigens auch eine selbst geschriebene Extension für IEnumerable<T>
(Ich frage mich, ob das dem ungeübten Auge auch so intuitiv verständlich vorkommt, wie mir)

Sehr knapp formulierte Ausgabe einer Directory-Traversion:


   private void ListDirs() {
      TreeEnumerable.FromRoot(@"..\..\..", Directory.GetDirectories).ForEach(Console.WriteLine);
   }

Hier wird die schon länger gültige C#-Syntax verwendet, nach der ein Methoden-Name ohne () den Delegaten auf die Methode bezeichnet.
.FromRoot() und .ForEach() bekommen also verschiedene Delegaten übergeben.

[Edit: ] Hupsala! - hab mich ja noch gar nicht für die super-flotte, wohlwollende und hilfreiche Redaktion bedankt - also dickes Danke an die Power-User, die das Teil gegengelesen und mit Anmerkungen verziert haben, und natürlich dickes Danke an herbivore, der entgegengenommen, gegengelesen, weitergereicht, freigeschaltet,... hat - na, herbivore eben 😉

Schlüsselwörter: rekursion, tree, baum, hierarchie

Der frühe Apfel fängt den Wurm.

M
334 Beiträge seit 2007
vor 14 Jahren

kann ich grade brauche, super sache 👍

B
218 Beiträge seit 2012
vor 10 Jahren

Schönes Ding 👍

R
71 Beiträge seit 2014
vor 9 Jahren

du auch hier 😉

schöne Anleitung 🙂
kann ich gut gebrauchen 👍 👍

P
157 Beiträge seit 2014
vor 9 Jahren

Hallo,

ich hab recht gute Erfahrungen mit dem Visitor-Pattern gemacht, wenns es darum geht Rekursionen zu vermeiden.

Vielleicht für die Pattern-Freunde eine alternative.

vg

Wenn's zum weinen nicht reicht, lach drüber!