Wie hierarchische Daten mit Linq

Question

suchen Ich brauche einen Baum für Daten zu suchen, die überall im Baum sein könnten. Wie kann das mit linq gemacht werden?

class Program 
{ 
    static void Main(string[] args) { 

     var familyRoot = new Family() {Name = "FamilyRoot"}; 

     var familyB = new Family() {Name = "FamilyB"}; 
     familyRoot.Children.Add(familyB); 

     var familyC = new Family() {Name = "FamilyC"}; 
     familyB.Children.Add(familyC); 

     var familyD = new Family() {Name = "FamilyD"}; 
     familyC.Children.Add(familyD); 

     //There can be from 1 to n levels of families. 
     //Search all children, grandchildren, great grandchildren etc, for "FamilyD" and return the object. 


    } 
} 

public class Family { 
    public string Name { get; set; } 
    List<Family> _children = new List<Family>(); 

    public List<Family> Children { 
     get { return _children; } 
    } 
} 

Answer 1

Das ist eine Erweiterung It'sNotALie.s answer.

public static class Linq 
{ 
    public static IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector) 
    { 
     return selector(source).SelectMany(c => Flatten(c, selector)) 
           .Concat(new[] { source }); 
    } 
} 

Probentest Nutzung:

var result = familyRoot.Flatten(x => x.Children).FirstOrDefault(x => x.Name == "FamilyD"); 

Returns familyD Objekt.

Sie können es auf IEnumerable<T> Quelle machen arbeiten:

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector) 
{ 
    return source.SelectMany(x => Flatten(x, selector)) 
     .Concat(source); 
} 

Answer 2

Ganz einfach:

familyRoot.Flatten(f => f.Children); 
//you can do whatever you want with that sequence there. 
//for example you could use Where on it and find the specific families, etc. 

IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector) 
{ 
    return selector(source).SelectMany(c => Flatten(selector(c), selector)) 
          .Concat(new[]{source}); 
} 

Answer 3

Nun, ich denke, die Art und Weise mit der Technik der Arbeit mit hierarchischen Strukturen gehen:

1. Sie benötigen einen Anker

2. zu machen Sie müssen die Rekursion Teil

   // Anchor 
   
   rootFamily.Children.ForEach(childFamily => 
   { 
       if (childFamily.Name.Contains(search)) 
       { 
        // Your logic here 
        return; 
       } 
       SearchForChildren(childFamily); 
   }); 
   
   // Recursion 
   
   public void SearchForChildren(Family childFamily) 
   { 
       childFamily.Children.ForEach(_childFamily => 
       { 
        if (_childFamily.Name.Contains(search)) 
        { 
         // Your logic here 
         return; 
        } 
        SearchForChildren(_childFamily); 
       }); 
   } 
   

Answer 4

So ist die einfachste Option, eine Funktion zu schreiben, die Ihre Hierarchie durchläuft und eine einzelne Sequenz erzeugt. Dies geht dann zu Beginn Ihrer LINQ-Operationen, z.B.

IEnumerable<T> Flatten<T>(this T source) 
    { 
     foreach(var item in source) { 
     yield item; 
     foreach(var child in Flatten(item.Children) 
      yield child; 
     } 
    } 

So rufen einfach: familyRoot.Flatten() Wo (n => n.Name == "Bob");.

Eine leichte Alternative würden Ihnen einen Weg geben, schnell einen ganzen Zweig zu ignorieren: family.Flatten (n => n.Children.Count> 2) .Where:

IEnumerable<T> Flatten<T>(this T source, Func<T, bool> predicate) 
    { 
     foreach(var item in source) { 
     if (predicate(item)) {   
      yield item; 
      foreach(var child in Flatten(item.Children) 
       yield child; 
     } 
    } 

Dann könnten Sie Dinge wie tun (...)

Answer 5

eine andere Lösung ohne Rekursion ...

var result = FamilyToEnumerable(familyRoot) 
       .Where(f => f.Name == "FamilyD"); 


IEnumerable<Family> FamilyToEnumerable(Family f) 
{ 
    Stack<Family> stack = new Stack<Family>(); 
    stack.Push(f); 
    while (stack.Count > 0) 
    { 
     var family = stack.Pop(); 
     yield return family; 
     foreach (var child in family.Children) 
      stack.Push(child); 
    } 
} 

Answer 6

ich zwei der vorgeschlagenen Codes versucht haben, und machte den Code ein bisschen mehr klar:

public static IEnumerable<T> Flatten1<T>(this T source, Func<T, IEnumerable<T>> selector) 
    { 
     return selector(source).SelectMany(c => Flatten1(c, selector)).Concat(new[] { source }); 
    } 

    public static IEnumerable<T> Flatten2<T>(this T source, Func<T, IEnumerable<T>> selector) 
    {    
     var stack = new Stack<T>(); 
     stack.Push(source); 
     while (stack.Count > 0) 
     { 
      var current = stack.Pop(); 
      yield return current; 
      foreach (var child in selector(current)) 
       stack.Push(child); 
     } 
    } 

Flatten2() scheint ein bisschen schneller sein, aber es ist ein enger Lauf.

Answer 7

Ich mag Stapel Kenneth Bo Christensens Antwort verwenden, es funktioniert super, ist es leicht zu lesen und es ist schnell (und Rekursion nicht verwendet werden). Die einzige unangenehme Sache ist, dass es um die Reihenfolge der untergeordneten Elemente umkehrt (weil Stapel FIFO). Wenn Ihnen die Sortierreihenfolge egal ist, ist es in Ordnung. Wenn dies der Fall ist, kann die Sortierung leicht mit dem Selektor (aktuell) erfolgen. Reverse() im foreach Schleife (der Rest des Codes ist das gleiche wie in Kenneth ursprünglichen post) ...

public static IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector) 
{    
    var stack = new Stack<T>(); 
    stack.Push(source); 
    while (stack.Count > 0) 
    { 
     var current = stack.Pop(); 
     yield return current; 
     foreach (var child in selector(current).Reverse()) 
      stack.Push(child); 
    } 
} 

Answer 8

Einige weitere Varianten zu den Antworten von It'sNotALie., MarcinJuraszek und DamienG.

Zuerst geben die ersteren zwei eine kontraintuitive Reihenfolge. Um eine schöne Baum-Traversal-Ordnung zu den Ergebnissen zu erhalten, invertiere einfach die Verkettung (setze zuerst die "Quelle").

Zweitens, wenn Sie mit einer teuren Quelle wie EF arbeiten, und Sie wollen ganze Zweige beschränken, ist Damiens Vorschlag, dass Sie das Prädikat injizieren, ein guter und kann immer noch mit Linq gemacht werden.

Schließlich kann es für eine teure Quelle auch gut sein, die interessierenden Felder von jedem Knoten mit einem injizierten Selektor vorzuwählen.

Putting alles zusammen:

public static IEnumerable<R> Flatten<T,R>(this T source, Func<T, IEnumerable<T>> children 
    , Func<T, R> selector 
    , Func<T, bool> branchpredicate = null 
) { 
    if (children == null) throw new ArgumentNullException("children"); 
    if (selector == null) throw new ArgumentNullException("selector"); 
    var pred = branchpredicate ?? (src => true); 
    if (children(source) == null) return new[] { selector(source) }; 

    return new[] { selector(source) } 
     .Concat(children(source) 
     .Where(pred) 
     .SelectMany(c => Flatten(c, children, selector, pred))); 
}