Bagaimana cara meratakan pohon melalui LINQ?

Jadi saya punya pohon sederhana:

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

Saya punya IEnumerable<MyNode>. Saya ingin mendapatkan daftar semua MyNode(termasuk objek simpul dalam ( Elements)) sebagai satu daftar datar Where group == 1. Bagaimana cara melakukan hal seperti itu melalui LINQ?

Anda bisa meratakan pohon seperti ini:

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

Anda kemudian dapat memfilter dengan groupmenggunakan Where(...).

Untuk mendapatkan beberapa "poin untuk gaya", konversikan Flattenke fungsi ekstensi di kelas statis.

public static IEnumerable<MyNode> Flatten(this IEnumerable<MyNode> e) =>
    e.SelectMany(c => c.Elements.Flatten()).Concat(e);

Untuk mendapatkan lebih banyak poin untuk "gaya yang lebih baik", konversikan Flattenke metode ekstensi umum yang menggunakan pohon dan fungsi yang menghasilkan turunan dari node:

public static IEnumerable<T> Flatten<T>(
    this IEnumerable<T> e
,   Func<T,IEnumerable<T>> f
) => e.SelectMany(c => f(c).Flatten(f)).Concat(e);

Panggil fungsi ini seperti ini:

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

Jika Anda lebih suka meratakan dalam pre-order daripada post-order, ganti di sekitar sisi Concat(...).

Masalah dengan jawaban yang diterima adalah tidak efisien jika pohonnya dalam. Jika pohonnya sangat dalam maka tumpukan itu akan meledak. Anda dapat memecahkan masalah dengan menggunakan tumpukan eksplisit:

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

Dengan asumsi n node dalam pohon dengan tinggi h dan faktor percabangan jauh lebih kecil dari n, metode ini adalah O (1) dalam ruang stack, O (h) dalam ruang heap dan O (n) dalam waktu. Algoritma lain yang diberikan adalah O (h) di stack, O (1) di heap dan O (nh) di waktu. Jika faktor percabangan kecil dibandingkan dengan n maka h berada di antara O (lg n) dan O (n), yang menggambarkan bahwa algoritma naïve dapat menggunakan jumlah stack yang berbahaya dan waktu yang banyak jika h mendekati n.

Sekarang setelah kami memiliki traversal, kueri Anda sangat mudah:

root.Traverse().Where(item=>item.group == 1);

Sekadar kelengkapan, berikut kombinasi jawaban dari dasblinkenlight dan Eric Lippert. Unit diuji dan semuanya. :-)

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

Memperbarui:

Untuk orang yang tertarik dengan level nesting (kedalaman). Salah satu hal baik tentang implementasi tumpukan enumerator eksplisit adalah bahwa setiap saat (dan khususnya saat menghasilkan elemen) stack.Countmewakili kedalaman pemrosesan saat ini. Jadi dengan mempertimbangkan hal ini dan memanfaatkan tupel nilai C # 7.0, kita cukup mengubah deklarasi metode sebagai berikut:

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

dan yieldpernyataan:

yield return (item, stack.Count);

Kemudian kita dapat mengimplementasikan metode asli dengan menerapkan simple Selectdi atas:

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

Asli:

Anehnya tidak ada (bahkan Eric) yang menunjukkan port berulang "alami" dari DFT pra-order rekursif, jadi ini dia:

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

Saya menemukan beberapa masalah kecil dengan jawaban yang diberikan di sini:

• Bagaimana jika daftar awal item adalah null?
• Bagaimana jika ada nilai nol dalam daftar anak?

Dibangun di atas jawaban sebelumnya dan muncul dengan yang berikut:

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

Dan tes unit:

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

Jika ada orang lain yang menemukan ini, tetapi juga perlu mengetahui level setelah mereka meratakan pohon, ini memperluas kombinasi dasblinkenlight dan solusi Eric Lippert dari Konamiman:

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

Pilihan lain adalah memiliki desain OO yang tepat.

mis. minta MyNodeuntuk mengembalikan semua rata.

Seperti ini:

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

Sekarang Anda dapat meminta MyNode tingkat atas untuk mendapatkan semua node.

var flatten = topNode.GetAllNodes();

Jika Anda tidak dapat mengedit kelas, ini bukanlah pilihan. Tetapi sebaliknya, saya pikir ini bisa lebih disukai dari metode LINQ (rekursif) terpisah.

Ini menggunakan LINQ, Jadi saya pikir jawaban ini dapat diterapkan di sini;)

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

Menggabungkan jawaban Dave dan Ivan Stoev seandainya Anda membutuhkan level bersarang dan daftarnya diratakan "dalam urutan" dan tidak terbalik seperti pada jawaban yang diberikan oleh 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();
            }
        }
    }

Berdasarkan jawaban Konamiman, dan komentar bahwa urutannya tidak terduga, berikut adalah versi dengan parameter sortir eksplisit:

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

Dan contoh penggunaan:

var flattened = doc.TraverseAndFlatten(x => x.DependentDocuments, y => y.Document.DocDated).ToList();

Di bawah ini adalah kode Ivan Stoev dengan fitur tambahan yang memberi tahu indeks setiap objek di jalur. Misalnya, telusuri "Item_120":

Item_0--Item_00
        Item_01

Item_1--Item_10
        Item_11
        Item_12--Item_120

akan mengembalikan item dan array int [1,2,0]. Jelas, level bersarang juga tersedia, sebagai panjang array.

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

Di sini beberapa implementasi siap menggunakan menggunakan Antrian dan mengembalikan pohon Ratakan saya terlebih dahulu dan kemudian anak-anak saya.

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

    }

Sesekali saya mencoba untuk mengatasi masalah ini dan merancang solusi saya sendiri yang mendukung struktur dalam sewenang-wenang (tidak ada rekursi), melakukan traversal pertama yang luas, dan tidak menyalahgunakan terlalu banyak kueri LINQ atau melakukan rekursi lebih dulu pada anak-anak. Setelah menggali di sekitar sumber .NET dan mencoba banyak solusi, saya akhirnya menemukan solusi ini. Itu akhirnya menjadi sangat dekat dengan jawaban Ian Stoev (yang jawabannya baru saja saya lihat), namun saya tidak menggunakan loop tak terbatas atau memiliki aliran kode yang tidak biasa.

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

Contoh yang berfungsi dapat ditemukan di sini .