Menu
I have a list of objects with property id and parent_id.
I want to build a tree to link up those children and parents.
1 parent may have several children and there is an object which will be the ancestor of all objects.
What's the fastest algorithm to implement that?
I use C# as programming language, but other languages are also okay.
888
Composite is a structural design pattern that lets you compose objects into tree structures and then work with these structures as if they were individual objects.
List of lists representation. A common way to represent trees succinctly using pure data is as a list of lists. Consider that in a list of lists, each element has one and only one parent (up to the outermost list) so meets our expectation of a tree as a hierarchical structure with no cycles.
In a tree data structure, each child from a node forms a subtree recursively. Every child node will form a subtree on its parent node. In this representation, we use two types of nodes one for representing the node with data and another for representing only references.
Absolutely. Just use Object instead of a specific type.
Something like that should do the trick :
public List<Node> MakeTreeFromFlatList(IEnumerable<Node> flatList)
{
var dic = flatList.ToDictionary(n => n.Id, n => n);
var rootNodes = new List<Node>();
foreach(var node in flatList)
{
if (node.ParentId.HasValue)
{
Node parent = dic[node.ParentId.Value];
node.Parent = parent;
parent.Children.Add(node);
}
else
{
rootNodes.Add(node);
}
}
return rootNodes;
}
(assuming that ParentId is a Nullable<int>, and is null for root nodes)
68
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
