如何循环递归数据类型

Question

我将分层数据读入递归数据结构。

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

所以它类似于一棵树。我的问题是，我不知道如何遍历所有元素或找到具有特定名称的内部元素。由于它可能非常 complex/deep 我无法真正使用嵌套循环，因为我不知道它会变得多深。

我怎样才能对这种结构中的所有元素进行循环？

Answer 1

void RecursiveMethod(Items items)
{
    if (items.Children != null)
    {
        foreach (Items i in items.Children)
        {
            RecursiveMethod(i);
        }
    }
    if (items.Name == "YourName")
    {
        // Do your stuff..
    }
}

Answer 2

您需要一些遍历算法实现。
有几个，要么是递归的，要么是非递归的。选择哪一个取决于您的特定用例。

例如，一种非递归的惰性宽度遍历：

public static class TreeVisitor
{
    public static IEnumerable<TNodeType> WidthTraversal<TNodeType>(TNodeType root, Func<TNodeType, IEnumerable<TNodeType>> getChildNodesFunc)
        where TNodeType : class
    {
        if (root == null)
        {
            throw new ArgumentNullException(nameof(root));
        }

        if (getChildNodesFunc == null)
        {
            throw new ArgumentNullException(nameof(getChildNodesFunc));
        }

        var visited = new HashSet<TNodeType>();
        var queue = new Queue<TNodeType>();

        yield return root;
        visited.Add(root);
        queue.Enqueue(root);

        while (queue.Count > 0)
        {
            var parent = queue.Dequeue();
            foreach (var child in getChildNodesFunc(parent))
            {
                if (child == default(TNodeType))
                    continue;

                if (!visited.Contains(child))
                {
                    yield return child;
                    visited.Add(child);
                    queue.Enqueue(child);
                }
            }
        }
    }
}

用法：

        var rootItem = new Items
        {
            Name = "Root",
            Children = new List<Items>
            {
                new Items { Name = "Child1" },
                new Items { Name = "Child2" },
                // etc
            }
        };

        foreach (var item in TreeVisitor.WidthTraversal(rootItem, _ => _.Children))
        {
            // ...
        }

Answer 3

由于您需要不使用递归的解决方案，这里有一个：

public Items FindByName(Items root, string targetName)
{
    var stack = new Stack<Items>();
    stack.Push(root);

    Items node;
    while (true)
    {
        node = stack.Pop();
        if (node == null)
        {
            // not found ..
        }
        if (node.Name == targetName)
        {
            break;
        }
        foreach (var child in node.Children)
        {
            stack.Push(child);
        }
    }
    return node;
}

Answer 4

我会这样做：

class Program
{
    static void Main(string[] args)
    {
        List<Item> items = new List<Item>() { new Item { Name = "Pasta", Children = new List<Item>() { new Item { Name = "Pasta", Children = null } } } };
        List<Item> pastas = GetItemsByName(items, "Pasta");
    }

    private static List<Item> GetItemsByName(List<Item> items, string name)
    {
        List<Item> found = new List<Item>();
        foreach (Item item in items)
        {
            if (item.Name == name)
            {
                found.Add(item);
            }
            if (item.Children != null)
            {
                found.AddRange(GetItemsByName(item.Children, name));
            }
        }
        return found;
    }
}


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

如何循环递归数据类型

How to loop recursive data type

c#

recursive-datastructures