Jak spłaszczyć drzewo za pomocą LINQ?

Mam więc proste drzewo:

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

Mam IEnumerable<MyNode>. Chcę uzyskać listę wszystkich MyNode(w tym obiektów węzłów wewnętrznych ( Elements)) jako jedną płaską listę Where group == 1. Jak to zrobić przez LINQ?

Możesz spłaszczyć drzewo w ten sposób:

IEnumerable<MyNode> Flatten(IEnumerable<MyNode> e) =>
    e.SelectMany(c => Flatten(c.Elements)).Concat(new[] { e });

Następnie możesz filtrować za grouppomocą Where(...).

Aby zdobyć punkty za styl, przekonwertuj Flattenna funkcję rozszerzającą w klasie statycznej.

public static IEnumerable<MyNode> Flatten(this IEnumerable<MyNode> e) =>
    e.SelectMany(c => c.Elements.Flatten()).Concat(e);

Aby zdobyć więcej punktów za „jeszcze lepszy styl”, przekonwertuj Flattensię na ogólną metodę rozszerzenia, która pobiera drzewo i funkcję, która tworzy potomków z węzła:

public static IEnumerable<T> Flatten<T>(
    this IEnumerable<T> e
,   Func<T,IEnumerable<T>> f
) => e.SelectMany(c => f(c).Flatten(f)).Concat(e);

Wywołaj tę funkcję w ten sposób:

IEnumerable<MyNode> tree = ....
var res = tree.Flatten(node => node.Elements);

Jeśli wolisz spłaszczanie w zamówieniu przedpremierowym, a nie po zamówieniu, przełączaj między bokami pliku Concat(...).

Problem z przyjętą odpowiedzią polega na tym, że jest ona nieefektywna, jeśli drzewo jest głębokie. Jeśli drzewo jest bardzo głębokie, wysadza stos. Możesz rozwiązać problem, 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 hi współczynnik rozgałęzienia znacznie mniejszy niż n, metoda ta to O (1) w przestrzeni stosu, O (h) w przestrzeni sterty i O (n) w czasie. Inny podany algorytm to O (h) na stosie, O (1) na stercie i O (nh) w czasie. Jeśli współczynnik rozgałęzienia jest mały w porównaniu z n, to h jest między O (lg n) a O (n), co pokazuje, że naiwny algorytm może używać niebezpiecznej ilości stosu i dużej ilości czasu, jeśli h jest bliskie n.

Teraz, gdy mamy przemierzanie, Twoje zapytanie jest proste:

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

Aby uzyskać kompletność, oto połączenie odpowiedzi od dasblinkenlight i Erica Lipperta. Jednostka przetestowana i wszystko. :-)

 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);
     }
 }

Aktualizacja:

Dla osób zainteresowanych poziomem zagnieżdżenia (głębokości). Jedną z dobrych rzeczy w jawnej implementacji stosu modułu wyliczającego jest to, że w dowolnym momencie (aw szczególności podczas generowania elementu) stack.Countreprezentuje aktualną głębokość przetwarzania. Biorąc to pod uwagę i wykorzystując krotki 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 yieldoświadczenie:

yield return (item, stack.Count);

Następnie możemy zaimplementować oryginalną metodę, stosując prostą Selectna powyższym:

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

Oryginał:

Zaskakująco nikt (nawet Eric) nie pokazał „naturalnego” iteracyjnego portu rekurencyjnego DFT w przedsprzedaży, więc oto jest:

    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 drobnych problemów z odpowiedziami podanymi tutaj:

• Co się stanie, jeśli początkowa lista pozycji jest pusta?
• A co, jeśli lista dzieci zawiera wartość null?

Oparty 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);
        }
    }
}

A 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; }
    }
}

W przypadku, gdy ktoś inny to znajdzie, ale musi również znać poziom po spłaszczeniu drzewa, to rozszerza się na kombinację rozwiązań dasblinkenlight i Erica Lipperta firmy Konamiman:

    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));
        }
    }

Naprawdę inną opcją jest odpowiedni projekt OO.

np. poproś MyNodeo zwrócenie wszystkich spłaszczonych.

Lubię to:

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 pobranie wszystkich węzłów.

var flatten = topNode.GetAllNodes();

Jeśli nie możesz edytować klasy, nie ma takiej opcji. Ale w przeciwnym razie myślę, że może to być preferowane z oddzielnej (rekurencyjnej) metody LINQ.

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

Połączenie odpowiedzi Dave'a i Ivana Stoeva na wypadek, gdybyś potrzebował poziomu zagnieżdżenia i listy spłaszczonej „w kolejności”, 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łaszcz 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);
            }
        }

    }

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;
}

Opierając się na odpowiedzi Konamiman i komentarzu, że kolejność jest nieoczekiwana, oto wersja z wyraźnym parametrem 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 Ivana Stoeva z dodatkową funkcją informowania o indeksie każdego obiektu na ścieżce. Na przykład wyszukiwanie „Przedmiot_120”:

Item_0--Item_00
        Item_01

Item_1--Item_10
        Item_11
        Item_12--Item_120

zwróci element i int array [1, 2, 0]. Oczywiście dostępny jest również poziom zagnieżdżenia, 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 próbuję zarysować ten problem i opracować własne rozwiązanie, które obsługuje dowolnie głębokie struktury (bez rekursji), wykonuje pierwsze przejście wszerz i nie nadużywa zbyt wielu zapytań LINQ ani nie wykonuje prewencyjnie rekursji na dzieciach. Po przekopaniu się w źródłach .NET i wypróbowaniu wielu rozwiązań, w końcu znalazłem to rozwiązanie. Skończyło się na tym, że było bardzo blisko odpowiedzi Iana Stoeva (którego odpowiedź widziałem dopiero teraz), jednak moja nie wykorzystuje nieskończonych pętli ani nie ma niezwykłego przepływu 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 roboczy można znaleźć tutaj .

Większość przedstawionych tutaj odpowiedzi to sekwencje zstępujące w głąb lub zygzakowate. Na przykład zaczynając od poniższego drzewa:

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

Odpowiedź dasblinkenlight daje następującą spłaszczoną sekwencję:

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

Konamiman za odpowiedź (która uogólnia Eric Lippert na odpowiedź ) produkuje ten spłaszczony sekwencję:

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

Ivan Stoev za odpowiedź produkuje ten spłaszczony sekwencję:

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

Jeśli interesuje Cię następująca sekwencja wszerz :

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 w zasadzie na użyciu a Queuezamiast a Stack. Nie ma faktycznego sortowania.

Uwaga: ta implementacja jest daleka od optymalnej 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-oparte drzewa-przechodzenie są znacznie bardziej wydajne pod względem użycia pamięci niż Queueimplementacje oparte na -base.