We have a node tree from a system, the Node model is like

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

So, based on the Node model, the JSON of the node tree will be something like below:

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

Now, I'd like to save every node in a flattened array or list. To traverse all the nodes, I know I can recursively get them. But, using recursion causes a big usage of memory.
Is there a way of using the loop logic, like while, for, or foreach logic to do the same?

CodePudding user response：

My goto tree iterator looks like this:

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

Called like DepthFirst(myRootNode, n => n.Children). This generic, so it can be reused for all different kinds of tree representations. It is also lazily evaluated.

This variant iterates in a depth first order, but it is trivial to change the stack to a queue to get a breadth first ordering.

CodePudding user response：

With this code, you can do it in a loop:

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

First, we add the root node to the result list. Then we enter a loop, which has another loop in it. This inner loop goes through all entries which have been added in the last iteration. In the first iteration, the inner loop goes only through the root node. The inner loop adds then all children of those nodes to the result list. The outer loop will run until the inner loop doesn't add any further nodes.

Note that it will change the order of the flattened list. The children of a node won't be directly behind their parent. Instead, the more down a node is in the hierarchy, the more in the end of the list the node will be. I hope this is ok for you, since you didn't write anything about your preferred order.

Online demo: https://dotnetfiddle.net/Rx67kK