Как зациклить рекурсивный тип данных

Question

Я считываю иерархические данные в рекурсивную структуру данных.

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

Так что это похоже на дерево. Моя проблема в том, что я понятия не имею, как я могу перебрать все элементы или найти внутренний элемент с определенным именем. Поскольку он может быть очень сложным / глубоким, я не могу по-настоящему работать с вложенными циклами, так как не знаю, насколько он будет глубоким.

Как мне создать цикл для всех элементов в такой структуре?

Answer 1

Я бы сделал это так:

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

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

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