Spłaszczyć drzewo (listę list) jednym stwierdzeniem?

Question

Spłaszczyć drzewo (listę list) jednym stwierdzeniem?

Dzięki nHibernate niektóre struktury danych, z którymi pracuję, to listy wewnątrz list. Więc na przykład mam obiekt danych o nazwie "Kategoria", który ma .Właściwość Children, która usuwa listę kategorii ... każdy z nich może mieć dzieci ... i tak dalej i tak dalej.

Muszę znaleźć sposób, aby zacząć od kategorii najwyższego poziomu w tej strukturze i uzyskać listę lub tablicę lub coś podobnego wszystkich dzieci w całej strukturze - więc wszystkie dzieci wszystkich dzieci itp. itd., spłaszczone w jednej liście.

Jestem pewien, że można to zrobić z rekurencją, ale uważam, że rekurencyjny kod to ból do pracy, i jestem przekonany, że musi być prostszy sposób w. Net 4 używając Linq lub coś podobnego-jakieś sugestie ?

21

.net flatten tree

Author: g t, 2010-10-11

Source

4 answers

Oto metoda rozszerzenia, która wykonuje zadanie:

// Depth-first traversal, recursive
public static IEnumerable<T> Flatten<T>(
        this IEnumerable<T> source,
        Func<T, IEnumerable<T>> childrenSelector)
{
    foreach (var item in source)
    {
        yield return item;
        foreach (var child in childrenSelector(item).Flatten(childrenSelector))
        {
            yield return child;
        }
    }
}

Możesz go użyć Tak:

foreach(var category in categories.Flatten(c => c.Children))
{
    ...
}

Powyższe rozwiązanie wykonuje pierwszy Trawers głębokości, jeśli chcesz pierwszy Trawers szerokości, możesz zrobić coś takiego:

// Breadth-first traversal, non-recursive
public static IEnumerable<T> Flatten2<T>(
        this IEnumerable<T> source,
        Func<T, IEnumerable<T>> childrenSelector)
{
    var queue = new Queue<T>(source);
    while (queue.Count > 0)
    {
        var item = queue.Dequeue();
        yield return item;
        foreach (var child in childrenSelector(item))
        {
            queue.Enqueue(child);
        }
    }
}

Ma również tę zaletę, że nie jest rekurencyjny...

UPDATE: właściwie, myślałem o sposobie, aby głębokość-pierwszy Trawers nie rekurencyjny... tutaj jest:

// Depth-first traversal, non-recursive
public static IEnumerable<T> Flatten3<T>(
        this IEnumerable<T> source,
        Func<T, IEnumerable<T>> childrenSelector)
{
    LinkedList<T> list = new LinkedList<T>(source);
    while (list.Count > 0)
    {
        var item = list.First.Value;
        yield return item;
        list.RemoveFirst();
        var node = list.First;
        foreach (var child in childrenSelector(item))
        {
            if (node != null)
                list.AddBefore(node, child);
            else
                list.AddLast(child);
        }
    }
}

Używam LinkedList<T> ponieważ wstawki są O (1) operacje, natomiast wstawki do a List<T> to O (n).

36

Author: Thomas Levesque,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-11-18 16:45:17

Biorąc pod uwagę klasę, o której wspomina @E. Z. Hart, można ją również rozszerzyć za pomocą metody pomocniczej, która moim zdaniem jest prostsza w tym przypadku.

public class Category
{
    public string Name { get; set; }

    public List<Category> Children { get; set; }

    public IEnumerable<Category> AllChildren()
    {
        yield return this;
        foreach (var child in Children)
        foreach (var granChild in child.AllChildren())
        {
            yield return granChild;
        }
    }   
}

1

Author: Ogglas,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-09-14 19:33:38

Jeśli width-first traversal jest OK i chcesz użyć tylko krótkiego, Nie rekurencyjnego kodu inline(w rzeczywistości 3 linie), Utwórz listę zainicjalizowaną za pomocą głównego elementu (- ów), a następnie rozszerz ją o jedną prostą pętlę for:

// your data object class looks like:
public class DataObject
{
  public List<DataObject> Children { get; set; }
  ...
}

...

// given are some root elements
IEnumerable<DataObject> rootElements = ...

// initialize the flattened list with the root elements
var result = new List<DataObject>(rootElements);
// extend the flattened list by one simple for-loop, 
// please note that result.Count may increase after every iteration!
for (int index = 0; index < result.Count; index++)
  result.AddRange(result[index].Children);

1

Author: Paul,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-01-19 09:20:36

score 12 · Accepted Answer

Zakładając, że twoja klasa kategorii wygląda mniej więcej tak:

 public class Category
 {
   public string Name { get; set; }
   public List<Category> Children { get; set; }
 }

Nie sądzę, że istnieje "łatwy" Nie-rekurencyjny sposób, aby to zrobić; jeśli po prostu szukasz pojedynczego wywołania metody, aby go obsłużyć, "łatwy" sposób jest zapisanie wersji rekurencyjnej w jednym wywołaniu metody. Prawdopodobnie istnieje na to powtarzalny sposób, ale zgaduję, że jest to dość skomplikowane. To tak, jakby zapytać "łatwy" sposób, aby znaleźć styczną do krzywej bez użycia rachunku.

W każdym razie, to prawdopodobnie zrób to:

public static List<Category> Flatten(Category root) {

    var flattened = new List<Category> {root};

    var children = root.Children;

    if(children != null)
    {
        foreach (var child in children)
        {
            flattened.AddRange(Flatten(child));
        }
    }

    return flattened;
}