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);
}
}
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);
}
}
TraverseCollection(treeView1.Nodes);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();
}
}
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());
}
}
private void CreateTreeNodes(TreeNodeCollection nodes, DirectoryInfo di) {
TreeNode nd = nodes.Add(di.Name);
foreach (DirectoryInfo child in di.GetDirectories()) {
CreateTreeNodes(nd.Nodes, child);
}
}
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));
}
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) { /*...*/ }
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));
}
- 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));
}
- 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:
- ein Root-Objekt bzw. eine Roots-Collection
- einen Delegaten, der angibt, wie von einem Element auf seine Children zugegriffen wird.
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(); }(di) => { di.GetDirectories() }DirectoryInfo diRoot = new DirectoryInfo();var diRoot = new DirectoryInfo();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));
}
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")
);
}
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);
}
(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);
}
.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