The recursion point is the part where you seem to be struggling.
Also, if this is really many-to-many and may include cycles, you need to prevent looping forever.
For the second issue use of a
HashSet<T>
is a good solution to keep track of nodes already visited.
You haven't indicated if you need to return the collection
flattened or if you need to perform some action at each node, so I'll make a few assumptions that you can refine...
So something like this:
HashSet<Node> Visited = new HashSet<Node>();
void Traverse(Node n)
{
if (n == null)
return;
if (Visited.Add(n))
{
DoSomething(n);
foreach (Node nn in n.GetItems().Concat(n.GetBranches()))
{
Traverse(nn);
}
}
}
The
.Concat()
is an extension method from Linq (
System.Linq
).
It would be equivalent to just have two consecutive
foreach
loops on the
n.GetItems()
and
n.GetBranches()
.
I'm assuming that those two methods always return something implementing
IEnumerable<Node>
. Specifically, they return a empty collection object
not null
when there are no such items as members.
If you need the collection of all of the
Node
s traversed, then the
Visited
object will contain that (in no particular order) and implements
IEnumerable<Node>
.
Edit:
If the objects really are Hierarchical, i.e. a tree structure with only one path to any node from the root, then the
HashSet
is not necessary because you can never get to a Node more than once, and a simple list of
Node
s would suffice:
Edit2: changed for different signature of GetItems and GetBranches.
List<Node> AllNodes = new List<Node>();
void Traverse(Node n)
{
if (n == null)
return;
AllNodes.Add(n);
foreach (Node nn in GetItems(server, n).Concat(GetBranches(server, n)))
{
Traverse(nn);
}
AllNodes.Add(n);
}
Pre-order
vs. post-order:
Given:
Root -+- R1 --- R11
|
+- R2 -+- R21
|
+- R22
Pre-order is:
Root R1 R11 R2 R21 R22
Post-Order is:
R11 R1 R21 R22 R2 Root
Edit 3:
public class RepresentationNode
{
public RepresentationNode()
{
Children = new List<RepresentationNode>();
}
public Node TheNode { get; set; }
public List<RepresentationNode> Children { get; private set; }
}
RepresentationNode Traverse(AppropriateType server, Node n)
{
RepresentationNode result = new RepresentationNode { TheNode = n };
result.Children.AddRange(GetItems(server, n.name).Concat(GetBranches(server, n.name)).Select(nn => Traverse(server, nn)));
return result;
}
I assume you have some way to get the root Node in order to start the recursion.
so in some other method:
Node root = somehow get the root Node;
RepresentationNode hierarchy = Traverse(server, root);
At this point you'll have a hierarchical representation of the "black box".