Re: TreeView Recursion - C# Discussion Boards

To define recursion, we must first define recursion!

(\ /)
(O.o)
(><)

1-Aug-09 7:50

Hi,
Here's what my table looks like..

ID    Parent    Name
------------------------
0     0         BaseLine
1     0         A
2     1         A1
3     1         A2
4     0         B
5     4         B1
6     4         B2

How would you load it recursively so it would show A1 & A2 under A and B1 & B2 under B and any deeper sub levels would show in the right node level.. I know it's supposed to be a simple recursion logic but it's getting me tired Sigh | :sigh:

MishaInTheCloud.blogspot.com

Mike Ellison1-Aug-09 10:47

Mike Ellison

1-Aug-09 10:47

You may want to consider an approach that stores the lineage for each item as a field in the database... something like this post:
http://www.sqlteam.com/article/more-trees-hierarchies-in-sql[^]
You're then in a position to ORDER BY that lineage column to display items organized by the hierarchy.

Muammar©1-Aug-09 12:50

All generalizations are wrong, including this one!

(\ /)
(O.o)
(><)

1-Aug-09 12:50

Hmmm... Looks promising but how would you apply it in C#?? The logic itself is a mess and I cant just rewrite it in my application.. Any idea??

OriginalGriff1-Aug-09 21:59

OriginalGriff

1-Aug-09 21:59

Here's the method I use:

/// <summary>
/// Adds a branch to a TreeView control
/// </summary>
/// <remarks>
/// The Path contains the name of the node to be used in the tree view, for example
/// "General" or "Colours".
/// If the path is qualified with '\' or '/' then it is treated as a hierarchical path
/// and the full path required is generated. For example, if the path was
/// "General\Colors\Pens" the the tree view would display
///      General
///          Colours
///              Pens
/// and any of these branches would select the node.
///
/// The Description can be used for the display of more information.
/// </remarks>
/// <example>
/// AddBranch(tvSelect.Nodes,
///           @"General\Colours",
///           @"Change the colours settings for items",
///           object o);
/// </example>
/// <param name="nc">TreeNodeCollection: TreeView Nodes collection to add to</param>
/// <param name="Path">string: TreeView Hierarchy path to object</param>
/// <param name="Description">string: Plain english description of the object</param>
/// <param name="o">object: object to add to TreeView</param>
public static void AddBranch(TreeNodeCollection nc, string Path, string Description, object o)
    {
    string[] paths = Path.Split('\\', '/'); // Break "General\Font" to "General", "Font" etc.
    TreeNode node;
    foreach (string s in paths)
        {
        if (s == null || s == "")
            {
            // Ignore leading "\", or instances of "\\".
            continue;
            }
        if ((node = FindBranch(nc, s)) == null)
            {
            // Branch does not exist.
            // create it.
            node = new TreeNode();
            node.Name = Description;
            node.Text = s;
            node.Tag = o;
            nc.Add(node);
            }
        // Move down the tree.
        // This allows us to create the sub-branches.
        nc = node.Nodes;
        }
    }

/// <summary>
/// Locates a given Node, returns it if found
/// </summary>
/// <param name="nc">TreeNodeCollection: List of TreeNode items to search</param>
/// <param name="name">string: Name of branch (or leaf) to search for.</param>
/// <returns>Node if found, null if not.</returns>
public static TreeNode FindBranch(TreeNodeCollection nc, string name)
    {
    if ((name != null) && (name != ""))
        {
        foreach (TreeNode n in nc)
            {
            if (n.Text == name)
                {
                return n;
                }
            }
        }
    return null;
    }

Comments make it pretty obvious how to use.

No trees were harmed in the sending of this message; however, a significant number of electrons were slightly inconvenienced.

This message is made of fully recyclable Zeros and Ones

Muammar©1-Aug-09 23:18

All generalizations are wrong, including this one!

(\ /)
(O.o)
(><)

1-Aug-09 23:18

Great, but how am I supposed to generate the path string?? Can you kindly tell me how would you populate my table's data into your tree??

This's how I'm loading the frist two levels to my tree:

private DataTable GenDT(string strSelect)
{
    if (con.State != ConnectionState.Open)
        con.Open();


    DataTable _dt = new DataTable();
    try
    {
        new OracleDataAdapter(strSelect, con).Fill(_dt);
    }
    catch (Exception) { }
    return _dt;
}

private void LoadBudgetLineItems()
{
    DataTable dt = GenDT(@"SELECT CODE, NAME, PARENT FROM BUDGETLINES ORDER BY CODE");
    int L1,L2;
    L1 = L2 = -1;

    TreeGridNode node = new TreeGridNode();
    foreach (DataRow dr in dt.Rows)
    {
        if (dr["PARENT"].ToString().Length == 0)
        {
            //Parent
            node = treeGridView1.Nodes.Add(null, dr["CODE"], dr["NAME"], "");
            node.ImageIndex = 0;
            node.DefaultCellStyle.Font = boldFont;
            node.DefaultCellStyle.BackColor = Color.Black;
            node.DefaultCellStyle.ForeColor = Color.White;
            L1++;

            //Level 2
            foreach (DataRow dr2 in dt.Rows)
            {
                if (dr2["PARENT"].ToString().Equals(dr["CODE"].ToString()))
                {
                    node = treeGridView1.Nodes[L1].Nodes.Add(null, dr2["CODE"], dr2["NAME"], "");
                    node.ImageIndex = 1;

                }
            }
        }

    }
}

Many thanks mate!

OriginalGriff2-Aug-09 0:34

OriginalGriff

2-Aug-09 0:34

That's not nice! Are you really stuck with that data structure? The reason I ask is that it assumes so many things:

That the Parent ID exists.
That the Parent ID is less than the Code ID.
That the parent ID is not the going to go recursive.

It would not take a lot of user mistakes to bomb the data structure - you are going to need some very good error checking to avoid looping or loosing data.

Honestly? I would change the data and / or process it twice, first pass to assure integrity, second pass to populate.

No trees were harmed in the sending of this message; however, a significant number of electrons were slightly inconvenienced.

This message is made of fully recyclable Zeros and Ones

Muammar©2-Aug-09 1:01

All generalizations are wrong, including this one!

(\ /)
(O.o)
(><)

2-Aug-09 1:01

You see, this's exactly why I didnt want to post my code at the first place Laugh | :laugh:

Ok, ignore the bullshit I'm running and tell me how would you manage it at both ends (Database structure and when it comes to populating the treeView control).. Please, I really need you to shed some light on my messy logic!

N a v a n e e t h9-Aug-09 4:47

9-Aug-09 4:47

Sounds like a good question. As a first step, let us create a class named Node which will have Id and Name as properties, AddChild and FindNode as methods. Consider the following code,

public sealed class Node
{
    readonly List<Node> childNodes = new List<Node>();
    Node parent = null;
    public Node(int id, string name)
    {
        this.Id = id;
        this.Name = name;
    }

    public void AddChild(Node node)
    {
        node.SetParent(this);
        childNodes.Add(node);
    }

    public void SetParent(Node parent)
    {
        this.parent = parent;
    }

    public Node FindNode(int id)
    {
        Node result = childNodes.SingleOrDefault(node => node.Id == id);
        if (result == null)
        {
            foreach (Node node in childNodes)
                result = node.FindNode(id);
        }
        return result;
    }

    public void PrintTree(Action<Node> callback)
    {
        callback(this);
        foreach (Node node in childNodes)
            node.PrintTree(callback);
    }

    public override string ToString()
    {
        return string.Format("Id : {0}, Parent Name : {1}, Name : {2}", 
            Id, parent == null ? "No parent" : parent.Name, Name);
    }

    public int Id { get; private set; }

    public string Name { get; private set; }
}

You have done with a recursive tree implementation!

If you are confused, here is the explanation.

1 - Each node holds its children nodes
2 - When a child node is added to a node, it will set the child nodes parent and add it to the children collection.
3 - FindNode() does a recursive search in all its children and tries to find a node with the specified id. If it can't find a node, returns NULL.
4 - PrintTree does a recursive search and ask each node and its children to print itself. The callback supplied will be called and you can handle this callback and do something useful. In this example, I have just printed the name.

Here is how you use it in a console application,

Node baseLine = new Node(0, "BaseLine");
baseLine.AddChild(new Node(1, "A"));

// find A node to add A1 and A2 as its children
Node aNode = baseLine.FindNode(1);
aNode.AddChild(new Node(2, "A1"));
aNode.AddChild(new Node(3, "A2"));

baseLine.AddChild(new Node(4, "B"));

// find B node to add B1 and B2 as its children
Node bNode = baseLine.FindNode(4);
bNode.AddChild(new Node(5, "B1"));
bNode.AddChild(new Node(6, "B2"));

// printing the whole tree
baseLine.PrintTree(node => Console.WriteLine(node));
Console.ReadKey();

I wrote a blog post that explains the thought process in writing recursive methods. Read it here[^].

Hope that helps Smile | :)

Navaneeth

How to use google | Ask smart questions

Muammar©9-Aug-09 9:53

All generalizations are wrong, including this one!

(\ /)
(O.o)
(><)

9-Aug-09 9:53

Thank you Navaneeth! You're definitely one of the most helpful C# references..

I like your way of wrapping it in a class, the truth is, I'm a bit slow this week and would be greatly thankful if you can show me how would you load it from a dataset to a treeview control.. You know, in an iteration loop like for or foreach..

Here's a reminder of the relevant table structure...

ID    Parent    Name
------------------------
0     0         BaseLine
1     0         A
2     1         A1
3     1         A2
4     0         B
5     4         B1
6     4         B2

Thanks again mate.. I really appreciate the time you've spent to help me out and hope you soon become a MS MVP as well!

N a v a n e e t h9-Aug-09 16:31

9-Aug-09 16:31

Here you go

bool firstIteration = true;
Node baseLine = null;
foreach (DataRow row in dt.Rows)
{
    if (firstIteration)
    {
        baseLine = new Node(int.Parse(row["Id"].ToString()),
            row["Name"].ToString());
        firstIteration = false;
    }
    else
    {
        int parentId = int.Parse(row["Parent"].ToString());
        Node parent = (baseLine.Id == parentId) ? baseLine :  baseLine.FindNode(parentId);
        parent.AddChild(new Node(int.Parse(row["Id"].ToString()),
                row["Name"].ToString()));
    }
}
baseLine.PrintTree(node => Console.WriteLine(node));
Console.ReadKey();

I'd suggest to avoid using DataTable in production code. You could achieve the above with a simple DataReader. DataTable uses reader internally. You may also need to add some sanity check to this code like NULL checking, data validation etc.

Smile | :)

Navaneeth

How to use google | Ask smart questions

Muammar©10-Aug-09 2:19

All generalizations are wrong, including this one!

(\ /)
(O.o)
(><)

10-Aug-09 2:19

Thank you thank you thank you Navaneeth for having such a temper with me but I still dont get what your PrintTree is for Confused | :confused:

I just want to fill a treeView control on a windows form Sigh | :sigh:

N a v a n e e t h10-Aug-09 7:40

10-Aug-09 7:40

Muammar© wrote:
but I still dont get what your PrintTree is for

Its the recursive method. It prints itself and asks children to do so. Each children will repeat this step until there is no children.

Muammar© wrote:
I just want to fill a treeView control on a windows form

Well, you could have said this before. Fortunately, our node implementation is pretty well extensible. So here it goes.

You need to add the below property to Node class. This property returns parent node of a node.

public Node Parent { get { return parent; } }

Since our Node class and TreeView's TreeNode class has different interfaces, we need a builder class that can convert Node instance into equivalent TreeNode. Name it TreeNodeBuilder.

public sealed class TreeNodeBuilder
{
    Node root = null;
    Dictionary<int, TreeNode> treeNodes = new Dictionary<int, TreeNode>();
    public TreeNodeBuilder(Node root)
    {
        this.root = root;
    }

    public TreeNode BuildTreeNode()
    {
        // root node. Baseline in your case
        TreeNode rootTreeNode = null;
        root.PrintTree(delegate(Node node)
        {
            // parent is null, this will be the root
            if (node.Parent == null)
            {
                rootTreeNode = new TreeNode(node.Name);
                rootTreeNode.Tag = node;
                // keeping this treenode
                treeNodes.Add(node.Id, rootTreeNode);
            }
            else
            {
                // checking any tree node added for this parent id
                if (treeNodes.ContainsKey(node.Parent.Id))
                {
                    TreeNode parent = treeNodes[node.Parent.Id];
                    TreeNode current = parent.Nodes.Add(node.Name);
                    current.Tag = node;
                    treeNodes.Add(node.Id, current);
                }
            }
        });
        return rootTreeNode;
    }
}

All you need to do is to supply your root node (baseline) to this class and call BuildTreeNode(). Here is how you do that,

// Code to create node in a loop. Same in the last post
TreeNodeBuilder nodeBuilder = new TreeNodeBuilder(baseLine); // baseline will be root node
treeView1.Nodes.Add(nodeBuilder.BuildTreeNode());

Run it and you are done!

Smile | :)

Navaneeth

How to use google | Ask smart questions

Muammar©10-Aug-09 7:49

All generalizations are wrong, including this one!

(\ /)
(O.o)
(><)

10-Aug-09 7:49

Ok, sorry just saw your post, glad you're still up Smile | :)

.. Just give me a minute to try it out.. please dont go anywhere Smile | :)

stay with me for a couple of minutes Smile | :)

Muammar©10-Aug-09 8:04

All generalizations are wrong, including this one!

(\ /)
(O.o)
(><)

10-Aug-09 8:04

N a v a n e e t h wrote:
// Code to create node in a loop. Same in the last post
TreeNodeBuilder nodeBuilder = new TreeNodeBuilder(baseLine); // baseline will be root node
treeView1.Nodes.Add(nodeBuilder.BuildTreeNode());

Ok, I told you I feel like a big idiot tonight so please tell me why am I getting only my root node when I write this:

Node baseLine = new Node(0, "BaseLine");
TreeNodeBuilder nodeBuilder = new TreeNodeBuilder(baseLine); // baseline will be root node
treeView1.Nodes.Add(nodeBuilder.BuildTreeNode());

I have to do some kind of iteration right?? Please show me mate.. I cant thank you enough Naveneeth, you're my hero now Smile | :)

ps. Dont worry, I'm not gay Laugh | :laugh:

All generalizations are wrong, including this one!

(\ /)
(O.o)
(><)

10-Aug-09 8:14

Ok, here's what I'm doing now:

private DataTable GenDT(string strSelect)
{
    if (con.State != ConnectionState.Open)
        con.Open();


    DataTable _dt = new DataTable();
    try
    {
        new OracleDataAdapter(strSelect, con).Fill(_dt);
    }
    catch (Exception) { }
    return _dt;
}

private void pop_tree()
{
    DataTable dt = GenDT("SELECT ID,PARENT,NAME FROM TT ORDER BY ID");

    bool firstIteration = true;
    Node baseLine = null;
    foreach (DataRow row in dt.Rows)
    {
        if (firstIteration)
        {
            baseLine = new Node(int.Parse(row["Id"].ToString()),
                row["Name"].ToString());
            firstIteration = false;
        }
        else
        {
            int parentId = int.Parse(row["Parent"].ToString());
            Node parent = (baseLine.Id == parentId) ? baseLine : baseLine.FindNode(parentId);
            parent.AddChild(new Node(int.Parse(row["Id"].ToString()),
                    row["Name"].ToString()));
        }
        TreeNodeBuilder nodeBuilder = new TreeNodeBuilder(baseLine); // baseline will be root node
        treeView1.Nodes.Add(nodeBuilder.BuildTreeNode());
    }
}

private void Form1_Load(object sender, EventArgs e)
{
    pop_tree();
}

And I'm getting multiple baseline nodes.. I guess I'm placing your lines in the wrong place of the loop right??

Solved:)

All generalizations are wrong, including this one!

(\ /)
(O.o)
(><)

10-Aug-09 8:21

Just have to move the last two lines outside the loop D'Oh! | :doh:

You know what?? I love you Big Grin | :-D

5 for all your posts and articles!!
You're one of the most most valuable MVPs and I'm going to didicate my next article to your honor Wink | ;)

Thank you Navaneeth.. Your the best!!

A minor bug?? I hope :s [modified]

All generalizations are wrong, including this one!

(\ /)
(O.o)
(><)

10-Aug-09 8:35

Hey,
I'm sorry for the headache but when adding to A1 or A2 a sub node like:

ID    Parent    Name
------------------------
0     0         BaseLine
1     0         A
2     1         A1
3     1         A2
4     0         B
5     4         B1
6     4         B2
7     2         A1.1
8     2         A1.2

I get null reference exception here:

parent.AddChild(new Node(int.Parse(row["Id"].ToString()),
        row["Name"].ToString()));

Please help Sigh | :sigh:

modified on Monday, August 10, 2009 2:43 PM

Re: A minor bug?? I hope :s

N a v a n e e t h10-Aug-09 9:29