Resources For IT Professionals
Post an article
Wikis - Page Details
  • First published by (eMicrosoft Partne)
  • When: 20 Aug 2013 6:04 AM
  • Last revision by (eMicrosoft Partne)
  • When: 23 Aug 2013 3:52 AM
  • Revisions: 6
  • Comments: 5
Options
RSSSubscribe to Article (RSS)
Can You Improve This Article?
Positively! Click Sign In to add the tip, solution, correction or comment that will help other users.

Report inappropriate content using these instructions.
Wiki  >  TechNet Articles  >  Baumstrukturen mit LINQ abfragen (de-DE)

Baumstrukturen mit LINQ abfragen (de-DE)

Baumstrukturen mit LINQ abfragen (de-DE)

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.


Table of Contents



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

Links


↑ Zurück zum Anfang

Siehe auch


↑ Zurück zum Anfang

Andere Sprachen

Dieser Artikel ist auch in folgenden Sprachen verfügbar
, , , , , , , , , , , , , , , , [Edit tags]
Leave a Comment
  • Please add 5 and 6 and type the answer here:
  • Post
Wiki - Revision Comment List(Revision Comment)
Sort by: Published Date | Most Recent | Most Useful
Comments
  • 23 Aug 2013 3:52 AM

    Carsten Siemens edited Revision 4. Comment: Fixed typo

  • 20 Aug 2013 6:17 AM

    Carsten Siemens edited Revision 3. Comment: Fixed misspelling

  • 20 Aug 2013 6:15 AM

    Carsten Siemens edited Revision 2. Comment: Fixed link "Zurück zum Anfang"

  • 20 Aug 2013 6:13 AM

    Carsten Siemens edited Revision 1. Comment: Fixed links "Zurück zum Anfang"

  • 20 Aug 2013 6:05 AM

    Carsten Siemens edited Original. Comment: Fixed language tag. Added "(de-DE)" to title.

Page 1 of 1 (5 items)
Wikis - Comment List
Sort by: Published Date | Most Recent | Most Useful
Posting comments is temporarily disabled until 10:00am PST on Saturday, December 14th. Thank you for your patience.
Comments
  • Posted by
    on 20 Aug 2013 6:05 AM

    Carsten Siemens edited Original. Comment: Fixed language tag. Added "(de-DE)" to title.

  • Posted by
    on 20 Aug 2013 6:13 AM

    Carsten Siemens edited Revision 1. Comment: Fixed links "Zurück zum Anfang"

  • Posted by
    on 20 Aug 2013 6:15 AM

    Carsten Siemens edited Revision 2. Comment: Fixed link "Zurück zum Anfang"

  • Posted by
    on 20 Aug 2013 6:17 AM

    Carsten Siemens edited Revision 3. Comment: Fixed misspelling

  • Posted by
    on 23 Aug 2013 3:52 AM

    Carsten Siemens edited Revision 4. Comment: Fixed typo

Page 1 of 1 (5 items)