how to convert an array of records into a hierarchical structure

makumazan84

here is a problem. I've got an array of records with 2 fields: ID and ParentID. This array represents a hierarchical tree, where each node can have multiple children. What I need is to convert it to a more compact form, like this (code is in C#)

public class TreeBranch
{
int ID;
List Children; //collection of children of this node
.........................
}

................
List MainTree;

// a collection that contains the whole tree I've came up with a dizzy solution, but I don't like it since it is O (n^2). Any ideas will be appreciated )

Lost User

What was your solution? Anyway, that way I might do this would be like this: while you are building the tree, also keep an array of your tree nodes, indexable by ID. Then when you want to add a node to its parent's Children, you can just index into that array to get the parent object. edit: if the nodes are in pre-order you can build the array while you process the items, otherwise you'd need two passes: one to fill the array, and one to build the tree (that is, of course, still O(n) )

modified on Thursday, July 29, 2010 7:21 AM

makumazan84 · modified on Thursday, July 29, 2010 7:21 AM

Hi & thanks for reply&interest. Nevermind my previous thought - that idea was not working ) What I need to do is to write a recursive method, so it will be able to work at any depth. Not that great with recursion, but job needs to be done. Once I'll finish that, I'll post an answer to share with others.

Lost User

Why would you need recursion here? A simple loop over all items would do.. unless there's something you haven't told us yet?

makumazan84

Partly my fault: original message has been parsed and it dropped the fact, that the field Children is a generic of type TreeBranch - it contains children of a certain node. Each of those children can have its own List of children, and so on. Anyways, it's all about converting an array of objects which have ID and ParentID into a tree hierarchy. Consider a case an array: (ParentID;ID) -,1 1,2 1,3 2,4 4,5 should look something like 1- 2- 3 4- 5 Because the depth of the tree is unknown, recursion is the only option - we have no idea about the nodes, that are inhereted from the current. For some dumb security reasons of my job I can't post the code here, but I'll do that later, since the task is very real life

Lost User

Your diagram is a bit confusing, what do you really mean? Btw, the depth of the resulting tree has no relevance - in fact the algorithm I described works for directed graphs in general (trees or not) even if they have disjunct subgraphs or cycles or both (making the "depth" undefined).

Lost User

How's it going?

T M Gray

Add each node to a HashTable using the ID as the key. Loop through the nodes and yourHash[this.ParentID].AddNode(this); I don't know O notation, but I think that would be 2n instead of n^2.

Lost User

T M Gray wrote:

I don't know O notation, but I think that would be 2n instead of n^2.

That's O(n) instead of O(n2) (fyi, that's what I said, but with a HashTable instead of an array)

getroshan

Hope this code helps. Its a generic implementation to render hierarchical objects using recursion. public interface IHierarchy<T> { string Name { get; set; } List<T> Relations { get; set; } } public class Employee : IHierarchy<Employee> { private string name; public string Name { get { return name; } set { name = value; } } private List<Employee> relations; public List<Employee> Relations { get { return relations; } set { relations = value; } } } public class Hierarchy<T> where T : IHierarchy<T> { private List<T> hierarchylist; public Hierarchy(List<T> list) { hierarchylist = list; } private string Replicate(string s, int count) { string output = string.Empty; for (int i = 0; i < count; i++) { output += s; } return output; } public void Render() { Render(hierarchylist, 0); } private void Render(List<T> list, int Level) { foreach (T emp in list) { Console.WriteLine(Replicate("-", Level) + emp.Name); if (emp.Relations != null) { int NextLevel = Level + 1; Render(emp.Relations, NextLevel); } } } } private void button1_Click(object sender, EventArgs e) { #region Heirarchy List<Employee> c4 = new List<Employee>(); c4.Add(new Employee { Name = "C41", Relations = null }); c4.Add(new Employee { Name = "C42", Relations = null }); List<Employee> c1 = new List<Employee>(); c1.Add(new Employee { Name = "C11", Relations = null }); c1.Add(new Employee { Name = "C12", Relations = null }); List<Employee> p1 = new List<Employee>(); p1.Add(new Employee { Name = "C1", Relations = c1 }); p1

Andrew Rissing

Borrowing from SQL, you might want to look at this: Modified Preorder Tree Traversal Algorithm[^] It's intended for non-cyclic trees and is optimized for reading. It's a little complicated to setup, but is quite efficient (O(n)) for recursive lookups. I don't have a C# implementation, but it could easily be done in a DataTable and retrieved from there. You could also add a depth to the table allowing for recursive pulls that would stop after X levels down. Anyways, see if that helps.