次のようにツリーを平坦化できます。
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(...)ます。
受け入れられた答えの問題は、ツリーが深い場合に非効率的であるということです。ツリーが非常に深い場合、スタックが吹き飛ばされます。明示的なスタックを使用して問題を解決できます。
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);
}
}
高さ h のツリーに n 個のノードがあり、分岐係数が 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);
アップデート：
入れ子のレベル（深さ）に興味がある人向け。明示的な列挙子スタックの実装の良い点の 1 つは、いつでも (特に要素を生成するとき) が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次に、上記にsimple を適用して元のメソッドを実装できます。
public static IEnumerable<T> Expand<T>(
this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector) =>
source.ExpandWithLevel(elementSelector).Select(e => e.Item);
オリジナル：
驚くべきことに、誰も (Eric でさえも) 再帰的な事前注文 DFT の「自然な」反復ポートを示していません。
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();
}
}
他の誰かがこれを見つけたが、ツリーを平坦化した後のレベルを知る必要がある場合、これはコナミマンの dasblinkenlight と Eric Lippert のソリューションの組み合わせを拡張します。
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));
}
}
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;
}
以下は、パス内のすべてのオブジェクトのインデックスを伝える追加機能を備えた Ivan Stoev のコードです。たとえば、「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<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();
}
}