Freigeben über

Baumstrukturen mit LINQ abfragen (de-DE)

  • Artikel

http://c.statcounter.com/9186659/0/1ecc522a/1/Dieser Artikel ist die deutsche Übersetzung meines zuerst auf Englisch erschienen Artikels How to Query Trees Using LINQ.

(Gerichtete) Bäume gehören zu den häufigsten Datenstrukturen in der Informatik. Wie sie mit LINQ genutzt werden, ist aber weniger offensichtlich. Dieser Artikel definiert eine generische LINQ-Extension, die dieses Problem löst, gibt Beispiele an und diskutiert Alternativen.

Motivation

Ausgangspunkt dieses Artikels war eine einfache Frage im LINQ-Forum, die einige Jahre unbeantwortet geblieben ist ...

Wie kann Knoten eines Baums unabhängig von ihrer Position abfragen?

Es scheint sich also zu lohnen, diese Aufgabe näher zu betrachten. Fangen wir mit einem Beispiel an! Eine einfache Klasse TreeNode ist so implementiert:

public class  TreeNode
{
    public string  Id { get; set; }
    public int  Data { get; set; }
    public List<TreeNode> Children { get; private  set; }
 
    public TreeNode(string id, int data)
        : this(id, data, new  TreeNode[0])
    { }
 
    public TreeNode(string node, int data, params TreeNode[] children)
    {
        Id = node;
        Data = data;
        Children = new  List<TreeNode>(children);
    }
}

Dazu passen folgende Testdaten:

TreeNode rootNode =
    new TreeNode("node-0", 35,
        new TreeNode("node-1", 17,
            new TreeNode("node-2", 20)),
        new TreeNode("node-3", 19),
        new TreeNode("node-4", 5,
            new TreeNode("node-5", 25),
            new TreeNode("node-6", 40)));

↑ Zurück zum Anfang

Lösung

Implementiere eine generische Extension-Klasse, die beliebige Baumstrukturen traversieren kann.  Die einzige zu erfüllende Vorbedingung ist, dass die Kinder eines Knoten als *IEnumerable *gespeichert werden. Die Wahl eines Lambda-Ausdruck als Selektor vermeidet, den Zugriffspfads fest zu kodieren und ermöglicht,  die Wiederverwendung der Extension.

public static  class LinqTreeExtension
{
    public static  IEnumerable<T> SelectNestedChildren<T>
        (this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
    {
        foreach (T item in source)
        {
            yield return  item;
            foreach (T subItem in SelectNestedChildren(selector(item), selector))
            {
                yield return  subItem;
            }
        }
    }
}

Die Extension-Methode SelectNestedChildren traversiert den Baum per Tiefensuche von links nach rechts.

↑ Zurück zum Anfang

Beispiel

Beispiel 1: Einebnen einer Baumstruktur (ohne die Wurzel des Baums)

var flattenedTreeWithoutRoot 
    = rootNode.Children
        .SelectNestedChildren(t => t.Children).ToList();

Die Ergebnisliste enthält die Knoten mit den IDs "note-1" bis "note-6". Hinweis:  Die Wurzel des Baums ist in der Ergebnisliste nicht enthalten. Wir korrigieren das im nächsten Beispiel.

Beispiel 2: Einebnen einer Baumstruktur (inklusive Wurzel des Baums)

var flattenedTreeIncludingRoot 
    = new  TreeNode[] {rootNode }
        .SelectNestedChildren(t => t.Children).ToList();

Die Abfrage wird auf einem Array ausgeführt, das die Wurzel des Baums als einziges Element enthält. Die Ergebnisliste enthält - wie erwartet - die Knoten mit den IDs "note-0" bis "note-6".

Beispiel 3: LINQ-Abfrage über alle Knoten eines Baums.

var result
    = new  TreeNode[] { rootNode }
        .SelectNestedChildren(t => t.Children)
        .Where(t => t.Data > 30).ToList();

Die Ergebnisliste enthält zwei Knoten mit den IDs "node-0" und "node-6".

↑ Zurück zum Anfang

Gegenanzeigen und Alternativen

Die vorgestellte LINQ-Erweiterung hat entscheidende Stärken:

  • Die Extension ist auf alle Baumstrukturen anwendbar, die ihre Kinder als IEnumerable speichern.
  • Sie integriert sich nahtlos in andere LINQ-Operationen.

In einigen Fällen muss jedoch auf Alternativen zurückgegriffen werden:

Zyklischer Graph statt eines Baums

Problem: Die Extension wird nicht terminieren, wenn sie in einen Zyklus des Graphen läuft.
Lösung: Modifikation der Extension:

  • Füge einen HashSet<T> zu der Extension hinzu, die über die bereits besuchten Knoten Buch führt.
  • Die Klasse T sollte GetHashCode() und Equals() überschreiben.
  • Die Extension muss bereits besuchte Knoten überspringen.

Persistenter Baum in der Datenbank

Problem: Wenn der Baum in einer Datenbank (und nicht im Speicher) vorliegt, ist die Extension unnötig aufwändig.
Lösung: Alle Knoten des Baums liegen in einer Datenbanktabelle vor, die direkt abgefragt werden kann. Dabei ist es unerheblich, ob es sich um eine logische Baumstruktur oder sogar einen zyklischen Graphen handelt. Die Abfrage erfolgt mit dem Entity Framework:

var databaseResult = context.TreeNodes
    .Where(t => t.Data > 30).ToList();

Im Falle dieses Beispiels sollten jedoch zwei kleine Änderungen an der Klasse TreeNode vorgenommen werden:

  • Das Property Children sollte den modifier virtual erhalten, um Lazy Loading zu ermöglichen.
  • Das Entity Framework benötigt einen weiteren parameterlosen Konstruktor.

XML-Datenstruktur

Eine XML-Datenstruktur ist ein Spezialfall eines gerichteten Baums.

**Problem: ** LINQ to XML ist auf XML-Documente spezialisiert.
Lösung: LINQ to XML verwenden. Dieser Ansatz reduziert den Codierungsaufwand und nutzt einen etablierten Standard. Außerdem sind weitere Features von LINQ to XML nutzbar. Beispiel:

var xmlElements = XDocument.Load("myfile.xml").Descendants();
 
var result = xmlElements.Where(x => ...);

XDocument.Descendents() gibt ein IEnumerable<XElement> zurück, das direkt abgefragt werden kann.

Fazit:
Die Nutzung von LINQ ist einfach. Es gibt jedoch nicht die Lösung, die für alle Aufgabenstellungen passt. 

↑ Zurück zum Anfang

↑ Zurück zum Anfang

Siehe auch

↑ Zurück zum Anfang

Andere Sprachen

Dieser Artikel ist auch in folgenden Sprachen verfügbar