C#用while循环替换递归

Question

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

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

因此，基于Node模型，节点树的JSON如下所示：

{
  "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": []
            }
          ]
        }
      ]
    }
    ...
  ]
}

现在，我想保存一个扁平数组或列表中的每个节点。为了遍历所有的节点，我知道我可以递归地得到它们。但是，使用递归会导致内存的大量使用。

是否有一种方法可以使用循环逻辑，如while、for或foreach逻辑来进行相同的操作？

Answer 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

Answer 2

我的goto树迭代器如下所示：

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)。这是泛型的，因此它可以用于所有不同类型的树表示。这也是懒洋洋的评价。

该变体按深度一阶迭代，但将堆栈更改为队列以获得宽度优先顺序是非常简单的。