MorkaLork Development

Interesting stuff I've picked up over the years...

Tree structures

2009-09-29 18:43:13 | 653 views | tree structure treeview control csharp node

What is a tree structure?



A tree structure is a way of representing hierarchical data. The TreeView uses data that is stored in a tree structure.
The name comes from the data being stored in the same way a tree works. The data has one root and then the elements derive from that root in various directions. The simplest way to understand a tree structure is to think of the Windows explorer toolbar where you have a root, say C:\, and then several folders connected to that, say C:\Program\ or C:\Games\ and these have sub folders themselves such as C:\Games\PacMan\ or C:\Documents\ebooks\.
A tree structure can be very useful in these cases, but it's quite hard to use in C# since there is no built-in collection to use.

This article will show you how to use a tree structure in C# utilizing the TreeView control.


The application


We will make a very nifty little music category TreeView application. It will display some music genres with sub genres, it will look like this:

Our fantastically dull application

Now, you could of course hard code these values in to the TreeView control, but that would not help you to understand how useful it is.
We will create two classes to help us; MyTree and MyNode. We won't call it TreeNode since there already is a class called TreeNode that we will use for something completely different.

We'll start with the node class:

MyNode.cs




using System;
using System.Collections.Generic;

namespace TreeExample {
public class MyNode {
//Properties
public List<MyNode> Children { get; set; }
public string Value { get; set; }

//Set indexer
public MyNode this[int index] {
get { return Children[index]; }
set { Children[index] = value; }
}

//Constructor
public MyNode(string _value) {
this.Value = _value;
this.Children = new List<MyNode>();
}

//Add a child node
public void AddChild(MyNode node) {
this.Children.Add(node);
}

public void RemoveChild(int index) {
this.Children.RemoveAt(index);
}
}
}


This class contains two very important properties; Value and Children. Value is the general value of this node (in string form) and Children are all the child nodes connected to it. Since every node can have X children we'll put them in a List of MyNode.

We add two methods as well for adding and removing children.

This class of course comes with the MyTree class that looks like this:

Tree.cs




using System;
using System.Collections.Generic;

namespace TreeExample {
class MyTree {
//The root element
public MyNode Root { get; set; }

public MyTree(String value) {
this.Root = new MyNode(value);
}
}
}


This is just a very short class that has only one property; the Root node. The root node has to be set since it's the only purpose of this class.

In combination these two classes can now be used like this:


MyTree Tree = new MyTree("Root");
Tree.Root.AddChild("child1");
Tree.Root.AddChild("child2");
Tree.Root.Children[0].AddChild("subChild1");



Since each node has its own collection of nodes the sub nodes are used via its parent node. That means that to connect to the roots child we have to call it via the root, root.Child, and to use the root´s child´s child we have to go to its parent, the roots child, root.Child.Child and so on (confusing?).

Since we are creating an application that displays music genres we will create a tree with 'Music' as root, and then add the genres and sub-genres:


//Create a tree with a 'Music' root node
MyTree tree = new MyTree("Music");

//Add three genres
tree.Root.AddChild(new MyNode("Rock"));
tree.Root.AddChild(new MyNode("Pop"));
tree.Root.AddChild(new MyNode("Classic"));

//Add metal and grunge in the rock genre
tree.Root.Children[0].AddChild(new MyNode("Metal"));
tree.Root.Children[0].AddChild(new MyNode("Grunge"));

//Add Country and Schlager to the Pop genre
tree.Root.Children[1].AddChild(new MyNode("Country"));
tree.Root.Children[1].AddChild(new MyNode("Schlager"));

//Add Baroque, Romantic and Opera to Classic
tree.Root.Children[2].AddChild(new MyNode("Baroque"));
tree.Root.Children[2].AddChild(new MyNode("Romantic"));
tree.Root.Children[2].AddChild(new MyNode("Opera"));

//Add French and Italian to the Opera genre
tree.Root.Children[2].Children[2].AddChild(new MyNode("French"));
tree.Root.Children[2].Children[2].AddChild(new MyNode("Italian"));


This picture may explain what we just did:

The TreeView control and its content explained


Adding to TreeView


The hard part is to add these nodes to the TreeView control. We can't do an ordinary loop since we don't know how many child nodes it contains (or, rather, we do, but we'll pretend we don't).
What we'll do is use a recursive method that calls itself if it finds any child nodes and loop through them as well.

A recursive method calls itself as many times as need to complete the task. This might be confusing, but a picture will visualize the basics:

A recursive method

If a condition is met it will call itself. If the condition is still met it will call itself until the condition is false. It will then return back.

Now, we have a root element, Music, which has three children: Rock, Pop and Classic. Each of these has children and in some cases sub children and we have to loop through them all.

This is the method we will use (loopNodes) together with its calling method (CreateTree):



private void CreateTree() {
//Create a tree with a 'Music' root node
MyTree tree = new MyTree("Music");

//Add three genres
tree.Root.AddChild(new MyNode("Rock"));
tree.Root.AddChild(new MyNode("Pop"));
tree.Root.AddChild(new MyNode("Classic"));

//Add metal and grunge in the rock genre
tree.Root.Children[0].AddChild(new MyNode("Metal"));
tree.Root.Children[0].AddChild(new MyNode("Grunge"));

//Add Country and Schlager to the Pop genre
tree.Root.Children[1].AddChild(new MyNode("Country"));
tree.Root.Children[1].AddChild(new MyNode("Schlager"));

//Add Baroque, Romantic and Opera to Classic
tree.Root.Children[2].AddChild(new MyNode("Baroque"));
tree.Root.Children[2].AddChild(new MyNode("Romantic"));
tree.Root.Children[2].AddChild(new MyNode("Opera"));

//Add French and Italian to the Opera genre
tree.Root.Children[2].Children[2].AddChild(new MyNode("French"));
tree.Root.Children[2].Children[2].AddChild(new MyNode("Italian"));

//Create a blank treenode
TreeNode treeNode = new TreeNode();
//Add the treenode to the treeView1 control
treeView1.Nodes.Add(treeNode);

//Recursively loop through the tree and add the leaves to the root node
loopNodes(tree.Root, treeNode);
}

private void loopNodes(MyNode node, TreeNode treeNode) {

//Set the current TreeNode object text value to the current MyNode value
treeNode.Text = node.Value;

//Loop through all the children of the current node
foreach (MyNode mn in node.Children) {
//Create a new TreeNode object to add to the current TreeNode object
TreeNode innerNode = new TreeNode();
innerNode.Text = mn.Value;

//Add the innerNode to the treeNode as a child
treeNode.Nodes.Add(innerNode);
//Check if the child has any children
loopNodes(mn, innerNode);
}
}


First of all, we create a TreeNode object, which is what the TreeView control uses, and we add it to the TreeView control. We will then add nodes to the TreeNode control as we go along.

We call our loopNodes method using our Root as MyNode object and the TreeNode object as a reference. We start by adding the Root and then we make a check if it has any children. If it has, we do the same thing over and over again.

We'll step through this using another picture:

A very odd picture with plenty of numbers....


1.


Node added: Music
Children: Yes; Rock, Pop, Classic
Search Rock recursively

2.


Node added: Rock
Children: Yes; Metal, Grunge
Search Metal recursively

3.


Node added: Metal
Children: No
Return to parent

4.


Node added: None
Children: Yes; Metal, Grunge
Search Grunge recursively

5.


Node added: Grunge
Children: No
Return to parent

6.


Node added: None
Children: Metal, Grunge
All children searched, return to parent

7.


Node added: None
Children: Rock, Pop, Classic
Search Pop recursively

And efter this it does the same for Pop and Classic. That's how the recursive method works. I hope this might shed some light on the somewhat tricky concept of recursive method usage.


Full code



MyNode.cs


using System;
using System.Collections.Generic;

namespace TreeExample {
public class MyNode {
//Properties
public List<MyNode> Children { get; set; }
public string Value { get; set; }

//Set indexer
public MyNode this[int index] {
get { return Children[index]; }
set { Children[index] = value; }
}

//Constructor
public MyNode(string _value) {
this.Value = _value;
this.Children = new List<MyNode>();
}

//Add a child node
public void AddChild(MyNode node) {
this.Children.Add(node);
}

public void RemoveChild(int index) {
this.Children.RemoveAt(index);
}
}
}


MyTree.cs


using System;
using System.Collections.Generic;

namespace TreeExample {
class MyTree {
//The root element
public MyNode Root { get; set; }

public MyTree(String value) {
this.Root = new MyNode(value);
}
}
}


Form1.cs


using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;

namespace TreeExample {
public partial class Form1 : Form {
public Form1() {
InitializeComponent();

//Set form properties
this.Name = "TreeViewDemo";
this.Text = "MorkaLork TreeView Demo";

CreateTree();
}

private void CreateTree() {
//Create a tree with a 'Music' root node
MyTree tree = new MyTree("Music");

//Add three genres
tree.Root.AddChild(new MyNode("Rock"));
tree.Root.AddChild(new MyNode("Pop"));
tree.Root.AddChild(new MyNode("Classic"));

//Add metal and grunge in the rock genre
tree.Root.Children[0].AddChild(new MyNode("Metal"));
tree.Root.Children[0].AddChild(new MyNode("Grunge"));

//Add Country and Schlager to the Pop genre
tree.Root.Children[1].AddChild(new MyNode("Country"));
tree.Root.Children[1].AddChild(new MyNode("Schlager"));

//Add Baroque, Romantic and Opera to Classic
tree.Root.Children[2].AddChild(new MyNode("Baroque"));
tree.Root.Children[2].AddChild(new MyNode("Romantic"));
tree.Root.Children[2].AddChild(new MyNode("Opera"));

//Add French and Italian to the Opera genre
tree.Root.Children[2].Children[2].AddChild(new MyNode("French"));
tree.Root.Children[2].Children[2].AddChild(new MyNode("Italian"));

//Create a blank treenode
TreeNode treeNode = new TreeNode();
//Add the treenode to the treeView1 control
treeView1.Nodes.Add(treeNode);

//Recursively loop through the tree and add the leaves to the root node
loopNodes(tree.Root, treeNode);
}

/// <summary>
/// Enters a node into a root node object
/// </summary>
/// <param name="node">The node to add</param>
/// <param name="treeNode">The root node to which all other nodes should be added</param>
private void loopNodes(MyNode node, TreeNode treeNode) {

//Set the current TreeNode object text value to the current MyNode value
treeNode.Text = node.Value;

//Loop through all the children of the current node
foreach (MyNode mn in node.Children) {
//Create a new TreeNode object to add to the current TreeNode object
TreeNode innerNode = new TreeNode();
innerNode.Text = mn.Value;

//Add the innerNode to the treeNode as a child
treeNode.Nodes.Add(innerNode);
//Check if the child has any children
loopNodes(mn, innerNode);
}
}
}
}


End result (once again):
The end result (once again)


Article comments

Feel free to comment this article using a facebook profile.

I'm using facebook accounts for identification since even akismet couldn't handle all the spam I receive every day.