主页 / 问题 / 1445843
Accepted
Kalmankantaja
Asked:2022-09-05 14:25:48 +0000 UTC2022-09-05 14:25:48 +0000 UTC

遍历树时如何摆脱递归

  • 772

如何更改此代码以摆脱递归？这个问题是这个问题的延续

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

0 个回答

  1. Best Answer

    对于初学者，您可以不使用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

    看来这就是你想要得到的。

    • 2

相关问题