Как сгладить дерево через LINQ?

Итак, у меня есть простое дерево:

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

У меня есть IEnumerable . Я хочу получить список всех MyNode (включая объекты внутреннего узла ( Elements )) как один плоский список Where group == 1 . Как это сделать через LINQ?

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

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

Затем вы можете фильтровать по group с помощью Where(...) .

Чтобы заработать «очки за стиль», конвертируйте Flatten в функцию расширения в статическом classе.

 public static IEnumerable Flatten(this IEnumerable e) { return e.SelectMany(c => c.Elements.Flatten()).Concat(e); } 

Чтобы заработать несколько очков за «еще лучший стиль», конвертируйте Flatten в общий метод расширения, который берет дерево и функцию, которая производит потомки:

 public static IEnumerable Flatten( this IEnumerable e, Func> f) { return e.SelectMany(c => f(c).Flatten(f)).Concat(e); } 

Вызвать эту функцию следующим образом:

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

Если вы предпочитаете сплющивание в предварительном порядке, а не в пост-порядке, переходите по сторонам Concat(...) .

Проблема с принятым ответом заключается в том, что он неэффективен, если дерево глубокое. Если дерево очень глубокое, то оно ударяет стек. Вы можете решить проблему, используя явный стек:

 public static IEnumerable Traverse(this MyNode root) { var stack = new Stack(); 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); 

Просто для полноты, вот комбинация ответов от dasblinkenlight и Эрика Липперта. Единица протестирована и все. 🙂

  public static IEnumerable Flatten( this IEnumerable items, Func> getChildren) { var stack = new Stack(); 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 представляет собой stack.Count глубину обработки. Поэтому, учитывая это и используя кортежи значений C # 7.0, мы можем просто изменить объявление метода следующим образом:

 public static IEnumerable<(T Item, int Level)> ExpandWithLevel( this IEnumerable source, Func> elementSelector) 

и утверждение yield :

 yield return (item, stack.Count); 

Затем мы можем реализовать оригинальный метод, применяя простой Select по вышесказанному:

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

Оригинал:

Удивительно, но никто (даже Эрик) не показал «естественный» итерационный порт рекурсивного предзакатного ДПФ, так вот вот он:

  public static IEnumerable Expand( this IEnumerable source, Func> elementSelector) { var stack = new Stack>(); 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(); } } 

В случае, если кто-либо еще это обнаружит, но также должен знать уровень после того, как они сплющили дерево, это расширится на комбинации Konamiman dasblinkenlight и решений Эрика Липперта:

  public static IEnumerable> FlattenWithLevel( this IEnumerable items, Func> getChilds) { var stack = new Stack>(); foreach (var item in items) stack.Push(new Tuple(item, 1)); while (stack.Count > 0) { var current = stack.Pop(); yield return current; foreach (var child in getChilds(current.Item1)) stack.Push(new Tuple(child, current.Item2 + 1)); } } 

Я нашел некоторые небольшие проблемы с ответами, приведенными здесь:

  • Что делать, если исходный список элементов равен NULL?
  • Что делать, если в списке детей есть нулевое значение?

Построенный на предыдущих ответах и ​​придумал следующее:

 public static class IEnumerableExtensions { public static IEnumerable Flatten( this IEnumerable items, Func> getChildren) { if (items == null) yield break; var stack = new Stack(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 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 Children { get; set; } } } 

Самый простой / наиболее понятный способ решения этой проблемы – использовать рекурсивный запрос LINQ. Этот вопрос: выражение рекурсии в LINQ имеет много дискуссий по этому вопросу, и этот конкретный ответ https://stackoverflow.com/a/793531/1550 подробно рассказывает о том, как вы его реализуете.

 void Main() { var allNodes = GetTreeNodes().Flatten(x => x.Elements); allNodes.Dump(); } public static class ExtensionMethods { public static IEnumerable Flatten(this IEnumerable source, Func> childrenSelector = null) { if (source == null) { return new List(); } var list = source; if (childrenSelector != null) { foreach (var item in source) { list = list.Concat(childrenSelector(item).Flatten(childrenSelector)); } } return list; } } IEnumerable 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 Elements; int group = 1; } 

Сочетание ответа Дейва и Ивана Стоева на случай, если вам нужен уровень гнездования, а список сглажен «по порядку» и не отменен, как в ответе, данном Конамиманом.

  public static class HierarchicalEnumerableUtils { private static IEnumerable> ToLeveled(this IEnumerable source, int level) { if (source == null) { return null; } else { return source.Select(item => new Tuple(item, level)); } } public static IEnumerable> FlattenWithLevel(this IEnumerable source, Func> elementSelector) { var stack = new Stack>>(); 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(); } } } 

На основе ответа Konamiman и комментария о том, что заказ неожиданен, вот версия с явным параметром sort:

 public static IEnumerable TraverseAndFlatten(this IEnumerable items, Func> nested, Func orderBy) { var stack = new Stack(); 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»:

 Item_0--Item_00 Item_01 Item_1--Item_10 Item_11 Item_12--Item_120 

будет возвращать элемент и массив int [1,2,0]. Очевидно, что уровень вложенности также доступен, как длина массива.

 public static IEnumerable<(T, int[])> Expand(this IEnumerable source, Func> getChildren) { var stack = new Stack>(); var e = source.GetEnumerator(); List indexes = new List() { -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(); } } 
  • Нерекурсивный алгоритм первого поиска глубины
  • С «N» нет узлов, сколько различных двоичных и двоичных поисковых деревьев возможно?
  • Поиск всех родителей в таблице mysql с одним запросом (Рекурсивный запрос)
  • Как эффективно строить дерево из плоской структуры?
  • Что такое левое-дочернее, правое-единственное представление дерева? Зачем вы его используете?
  • Давайте будем гением компьютера.