Jak spłaszczyć drzewo przez LINQ?

Problem z zaakceptowaną odpowiedzią polega na tym, że jest ona nieefektywna, jeśli drzewo jest głębokie. Jeśli drzewo jest Bardzo Głębokie, to wieje stos. Problem można rozwiązać używając jawnego stosu:

public static IEnumerable<MyNode> Traverse(this MyNode root)
{
    var stack = new Stack<MyNode>();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach(var child in current.Elements)
            stack.Push(child);
    }
}

Zakładając n węzłów w drzewie o wysokości h i współczynniku rozgałęzienia znacznie mniejszym niż n, metoda ta wynosi O(1) w przestrzeni stosu, O(h) w przestrzeni stosu i O(N) w czasie. Innym podanym algorytmem jest O (h) w stosie, o(1) w stercie i o(nh) w czasie. Jeśli współczynnik rozgałęzienia jest mały w porównaniu do n, h znajduje się pomiędzy O (lg n) I O (N), co ilustruje, że naiwny algorytm może użyć niebezpiecznej ilości stosu i dużej ilości czasu, jeśli H jest blisko n.

Teraz, gdy mamy Trawers, Twoje zapytanie jest proste:

root.Traverse().Where(item=>item.group == 1);

Dla kompletności, oto kombinacja odpowiedzi dasblinkenlight i Eric Lippert. Jednostka testowana i w ogóle. :-)

 public static IEnumerable<T> Flatten<T>(
        this IEnumerable<T> items,
        Func<T, IEnumerable<T>> getChildren)
 {
     var stack = new Stack<T>();
     foreach(var item in items)
         stack.Push(item);

     while(stack.Count > 0)
     {
         var current = stack.Pop();
         yield return current;

         var children = getChildren(current);
         if (children == null) continue;

         foreach (var child in children) 
            stack.Push(child);
     }
 }

Update:

Dla osób zainteresowanych poziomem zagnieżdżenia (głębią). Jedną z dobrych rzeczy na temat implementacji stosu jawnego enumeratora jest to, że w dowolnym momencie (a w szczególności podczas otrzymywania elementu) stack.Count reprezentuje aktualnie przetwarzaną głębokość. Biorąc to pod uwagę i używając krotek wartości C#7.0, możemy po prostu zmienić deklarację metody w następujący sposób:

public static IEnumerable<(T Item, int Level)> ExpandWithLevel<T>(
    this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)

I yield wypowiedź:

yield return (item, stack.Count);

Wtedy możemy zaimplementować oryginał metoda poprzez zastosowanie prostej Select na powyższym:

public static IEnumerable<T> Expand<T>(
    this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector) =>
    source.ExpandWithLevel(elementSelector).Select(e => e.Item);

Oryginalny:

    public static IEnumerable<T> Expand<T>(
        this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = source.GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return item;
                    var elements = elementSelector(item);
                    if (elements == null) continue;
                    stack.Push(e);
                    e = elements.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }

Znalazłem kilka małych problemów z odpowiedziami podanymi tutaj:

• co jeśli początkowa lista elementów jest null?
• co jeśli na liście dzieci znajduje się wartość null?

Zbudowany na poprzednich odpowiedziach i wymyślił:

public static class IEnumerableExtensions
{
    public static IEnumerable<T> Flatten<T>(
        this IEnumerable<T> items, 
        Func<T, IEnumerable<T>> getChildren)
    {
        if (items == null)
            yield break;

        var stack = new Stack<T>(items);
        while (stack.Count > 0)
        {
            var current = stack.Pop();
            yield return current;

            if (current == null) continue;

            var children = getChildren(current);
            if (children == null) continue;

            foreach (var child in children)
                stack.Push(child);
        }
    }
}

I testy jednostkowe:

[TestClass]
public class IEnumerableExtensionsTests
{
    [TestMethod]
    public void NullList()
    {
        IEnumerable<Test> items = null;
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(0, flattened.Count());
    }
    [TestMethod]
    public void EmptyList()
    {
        var items = new Test[0];
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(0, flattened.Count());
    }
    [TestMethod]
    public void OneItem()
    {
        var items = new[] { new Test() };
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(1, flattened.Count());
    }
    [TestMethod]
    public void OneItemWithChild()
    {
        var items = new[] { new Test { Id = 1, Children = new[] { new Test { Id = 2 } } } };
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(2, flattened.Count());
        Assert.IsTrue(flattened.Any(i => i.Id == 1));
        Assert.IsTrue(flattened.Any(i => i.Id == 2));
    }
    [TestMethod]
    public void OneItemWithNullChild()
    {
        var items = new[] { new Test { Id = 1, Children = new Test[] { null } } };
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(2, flattened.Count());
        Assert.IsTrue(flattened.Any(i => i.Id == 1));
        Assert.IsTrue(flattened.Any(i => i == null));
    }
    class Test
    {
        public int Id { get; set; }
        public IEnumerable<Test> Children { get; set; }
    }
}

Jeśli ktoś inny to znajdzie, ale musi znać poziom po spłaszczeniu drzewa, rozszerza się to na kombinację rozwiązań Konamimana dasblinkenlight i Erica Lipperta:]}

    public static IEnumerable<Tuple<T, int>> FlattenWithLevel<T>(
            this IEnumerable<T> items,
            Func<T, IEnumerable<T>> getChilds)
    {
        var stack = new Stack<Tuple<T, int>>();
        foreach (var item in items)
            stack.Push(new Tuple<T, int>(item, 1));

        while (stack.Count > 0)
        {
            var current = stack.Pop();
            yield return current;
            foreach (var child in getChilds(current.Item1))
                stack.Push(new Tuple<T, int>(child, current.Item2 + 1));
        }
    }

Inną opcją jest posiadanie odpowiedniego projektu OO.

Np. poproś {[2] } o zwrócenie wszystkich spłaszczonych.

Tak:

class MyNode
{
    public MyNode Parent;
    public IEnumerable<MyNode> Elements;
    int group = 1;

    public IEnumerable<MyNode> GetAllNodes()
    {
        if (Elements == null)
        {
            return Enumerable.Empty<MyNode>(); 
        }

        return Elements.SelectMany(e => e.GetAllNodes());
    }
}

Teraz możesz poprosić MyNode najwyższego poziomu o uzyskanie wszystkich węzłów.

var flatten = topNode.GetAllNodes();

Jeśli nie możesz edytować klasy, to nie jest to opcja. Ale poza tym, myślę, że może być to preferowana oddzielna (rekurencyjna) metoda LINQ.

To używa LINQ, więc myślę, że ta odpowiedź ma zastosowanie tutaj;)

Połączenie odpowiedzi Dave 'a i Ivana Stoeva w przypadku, gdy potrzebujesz poziomu zagnieżdżenia i listy spłaszczonej "w porządku", a nie odwróconej, jak w odpowiedzi udzielonej przez Konamimana.

 public static class HierarchicalEnumerableUtils
    {
        private static IEnumerable<Tuple<T, int>> ToLeveled<T>(this IEnumerable<T> source, int level)
        {
            if (source == null)
            {
                return null;
            }
            else
            {
                return source.Select(item => new Tuple<T, int>(item, level));
            }
        }

        public static IEnumerable<Tuple<T, int>> FlattenWithLevel<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
        {
            var stack = new Stack<IEnumerator<Tuple<T, int>>>();
            var leveledSource = source.ToLeveled(0);
            var e = leveledSource.GetEnumerator();
            try
            {
                while (true)
                {
                    while (e.MoveNext())
                    {
                        var item = e.Current;
                        yield return item;
                        var elements = elementSelector(item.Item1).ToLeveled(item.Item2 + 1);
                        if (elements == null) continue;
                        stack.Push(e);
                        e = elements.GetEnumerator();
                    }
                    if (stack.Count == 0) break;
                    e.Dispose();
                    e = stack.Pop();
                }
            }
            finally
            {
                e.Dispose();
                while (stack.Count != 0) stack.Pop().Dispose();
            }
        }
    }

Oto kilka gotowych do użycia implementacji za pomocą kolejki i zwracania drzewa spłaszczonego najpierw mnie, a potem moje dzieci.

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> items, 
    Func<T,IEnumerable<T>> getChildren)
    {
        if (items == null)
            yield break;

        var queue = new Queue<T>();

        foreach (var item in items) {
            if (item == null)
                continue;

            queue.Enqueue(item);

            while (queue.Count > 0) {
                var current = queue.Dequeue();
                yield return current;

                if (current == null)
                    continue;

                var children = getChildren(current);
                if (children == null)
                    continue;

                foreach (var child in children)
                    queue.Enqueue(child);
            }
        }

    }

Większość prezentowanych tutaj odpowiedzi tworzy depth-first lub sekwencje zig-zag. Na przykład zaczynając od drzewa poniżej:

        1                   2 
       / \                 / \
      /   \               /   \
     /     \             /     \
    /       \           /       \
   11       12         21       22
  / \       / \       / \       / \
 /   \     /   \     /   \     /   \
111 112   121 122   211 212   221 222

Dasblinkenlight ' s odpowiedź daje tę spłaszczoną sekwencję:

111, 112, 121, 122, 11, 12, 211, 212, 221, 222, 21, 22, 1, 2

Odpowiedź Konamimana (która uogólnia odpowiedź Erica Lipperta } ) tworzy tę spłaszczoną sekwencję:

2, 22, 222, 221, 21, 212, 211, 1, 12, 122, 121, 11, 112, 111

Odpowiedź Iwana Stojewa daje tę spłaszczoną sekwencję:

1, 11, 111, 112, 12, 121, 122, 2, 21, 211, 212, 22, 221, 222

Jeśli jesteś zainteresowany szerokość-pierwsza Sekwencja jak ta:

1, 2, 11, 12, 21, 22, 111, 112, 121, 122, 211, 212, 221, 222

...to jest rozwiązanie dla Ciebie:

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source,
    Func<T, IEnumerable<T>> childrenSelector)
{
    var queue = new Queue<T>(source);
    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        yield return current;
        var children = childrenSelector(current);
        if (children == null) continue;
        foreach (var child in children) queue.Enqueue(child);
    }
}

Różnica w implementacji polega zasadniczo na użyciu Queue zamiast Stack. Nie ma faktycznego sortowania.

Uwaga: Ta implementacja nie jest optymalna pod względem wydajności pamięci, ponieważ duży procent całkowitej liczby elementów zostanie zapisany w wewnętrznej kolejce podczas wyliczania. Stack-na podstawie implementacje tree-traversals są znacznie bardziej wydajne pod względem wykorzystania pamięci niż implementacje oparte na Queue.

void Main()
{
    var allNodes = GetTreeNodes().Flatten(x => x.Elements);

    allNodes.Dump();
}

public static class ExtensionMethods
{
    public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector = null)
    {
        if (source == null)
        {
            return new List<T>();
        }

        var list = source;

        if (childrenSelector != null)
        {
            foreach (var item in source)
            {
                list = list.Concat(childrenSelector(item).Flatten(childrenSelector));
            }
        }

        return list;
    }
}

IEnumerable<MyNode> GetTreeNodes() {
    return new[] { 
        new MyNode { Elements = new[] { new MyNode() }},
        new MyNode { Elements = new[] { new MyNode(), new MyNode(), new MyNode() }}
    };
}

class MyNode
{
    public MyNode Parent;
    public IEnumerable<MyNode> Elements;
    int group = 1;
}

Bazując na odpowiedzi Konamimana i komentarzu, że zamówienie jest nieoczekiwane, oto wersja z wyraźnym param sortowania:

public static IEnumerable<T> TraverseAndFlatten<T, V>(this IEnumerable<T> items, Func<T, IEnumerable<T>> nested, Func<T, V> orderBy)
{
    var stack = new Stack<T>();
    foreach (var item in items.OrderBy(orderBy))
        stack.Push(item);

    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;

        var children = nested(current).OrderBy(orderBy);
        if (children == null) continue;

        foreach (var child in children)
            stack.Push(child);
    }
}

I przykładowe użycie:

var flattened = doc.TraverseAndFlatten(x => x.DependentDocuments, y => y.Document.DocDated).ToList();

Poniżej znajduje się kod Iwana Stojewa z dodatkową funkcją informującą o indeksie każdego obiektu na ścieżce. Np. wyszukaj "Item_120":

Item_0--Item_00
        Item_01

Item_1--Item_10
        Item_11
        Item_12--Item_120

Zwróci element i tablicę int [1,2,0]. Oczywiście, poziom zagnieżdżania jest również dostępny, jako długość tablicy.

public static IEnumerable<(T, int[])> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> getChildren) {
    var stack = new Stack<IEnumerator<T>>();
    var e = source.GetEnumerator();
    List<int> indexes = new List<int>() { -1 };
    try {
        while (true) {
            while (e.MoveNext()) {
                var item = e.Current;
                indexes[stack.Count]++;
                yield return (item, indexes.Take(stack.Count + 1).ToArray());
                var elements = getChildren(item);
                if (elements == null) continue;
                stack.Push(e);
                e = elements.GetEnumerator();
                if (indexes.Count == stack.Count)
                    indexes.Add(-1);
                }
            if (stack.Count == 0) break;
            e.Dispose();
            indexes[stack.Count] = -1;
            e = stack.Pop();
        }
    } finally {
        e.Dispose();
        while (stack.Count != 0) stack.Pop().Dispose();
    }
}

Od czasu do czasu staram się zarysować ten problem i opracować własne rozwiązanie, które obsługuje arbitralnie głębokie struktury (bez rekurencji), wykonuje szerokość pierwszego przejścia i nie nadużywa zbyt wielu zapytań LINQ lub prewencyjnie wykonuje rekurencję na dzieciach. Po grzebaniu w źródle . NET i wypróbowaniu wielu rozwiązań, w końcu wymyśliłem to rozwiązanie. Skończyło się na tym, że jest bardzo blisko odpowiedzi Iana Stoeva (którego odpowiedź widziałem dopiero teraz), jednak moja Nie używaj nieskończonych pętli lub mieć nietypowy przepływ kodu.

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> source,
    Func<T, IEnumerable<T>> fnRecurse)
{
    if (source != null)
    {
        Stack<IEnumerator<T>> enumerators = new Stack<IEnumerator<T>>();
        try
        {
            enumerators.Push(source.GetEnumerator());
            while (enumerators.Count > 0)
            {
                var top = enumerators.Peek();
                while (top.MoveNext())
                {
                    yield return top.Current;

                    var children = fnRecurse(top.Current);
                    if (children != null)
                    {
                        top = children.GetEnumerator();
                        enumerators.Push(top);
                    }
                }

                enumerators.Pop().Dispose();
            }
        }
        finally
        {
            while (enumerators.Count > 0)
                enumerators.Pop().Dispose();
        }
    }
}

Przykład pracy można znaleźć tutaj .