Hierarchical Tree Represented by Modified Preorder Tree Traversal Technique using C# 3.0 and SQL 2005

• Download demo project - 47.5 KB

Introduction

During my work in a (CMS) Content Management System, and in the module of Content-mapping (which is a .NET desktop application), I needed to classify my contents into a chain of categories like hierarchical tree, but I also needed to represent that tree into more than a format, such as Textual, Tabular, Nodes and Database.

I searched the web about which .NET library is going to represent my tree into the SQL2005 database. I couldn't find that library, but I found an article (Gijs Van Tulder) is titled Storing Hierarchical Data in a Database that explains the concept of the MPTT (Modified Preorder Tree Traversal). Unfortunately, it was written for PHP developers, so, I translated the concept into C# and SQL2005 code. Moreover, I wrote some algorithms to represent trees into textual, tabular, tree view nodes and graphical format. I also used provider model techniques as a step to support various databases such as SQLite.

Finally, I gathered all this stuff into one project, but, the entire classes could be easily reused and separated into class libraries, even the innovative algorithms (that I wrote) could be reused individually like the one that is written to render the graphical representation of the tree.

Now I think that I have an efficient way to add, insert, delete and retrieve tree-elements using many ways including a way for SQL2005 database with a very effective schema, which is MPTT that minimizes the number of database queries by having just one query for each activity.

What is Hierarchical Tree?

Simply, it is a structure of data that looks like a real tree, even though the hierarchical-tree is generally shown upside down compared with a real tree; that is to say with the root at the top and the leaves at the bottom, elements of that structure are related with each other by a parent-child relationship, those relationships are represented by a connecting-lines between elements and they are called "Branches", moreover, elements that have no superior are called "ROOTs" and elements that have no children are called "Leaves".

The following example demonstrates a textual representation for the Animal-kingdom tree:

Animal Kingdom
#Backbones
##Mammal
##Lungs
##Reptile
##Bird
##Gills
###Fish
###Amphibian
#No Backbones
##Starfish
##Mollusk
###Snail
###Clam
##Jointed Legs
###Insect
###Spider
###Crustacean

So we have 1 root (Animal Kingdom) and 12 leaves (Mammal, Lungs, Reptile, Bird, Fish, Amphibian, Starfish, Snail, Clam, Insect, Spider, Crustacean), we have 18 lines where each line contains one tree element/node, the count of (#)s in front of the node-title represents the depth level of the element in the tree, and elements that have the same level and have the same parent are called "SIBLINGs".

A graphical representation of such trees exist in Figure 2, where a rectangle is a symbolic representation of a node, and also a tabular representation for such trees exist in Figure 3.

Using the Demo Project

Back to the previous section, copy the text of Figure 1, and paste it into the TextBox of the right hand side on the interface of demo project, then, press the button that is titled "<<" to convert the text into the traditional tree representation in the TreeView control on the left hand side.

Show a tabular representation of the tree by clicking the radio button that is called "Tabular," and toggle between textual and tabular using the other radio button that is called "Textual".

To save the tree you just converted into SQL2005 database, you should first select an existing database, but you don't have to create any tables, just construct a working connection-string by clicking the button that is called "Connection String," after composing the connection string, simply click the button that is called "Save" to save the tree into a table called "tblTree," the table will be created automatically if it does not exist or is truncated if it is existing.

Of course, you could load this tree any time again from the same connection-string if you provided it correctly, just compose the connection string and click the "Load" button. However, you don't have to enter the connection string each time you open the demo project, it saves the connection string into a file named constring.txt automatically.

Now you can enjoy showing the graphical representation of the tree by clicking the "Draw" button.

Using the Code

You simply have to create an object from the MpttCoreEngine class and call any method from its interface.

MpttCoreEngine engine = new MpttCoreEngine();

This class contains all the algorithms that were written to represent hierarchical trees in various formats, the following list contains the most important methods in this class.

The following code is a snapshot from the demo project which demonstrates how to use those methods.

private void LoadDb()
{
    try
    {
        treeView.Nodes.Clear();
        TreeNode node = null;
        engine.SetConnectionString(_connectionString);
        node = engine.ConvertMpttIntoTree();
        if (node != null)
        {
            treeView.Nodes.Add(node);
            treeView.ExpandAll();
        }
    }
    catch (Exception e)
    {
        MessageBox.Show(e.Message +
                 "\r\nThe Connection string may not be correct");
    }
}

private void SaveDb()
{
    if (treeView.Nodes.Count <= 0)
        return;
    try
    {
        engine.SetConnectionString(_connectionString);
        engine.ConvertTreeIntoMptt(treeView.Nodes[0]);
    }
    catch (Exception e)
    {
        MessageBox.Show(e.Message +
                 "\r\nThe Connection string may not be correct");
    }
}

private void TreeReflection()
{
    char t = (delimiter.Text.Length > 0 ? delimiter.Text[0] : '#');
    engine.LevelDelimiter = t;
    //
    treeView.Nodes.Clear();
    TreeNode node = null;
    if (textual.Checked)
        node = engine.ConvertTextIntoTree(textView.Text, _delimiter, '*');
    else//tabular
        node = engine.ConvertTextTableIntoTree(textView.Text, true);
    if (node != null)
    {
        treeView.Nodes.Add(node);
        treeView.ExpandAll();
    }
}

private void TextReflection()
{
    if (treeView.Nodes.Count <= 0)
        return;
    char t = (delimiter.Text.Length > 0 ? delimiter.Text[0] : '#');
    engine.LevelDelimiter = t;
    if (textual.Checked)
    {
        textView.Text = engine.ConvertTreeIntoText(treeView.Nodes[0], false);
    }
    else
    {
        textView.Text = engine.ConvertTreeIntoTable(treeView.Nodes[0], false);
    }
}

private void btnDraw_Click(object sender, EventArgs e)
{
    if (treeView.Nodes.Count <= 0)
        return;
    Bitmap bmp = engine.DrawTree(treeView.Nodes[0]);
    TreePreview preview = new TreePreview(bmp);
    preview.Show();
}

Points of Interest

The code is full of interest points, where most of them may need individual articles to explain. Here are the most important ones:

1. The algorithm of drawing the tree nodes is so complex, I used anonymous functions, recursion and callbacks to calculate accurate locations for the nodes. You can find that algorithm on the function DrawTree.
2. The MPTT concept is explained in several places on the web, though, I composed that concept with a design pattern known by "provider model", where, an abstract class called TreeProvider is created to be implemented and supports any database type like SQL2005, MySQL or SQLite.
3. You could simply separate the core of the demo projects into a class library by copying only the folder named Core to any project you want.

History

Version 1.0

1. TreeView representation
2. Textual representation
3. Tabular representation
4. MPTT representation
5. Graphical representation
6. SQL2005 support