C# 将递归替换为 while 循环-解网

问：

我们有一个来自系统的节点树，模型就像Node

Public class Node {
  public string Name { get; set; }
  public bool HasChildren { get; set; }
  public List<Node> Children { get; set; }
}

因此，根据模型，节点树的 JSON 将如下所示：Node

{
  "Name": "Root",
  "HasChildren": true,
  "Children": [
    {
      "Name": "Node-1",
      "HasChildren": true,
      "Children": [
        {
          "Name": "Node-1-1",
          "HasChildren": false,
          "Children": []
        }
      ]
    },
    {
      "Name": "Node-2",
      "HasChildren": true,
      "Children": [
        {
          "Name": "Node-2-1",
          "HasChildren": false,
          "Children": [
            {
              "Name": "Node-2-1-1",
              "HasChildren": false,
              "Children": []
            }
          ]
        },
        {
          "Name": "Node-2-2",
          "HasChildren": false,
          "Children": [
            {
              "Name": "Node-2-2-1",
              "HasChildren": false,
              "Children": []
            }
          ]
        }
      ]
    }
    ...
  ]
}

现在，我想将每个节点保存在一个扁平化的数组或列表中。要遍历所有节点，我知道我可以递归地获取它们。但是，使用递归会导致大量内存使用。
有没有办法使用循环逻辑，如、或逻辑来做同样的事情？whileforforeach

C# for 循环递归 while-loop foreach

“有没有办法......”。几乎可以肯定。你试过什么，你卡在哪里？这个网站不是你告诉我们你想要什么，我们为你编写代码的地方。考虑所需的逻辑，最好尝试在代码中实现该逻辑，然后，如果它不起作用，请向我们展示您做了什么，并准确解释它的问题所在。

0赞 9/23/2022

更好地根据您的需求更改编码逻辑？

2赞 jdweng 9/23/2022

递归比其他解析方法使用更多的内存是不正确的。调用方法时会使用少量开销内存。递归可以多次使用，但内存量并不大。树结构的大小不应在递归方法内部，如果使用递归或不使用递归，则大小相同。

1赞 Jeremy Lakeman 9/23/2022

递归解决方案将使用堆栈来记住你所处的位置。循环需要一些其他数据结构来记住这一点。使用堆栈具有优势，因为您可以轻松地将数据类型混合在一起，而无需任何额外的堆分配。

答：

2赞 SomeBody 9/23/2022 #1

使用此代码，您可以在循环中完成：

List<Node> result = new List<Node> { node };
        bool finished = false;
        int start = 0;
        while(!finished)
        {
            int end = result.Count;
            for(int i = start; i < end; i++)
            {
                if(result[i].HasChildren)
                {
                    result.AddRange(result[i].Children);
                }
            }
            
            if(result.Count == start)
            {
                finished = true;
            }
            start = end;
        }

首先，我们将根节点添加到结果列表中。然后我们进入一个循环，其中有另一个循环。此内部循环遍历上次迭代中添加的所有条目。在第一次迭代中，内部循环仅通过根节点。然后，内部循环将这些节点的所有子节点添加到结果列表中。外部循环将运行，直到内部循环不再添加任何节点。

请注意，它将更改扁平化列表的顺序。节点的子节点不会直接位于其父节点的后面。相反，节点在层次结构中的位置越靠后，该节点在列表末尾的位置就越大。我希望这对你来说没问题，因为你没有写任何关于你喜欢的订单。

在线演示：https://dotnetfiddle.net/Rx67kK

public static IEnumerable<T> DepthFirst<T>(T self, Func<T, IEnumerable<T>> selector)
{
    var stack = new Stack<T>();
    stack.Push(self);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var child in selector(current))
        {
            stack.Push(child);
        }
    }
}

称为 .这是泛型的，因此它可以重用于所有不同类型的树表示形式。它也被懒惰地评估。DepthFirst(myRootNode, n => n.Children)

此变体以深度一阶迭代，但将堆栈更改为队列以获得广度一阶是微不足道的。

上一个：需要程序每五次输出字符串，而循环已在开关盒中运行

下一个：所以我尝试在不使用 C# 中的 sort 函数的情况下按升序对列表进行排序，而且我有点新，所以我想知道我该怎么做？[复制]

C# 将递归替换为 while 循环

C# replace recursive with while loop

评论

评论