Как избавиться от рекурсии при обходе дерева

Question

Как можно этот код изменить так, чтобы избавиться от рекурсии? Этот вопрос является продолжением вот этого

public static IEnumerable<VisualElement> GetChildren(VisualElement root)
{
    yield return root;
    if (root?.Children != null)
        foreach (var child in root.Children)
        {
            foreach (var node in GetChildren(child))
                yield return node;
        }
}

VisualElement:

class VisualElement
{
   public string Name { get; set; }
   public IEnumerable<VisualElement> Children { get; set; }
}

Answer 1

Для начала, можно обойтись без yield, но оставить рекурсию, такое решение будет эффективнее по ресурсозатратности, чем генерация итератора для yield, хотя суть решения остается та же.

public static IEnumerable<VisualElement> GetChildren(VisualElement root)
{
    var result = Enumerable.Repeat(root, 1);
    if (root.Children is null)
        return result;
    return result.Concat(root.Children.SelectMany(x => GetChildren(x)));
}

А вот так можно обойтись без рекурсии. Суть решения в обходе нод дерева, но для этого нужны 3 связи - от родителя к первому дочернему элементу, от последнего дочернего элемента к родителю и от элемента в следующему элементу.

public static IEnumerable<VisualElement> GetChildren(VisualElement root)
{
    Stack<IEnumerator<VisualElement>> wayback = new();
    yield return root;
    if (root.Children is null)
        yield break;
    var enumerator = root.Children.GetEnumerator();
    bool moved;
    while ((moved = enumerator.MoveNext()) || wayback.Count > 0)
    {
        if (!moved)
        {
            enumerator.Dispose();
            enumerator = wayback.Pop();
            continue;
        }
        var node = enumerator.Current;
        yield return node;
        if (node.Children is null)
            continue;
        wayback.Push(enumerator);
        enumerator = node.Children.GetEnumerator();
    }
    enumerator.Dispose();
}

Запущу простой тест

var root = new VisualElement
{
    Name = "1",
    Children = Enumerable.Range(2, 5).Select(x => new VisualElement 
    { 
        Name = $"-{x}", 
        Children = new[] 
        { 
            new VisualElement { Name = $"--{x}a" }, 
            new VisualElement { Name = $"--{x}b" } 
        } 
    })
};
foreach (var node in GetChildren(root))
{
    Console.WriteLine(node.Name);
}

Получаю вот такой вывод в консоль

1
-2
--2a
--2b
-3
--3a
--3b
-4
--4a
--4b
-5
--5a
--5b
-6
--6a
--6b

Кажется это то, что вы хотели получить.

БЛОГ НА HUSL

Как избавиться от рекурсии при обходе дерева

Ответы (1 шт):