CODEWITHSUNDEEP
c#
Stan
Stan

Reputation: 38255

How to traverse a multi-hierarchy array in C#

Say rootNode is a multi-hierarchy data structure.

rootNode.Add(node1);
rootNode.Add(node2);
node1.Add(node3);
node1.Add(node4);
node3.Add(node5);

If use foreach to traverse rootNode will only get node1, node2. How do I traverse all nodes in rootNode?

foreach(var node in rootNode){...}

Upvotes: 1

Views: 1933

Answers (6)

jCoder
jCoder

Reputation: 2319

Even if the (working) recursive methods have been posted yet, I'd like to contribute two additional methods.

The first one "pushes" each node in the tree into an Action<Node> that can "consume" it.

public void TraverseWithAction(Action<Node> nodeAction) {
    nodeAction(this);
    foreach(Node n in this.children) {
        n.TraverseWithAction(nodeAction);
    }
}

Usage example:

rootNode.TraverseWithAction(n => buffer.Append(n.ToString()));

The second one provides an IEnumerable<Node> over the root node and all its child nodes, recursively. (And, yes, there are only two loops but they can handle trees deeper than two.)

public IEnumerable<Node> TraverseAsEnumerable() {
    yield return this;
    foreach(Node n in this.children) {
        foreach (Node n2 in n.TraverseAsEnumerable()) {
            yield return n2;
        }
    }
}

Usage example:

foreach (Node n in rootNode.TraverseAsEnumerable()) {
    // do something with n
}

Both methods use recursion so they might fail on very deep structures.

Upvotes: 1

LukeH
LukeH

Reputation: 269498

If your structure isn't too deep then you can safely use the recursive method given in the other answers.

If, however, your structure is potentially very deep then using recursion runs the risk of blowing the call stack and causing a StackOverflowException.

Here's an example of a non-recursive way of traversing your structure:

var stack = new Stack<TNode>();
stack.Push(rootNode);

while (stack.Count > 0)
{
    var node = stack.Pop();
    // do whatever you need to do with each node here

    foreach (var childNode in node)
    {
        stack.Push(childNode);
    }
}

Upvotes: 1

Bob
Bob

Reputation: 99794

The easiest way would be recursion. What is recursion? See this answer for an example.

public void TraverseNodes(Node parentNode)
{
   //iterate through child nodes
   foreach(var node in parentNode)
   {
       //action
       //iterate though child's child nodes. 
       TraverseNodes(node);
   }
}

Basically you are performing the same operation on all the child items by calling the same method (TraverseNodes) on all of the parent items (starting from the first parent).

Upvotes: 1

YetAnotherUser
YetAnotherUser

Reputation: 9356

You can traverse the tree using recursion.

    VisitNode(Node n){
        foreach(var cn in n.Children){
            VisitNode(cn);
        }
        //Do what you want to do with your node here
        Console.Writeline(n.Value);
   }

Here is an example of breadth first traversal.

Upvotes: 2

Dave
Dave

Reputation: 2417

You can setup a simple recursive function

//Pseudo-code

public void traverse(Node n)
{
    if(n hasChildren)
    {
        foreach(Node child in n.children)
        {
              traverse(child);
        }
    }        
}

Upvotes: 1

InBetween
InBetween

Reputation: 32770

Make a recursive call:

TraverseNodes(parentNode)
{
    for each (Node node in parentNode)
    {
         if (node.Nodes.Count>0)
             TraverseNodes(node);
    }
}

Upvotes: 1

Related Questions