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){...}
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.
Make a recursive call:
TraverseNodes(parentNode)
{
for each (Node node in parentNode)
{
if (node.Nodes.Count>0)
TraverseNodes(node);
}
}
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);
}
}
}
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).
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);
}
}
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.
