Jak spłaszczyć drzewo za pomocą LINQ?


96

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?


1
W jakiej kolejności ma się znajdować spłaszczona lista?
Philip

1
Kiedy węzły przestają mieć węzły podrzędne? Zakładam, że to kiedy Elementsjest zerowy czy pusty?
Adam Houldsworth

może być zduplikowany ze stackoverflow.com/questions/11827569/ ...
Tamir

Najłatwiejszym / najbardziej przejrzystym sposobem rozwiązania tego problemu jest użycie rekursywnego zapytania LINQ. To pytanie: stackoverflow.com/questions/732281/expressing-recursion-in-linq jest przedmiotem wielu dyskusji na ten temat, a ta konkretna odpowiedź zawiera szczegółowe informacje na temat sposobu jego zaimplementowania.
Alvaro Rodriguez

Odpowiedzi:


140

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(...).


@AdamHouldsworth Dzięki za zmianę! Element w wywołaniu Concatpowinien być new[] {e}, a nie new[] {c}(nawet by się tam nie skompilował c).
Sergey Kalinichenko

Nie zgadzam się: kompilacja, testowanie i praca z c. Używanie enie kompiluje się. Możesz również dodać, if (e == null) return Enumerable.Empty<T>();aby poradzić sobie z pustymi listami podrzędnymi.
Adam Houldsworth

1
bardziej jak `public static IEnumerable <T> Flatten <T> (this IEnumerable <T> source, Func <T, IEnumerable <T>> f) {if (source == null) return Enumerable.Empty <T> (); return source.SelectMany (c => f (c) .Flatten (f)). Concat (source); } `
myWallJSON

10
Zauważ, że to rozwiązanie to O (nh), gdzie n to liczba elementów w drzewie, a h to średnia głębokość drzewa. Ponieważ h może znajdować się między O (1) a O (n), jest to między algorytmem O (n) i O (n kwadrat). Są lepsze algorytmy.
Eric Lippert

1
Zauważyłem, że funkcja nie dodaje elementów do spłaszczonej listy, jeśli lista jest typu IEnumerable <baseType>. Możesz rozwiązać ten problem, wywołując następującą funkcję: var res = tree.Flatten (node ​​=> node.Elements.OfType <DerivedType>)
Frank Horemans

125

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

3
@johnnycardy: Jeśli masz zamiar spierać się o coś, być może kod nie jest oczywiście poprawny. Co może sprawić, że będzie jaśniej poprawne?
Eric Lippert

3
@ebramtharwat: dobrze. Możesz przywołać Traversewszystkie elementy. Lub możesz zmodyfikować, Traverseaby wziąć sekwencję i popchnąć wszystkie elementy sekwencji stack. Pamiętaj, stackto „elementy, których jeszcze nie przeszedłem”. Możesz też utworzyć „fikcyjny” korzeń, w którym sekwencja jest jego potomkami, a następnie przejść przez fikcyjny korzeń.
Eric Lippert

2
Jeśli to zrobisz foreach (var child in current.Elements.Reverse()), uzyskasz bardziej oczekiwane spłaszczenie. W szczególności dzieci będą pojawiać się w kolejności, w jakiej się pojawiają, a nie ostatnie dziecko jako pierwsze. W większości przypadków nie powinno to mieć znaczenia, ale w moim przypadku potrzebowałem spłaszczenia w przewidywalnej i oczekiwanej kolejności.
Micah Zoltu

2
@MicahZoltu, możesz uniknąć .Reverse, wymieniając Stack<T>na aQueue<T>
Rubens Farias

2
@MicahZoltu Masz rację co do kolejności, ale problem Reversepolega na tym, że tworzy ona dodatkowe iteratory, czego to podejście ma unikać. @RubensFarias Podstawiając Queuedo Stackwyników szerokości pierwszego przechodzenia.
Jack A.

26

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

3
Aby uniknąć NullReferenceException, var children = getChildren (current); if (dzieci! = null) {foreach (zmienne dziecko w dzieciach) stack.Push (dziecko); }
serg

3
Chciałbym zauważyć, że chociaż powoduje to spłaszczenie listy, zwraca ją w odwrotnej kolejności. Ostatni element staje się pierwszym itd.
Corcus

22

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

Zakładam, że przełączasz się za ekażdym razem, gdy dzwonisz, elementSelectoraby utrzymać zamówienie w przedsprzedaży - jeśli kolejność nie miała znaczenia, czy możesz zmienić funkcję, aby przetwarzała wszystkie eraz uruchomione?
NetMage

@NetMage Chciałem specjalnie zamówić w przedsprzedaży. Przy niewielkiej zmianie może obsługiwać zamówienia pocztowe. Ale najważniejsze jest to, że jest to przejście przez pierwszą głębokość . Dla Breath First przemierzania Chciałbym użyć Queue<T>. W każdym razie chodzi o to, aby zachować mały stos z modułami wyliczającymi, bardzo podobny do tego, co dzieje się w implementacji rekurencyjnej.
Ivan Stoev

@IvanStoev Myślałem, że kod zostanie uproszczony. Wydaje mi się, że użycie tego Stackspowodowałoby zygzakowatą pierwszą szerokość szerokości.
NetMage

Jaki jest sens utrzymywania a Stack<IEnumerator<T>>zamiast a Stack<T>? Moduły wyliczające są zwykle zmiennymi typami wartości i są zwykle implementowane jako maszyny stanu. Spodziewam się więc, że Stack<IEnumerator<T>>rozwiązanie będzie generalnie nieefektywne pod względem pamięci i zwiększy nacisk na moduł odśmiecania pamięci (z powodu pudełkowych typów wartości).
Theodor Zoulias

1
Ivan po bliższym przyjrzeniu się masz rację w obu punktach. Boks jest nieunikniony, a przechowywanie kalkulatora dzieci jest z pewnością lepsze niż przechowywanie wszystkich dzieci. Głosowano za. :-)
Theodor Zoulias

7

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

4

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

2

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


Może Enumerabl.Empty lepiej niż nowa lista?
Frank

1
W rzeczy samej! Zaktualizowano!
Julian

1

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

Fajnie byłoby również móc najpierw określić głębokość lub najpierw szerokość ...
Hugh

1

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

    }

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

1
użycie foreach w rozszerzeniu oznacza, że ​​nie jest to już „opóźnione wykonanie” (chyba że oczywiście użyjesz zwrotu zysku).
Tri Q Tran

0

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

0

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

Cześć @lisz, gdzie wklejasz ten kod? Pojawiają się błędy, takie jak „Modyfikator„ public ”nie jest prawidłowy dla tego elementu”, „Modyfikator„ static ”nie jest prawidłowy dla tego elementu”
Kynao

0

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 .


0

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.