Сгладить дерево (список списков) с одним утверждением?

Благодаря nHibernate некоторые из структур данных, с которыми я работаю, являются списками внутри списков в списках. Так, например, у меня есть объект данных, называемый "категория", который имеет свойство .Children, которое разрешает список категорий... каждый из которых может иметь детей... и т.д. И т.д.

Мне нужно найти способ начать в категории верхнего уровня в этой структуре и получить список или массив или что-то подобное из всех детей во всей структуре - так что все дети всех детей и т.д. и т.д., сплющены в один список.

Я уверен, что это может быть сделано с рекурсией, но я нахожу рекурсивный код болью, чтобы работать, и я убежден, что в .Net 4 должен быть более простой способ использования Linq или somesuch - любые предложения?

Ответы

Ответ 1

Предполагая, что ваш класс категории выглядит примерно так:

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

Я не думаю, что существует "простой" нерекурсивный способ сделать это; если вы просто ищете один вызов метода для его обработки, "простым" способом является запись рекурсивной версии в один вызов метода. Вероятно, есть итеративный способ сделать это, но я предполагаю, что это на самом деле довольно сложно. Это как просить "легкий" способ найти касательную к кривой без использования исчисления.

Во всяком случае, это, вероятно, сделало бы это:

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

Ответ 2

Здесь используется метод расширения, выполняющий задание:

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

Вы можете использовать его следующим образом:

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

В приведенном выше решении происходит обход глубины, если вы хотите пройти по ширине в первый раз, вы можете сделать что-то вроде этого:

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

Он также имеет преимущество в том, что он не рекурсивно...

ОБНОВЛЕНИЕ: Вообще-то, я просто подумал о том, как сделать реверсивный поиск по глубине первым... вот он:

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

Я использую LinkedList<T>, потому что вставки - это операции O (1), а вставки - O (n).

Ответ 3

Если обход ширины в порядке, и вы хотите использовать только короткий нерекурсивный встроенный код (фактически 3 строки), создайте список, инициализированный корневым элементом (-ами), а затем расширьте его одним простым 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);

Ответ 4

Учитывая класс @E.Z.Hart, вы также можете расширить его с помощью вспомогательного метода для этого, который, я думаю, в этом случае проще.

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