load hierarchy to treeview

Question

i v got this class :

public class hierarchymain 
   {
       public String label;              // Label to be displayed in treeview
       public int parentId;             // ID of the parent. Root have 0 in parent ID
       public int ID;                     //Id in table. ignore it
   }

but i cant figure out the right way to load it into treeview...

hierarchy = new List<Hierarchymain> {
            new Hierarchymain{Label="ONE",ParentID=0, ID=0},
            new Hierarchymain{Label="TWO", ParentID=0, ID=1},
            new Hierarchymain{Label="THREE", ParentID=1, ID=2},
            new Hierarchymain{Label="Four", ParentID=2, ID=3},
            new Hierarchymain{Label="five", ParentID=3, ID=4},
            new Hierarchymain{Label="six", ParentID=4, ID=5},
            new Hierarchymain{Label="seven", ParentID=0, ID=6}
        };

any ideas?

Answer 1

There are many ways to do that. Before I go, I want to point out that as many commenters mentioned, the provided sample is not correct - if ParentID=0 represents a root node, then you should not have a node with ID=0, so I'll be using the same data as yours but with each item ID incremented. Here is the corrected (and additionally shuffled) data I'll be using for testing:

var source = new List<Hierarchymain> {
    new Hierarchymain{ Label="THREE", ParentID=2, ID=3},
    new Hierarchymain{ Label="six", ParentID=5, ID=6},
    new Hierarchymain{ Label="Four", ParentID=3, ID=4},
    new Hierarchymain{ Label="five", ParentID=4, ID=5},
    new Hierarchymain{ Label="TWO", ParentID=1, ID=2},
    new Hierarchymain{ Label="seven", ParentID=0, ID=7},
    new Hierarchymain{ Label="ONE", ParentID=0, ID=1},
};

Now the solutions.

(A) Straightforward recursive implementation: Start with the root items, create a node for each item, and then do the same with its children.

static void PopulateA(TreeView treeView, IEnumerable<Hierarchymain> source)
{
    AddNodes(treeView.Nodes, 0, source);
}
static void AddNodes(TreeNodeCollection parentNodes, int parentID, IEnumerable<Hierarchymain> source)
{
    foreach (var item in source.Where(item => item.ParentID == parentID))
    {
        var node = parentNodes.Add(item.Label);
        AddNodes(node.Nodes, item.ID, source);
    }
}

(B) Different implementation of (A). The problem with (A) is that it has O(N^2) time complexity. But that can easily be improved by preparing a lookup structure at the beginning and still keeping the simplicity.

static void PopulateB(TreeView treeView, IEnumerable<Hierarchymain> source)
{
    AddNodes(treeView.Nodes, 0, source.ToLookup(item => item.ParentID));
}
static void AddNodes(TreeNodeCollection parentNodes, int parentID, ILookup<int, Hierarchymain> source)
{
    foreach (var item in source[parentID])
    {
        var node = parentNodes.Add(item.Label);
        AddNodes(node.Nodes, item.ID, source);
    }
}

(C) Iterative implementation of the above. If the hierarchy is too deep, the recursive implementations will fail with StackOverflowException. That could be solved by turning them into iterative version, sacrificing readability and simplicity. Here is the equivalent of (B):

static void PopulateC(TreeView treeView, IEnumerable<Hierarchymain> source)
{
    var itemsByParentId = source.ToLookup(item => item.ParentID);
    var parentNodesStack = new Stack<TreeNodeCollection>();
    var childEnumeratorStack = new Stack<IEnumerator<Hierarchymain>>();
    var parentNodes = treeView.Nodes;
    var childEnumerator = itemsByParentId[0].GetEnumerator();
    try {
        while (true)
        {
            while (childEnumerator.MoveNext())
            {
                var item = childEnumerator.Current;
                var node = parentNodes.Add(item.Label);
                parentNodesStack.Push(parentNodes);
                childEnumeratorStack.Push(childEnumerator);
                parentNodes = node.Nodes;
                childEnumerator = itemsByParentId[item.ID].GetEnumerator();
            }
            if (childEnumeratorStack.Count == 0) break;
            childEnumerator.Dispose();
            childEnumerator = childEnumeratorStack.Pop();
            parentNodes = parentNodesStack.Pop();
        }
    }
    finally
    {
        childEnumerator.Dispose();
        while (childEnumeratorStack.Count != 0) childEnumeratorStack.Pop().Dispose();
    }
}

(D) This is the algorithm I usually use. The same idea can be implemented recursively, but I use this for the same reasons mentioned in (C). It works as follows: During the processing, we maintain a map of the created nodes by ID in order to be able to locate the parent nodes. For each item from the input sequence we build a stack containing the items which nodes are not created yet, and then just process it in reverse order. This way we ensure the parents are created before their children.

static void PopulateD(TreeView treeView, IEnumerable<Hierarchymain> source)
{
    var itemById = source.ToDictionary(item => item.ID);
    var nodeById = new Dictionary<int, TreeNode>();
    var addStack = new Stack<Hierarchymain>();
    foreach (var nextItem in source)
    {
        // Collect the info about the nodes that need to be created and where
        TreeNodeCollection parentNodes;
        for (var item = nextItem; ; item = itemById[item.ParentID])
        {
            TreeNode node;
            if (nodeById.TryGetValue(item.ID, out node))
            {
                // Already processed
                parentNodes = node.Nodes;
                break;
            }
            addStack.Push(item);
            if (item.ParentID == 0)
            {
                // Root item
                parentNodes = treeView.Nodes;
                break;
            }
        }
        // Create node for each collected item in reverse order
        while (addStack.Count > 0)
        {
            var item = addStack.Pop();
            var node = parentNodes.Add(item.Label);
            nodeById.Add(item.ID, node);
            parentNodes = node.Nodes;
        }
    }
}

Hope that helps.

Answer 2

When populating the tree, you can use a dictionary to retrieve the parent of a new item to add. If we can assume that parents are always defined before children, the second foreach can be omitted.

var dict = new Dictionary<int, TreeNode>();
var orphans = new Queue<Hierarchymain>();
foreach (Hierarchymain item in hierarchy)
{
    TreeNode newNode = new TreeNode(item.Label);
    TreeNode parent;
    if (dict.TryGetValue(item.ParentID, out parent))
        parent.Nodes.Add(newNode);
    else if (item.ParentID == 0)
        treeView1.Nodes.Add(newNode);
    else
        orphans.Enqueue(item);

    dict.Add(item.ID, newNode);
}

// processing nodes, whose parents were created later
foreach (Hierarchymain item in orphans)
{
    TreeNode orphan = dict[item.ID];
    TreeNode parent;
    if (dict.TryGetValue(item.ParentID, out parent))
        parent.Nodes.Add(orphan); // parent found
    else
        treeView1.Nodes.Add(orphan); // the node is a real orphan, adding to the root
}