Итак, у меня есть простое дерево:
class MyNode
{
public MyNode Parent;
public IEnumerable<MyNode> Elements;
int group = 1;
}
У меня есть IEnumerable<MyNode>
. Я хочу получить список всего MyNode
(включая объекты внутреннего узла ( Elements
)) в виде одного плоского списка Where
group == 1
. Как это сделать через LINQ?
Elements
ноль или пусто?Ответы:
Сгладить дерево можно так:
IEnumerable<MyNode> Flatten(IEnumerable<MyNode> e) => e.SelectMany(c => Flatten(c.Elements)).Concat(new[] { e });
Затем вы можете фильтровать,
group
используяWhere(...)
.Чтобы заработать несколько «очков за стиль», преобразуйтесь
Flatten
в функцию расширения в статическом классе.public static IEnumerable<MyNode> Flatten(this IEnumerable<MyNode> e) => e.SelectMany(c => c.Elements.Flatten()).Concat(e);
Чтобы заработать больше очков за «еще лучший стиль», преобразуйтесь
Flatten
в универсальный метод расширения, который принимает дерево и функцию, производящую потомков от узла:public static IEnumerable<T> Flatten<T>( this IEnumerable<T> e , Func<T,IEnumerable<T>> f ) => e.SelectMany(c => f(c).Flatten(f)).Concat(e);
Вызовите эту функцию так:
IEnumerable<MyNode> tree = .... var res = tree.Flatten(node => node.Elements);
Если вы предпочитаете сглаживание в предварительном заказе, а не в пост-заказе, поменяйте стороны
Concat(...)
.источник
Concat
должен бытьnew[] {e}
, а неnew[] {c}
(он даже не компилируется сc
ним).c
. Использованиеe
не компилируется. Вы также можете добавить,if (e == null) return Enumerable.Empty<T>();
чтобы справиться с пустыми дочерними списками.Проблема с принятым ответом заключается в том, что он неэффективен, если дерево глубокое. Если дерево очень глубокое, оно сносит стопку. Вы можете решить проблему, используя явный стек:
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); } }
Предполагая, что n узлов в дереве высотой h и коэффициент ветвления значительно меньше n, этот метод составляет O (1) в пространстве стека, O (h) в пространстве кучи и O (n) во времени. Другой приведенный алгоритм - O (h) в стеке, O (1) в куче и O (nh) во времени. Если коэффициент ветвления мал по сравнению с n, тогда h находится между O (lg n) и O (n), что показывает, что наивный алгоритм может использовать опасное количество стека и большое количество времени, если h близко к n.
Теперь, когда у нас есть обход, ваш запрос прост:
root.Traverse().Where(item=>item.group == 1);
источник
Traverse
все элементы. Или вы можете изменить,Traverse
чтобы взять последовательность, и заставить ее вставлять все элементы последовательностиstack
. Помните,stack
это «элементы, которые я еще не прошел». Или вы можете создать «фиктивный» корень, где ваша последовательность является его дочерними элементами, а затем пройти по фиктивному корню.foreach (var child in current.Elements.Reverse())
вы получите более ожидаемое сплющивание. В частности, дети будут появляться в том порядке, в котором они появляются, а не в том порядке, в котором они были последними. В большинстве случаев это не имеет значения, но в моем случае мне нужно, чтобы выравнивание происходило в предсказуемом и ожидаемом порядке..Reverse
путем заменыStack<T>
наQueue<T>
Reverse
том, что он создает дополнительные итераторы, чего этот подход призван избежать. @RubensFarias ПодстановкаQueue
дляStack
результатов в ширину-первых обхода.Для полноты картины вот комбинация ответов от dasblinkenlight и Эрика Липперта. Модульное тестирование и все такое. :-)
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); } }
источник
Обновить:
Для людей, интересующихся уровнем вложенности (глубиной). Одним из преимуществ явной реализации стека перечислителя является то, что в любой момент (и, в частности, при выдаче элемента) он
stack.Count
представляет текущую глубину обработки. Итак, принимая это во внимание и используя кортежи значений C # 7.0, мы можем просто изменить объявление метода следующим образом:public static IEnumerable<(T Item, int Level)> ExpandWithLevel<T>( this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
и
yield
заявление:yield return (item, stack.Count);
Затем мы можем реализовать исходный метод, применив простой
Select
к приведенному выше:public static IEnumerable<T> Expand<T>( this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector) => source.ExpandWithLevel(elementSelector).Select(e => e.Item);
Оригинал:
Удивительно, но никто (даже Эрик) не показал "естественный" итерационный порт рекурсивного ДПФ с предварительным заказом, так что вот он:
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(); } }
источник
e
каждый раз, когда звоните,elementSelector
чтобы поддерживать предварительный заказ - если порядок не имеет значения, не могли бы вы изменить функцию, чтобы обрабатывать всеe
после запуска?Queue<T>
. В любом случае, идея здесь состоит в том, чтобы сохранить небольшой стек с перечислителями, очень похожий на то, что происходит в рекурсивной реализации.Stack
приведет к зигзагообразному обходу в ширину.Stack<IEnumerator<T>>
вместо aStack<T>
? Перечислители обычно представляют собой изменяемые типы значений и обычно реализуются как конечные автоматы. Поэтому я ожидаю, чтоStack<IEnumerator<T>>
решение будет в целом неэффективным с точки зрения памяти и добавит нагрузке на сборщик мусора (из-за типов значений в штучной упаковке).Я обнаружил несколько небольших проблем с ответами, приведенными здесь:
Основываясь на предыдущих ответах, я пришел к следующему:
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); } } }
И юнит-тесты:
[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; } } }
источник
В случае, если кто-то еще обнаружит это, но также должен знать уровень после того, как они сплющили дерево, это расширяет комбинацию Konamiman dasblinkenlight и решений Эрика Липперта:
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)); } }
источник
Другой вариант - создать правильный объектно-ориентированный дизайн.
например попросить
MyNode
вернуть все разложить.Как это:
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()); } }
Теперь вы можете попросить MyNode верхнего уровня получить все узлы.
var flatten = topNode.GetAllNodes();
Если вы не можете редактировать класс, тогда это не вариант. Но в противном случае я думаю, что это может быть предпочтительнее отдельного (рекурсивного) метода LINQ.
Здесь используется LINQ, поэтому я думаю, что этот ответ применим здесь;)
источник
Объединение ответов Дейва и Ивана Стоева на случай, если вам нужен уровень вложенности и список, сплющенный «по порядку», а не перевернутый, как в ответе, данном Konamiman.
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(); } } }
источник
Вот несколько готовых к использованию реализаций, использующих Queue и возвращающих дерево Flatten сначала мне, а затем моим детям.
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; }
источник
Основываясь на ответе Konamiman и комментарии о том, что порядок неожиданный, вот версия с явным параметром сортировки:
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); } }
И пример использования:
var flattened = doc.TraverseAndFlatten(x => x.DependentDocuments, y => y.Document.DocDated).ToList();
источник
Ниже приведен код Ивана Стоева с дополнительной функцией определения индекса каждого объекта на пути. Например, поиск "Item_120":
вернет элемент и массив int [1,2,0]. Очевидно, что уровень вложенности также доступен, как длина массива.
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(); } }
источник
Время от времени я пытаюсь поцарапать эту проблему и разработать собственное решение, которое поддерживает сколь угодно глубокие структуры (без рекурсии), выполняет обход в ширину и не злоупотребляет слишком большим количеством запросов LINQ и не выполняет превентивную рекурсию для детей. Покопавшись в исходниках .NET и попробовав множество решений, я наконец нашел это решение. В итоге он оказался очень близок к ответу Яна Стоева (чей ответ я только что видел), однако в моем не используются бесконечные циклы или необычный поток кода.
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(); } } }
Рабочий пример можно найти здесь .
источник
Большинство ответов, представленных здесь, производят последовательности в глубину или зигзагообразные последовательности. Например, начиная с дерева ниже:
dasblinkenlight в ответ производит эту сплющенную последовательность:
Konamiman в ответ (что обобщается Эрик Липперта ответа ) производит эту сплюснутую последовательность:
Ответ Ивана Стоева дает эту уплощенную последовательность:
Если вы заинтересованы в широте первой последовательности , как это:
... тогда это решение для вас:
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); } }
Разница в реализации в основном заключается в использовании
Queue
вместоStack
. Фактической сортировки не происходит.Внимание: эта реализация далека от оптимальной с точки зрения эффективности использования памяти, поскольку большой процент от общего числа элементов в конечном итоге будет сохранен во внутренней очереди во время перечисления.
Stack
обходы на основе дерева намного эффективнее с точки зрения использования памяти, чемQueue
реализации на основе.источник