Click here to Skip to main content
Click here to Skip to main content

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

, 10 Dec 2008
Rate this:
Please Sign up or sign in to vote.
Gathering of various algorithms into one library to transform Hierarchical trees between various formats, and allows them to be represented into SQL2005, the formats supported are TreeView, Textual, Tabular, Modified Preorder Tree Traversal and Graphical.
demosmall.JPG

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 found 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 these staff 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
Figure 1: Hierarchical tree, textual representation.

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.

treesmall.JPG

Figure 2: Hierarchical tree graphical representation.
ID Parent ID Title Left Right
1 0 Animal Kingdom 1 36
2 1 Backbones 2 17
3 2 Mammal 3 4
4 2 Lungs 5 6
5 2 Reptile 7 8
6 2 Bird 9 10
7 2 Gills 11 16
8 7 Fish 12 13
9 7 Amphibian 14 15
10 1 No Backbones 18 35
11 10 Starfish 19 20
12 10 Mollusk 21 26
13 12 Snail 22 23
14 12 Clam 24 25
15 10 Jointed Legs 27 34
16 15 Insect 28 29
17 15 Spider 30 31
18 15 Crustacean 32 33
 
Figure 3: Hierarchical tree tabular representation.

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 in 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 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.

SetConnectionString Use this function to provide a connection string to the engine
ConvertMpttIntoTree Use this function to load tree nodes from the database
ConvertTreeIntoMptt Use this function to save tree nodes to database
ConvertTextIntoTree Converts textual tree into TreeNode suitable to TreeView
ConvertTextTableIntoTree Converts tabular tree into TreeNode suitable for TreeView
ConvertTreeIntoText Converts TreeNode back to textual representation
ConvertTreeIntoTable Converts TreeNode back to tabular representation
DrawTree Draws TreeNode on an Image and returns the Image for later use

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:

  1. 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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Wael Alghool
Architect Government
Qatar Qatar
Programmer since 1990 with Pascal, VC++, C#, ASP.NET, jQuery, J2EE and Android.
PMP Certified since 2009.
PSP Certified since 2005.
Business & System analyst since 2004.
Led teams in between 8 to 30 members.
Worked for www.harf.com, www.islamweb.net, islam.gov.qa and islamonline.net.

Comments and Discussions

 
GeneralMy vote of 5 Pinprofessionalashumeerut5-Aug-13 20:48 
QuestionHow to use it in asp.net website Pinprofessionalashumeerut5-Aug-13 20:04 
GeneralGreat Code Pinprofessionalashumeerut5-Aug-13 19:59 
Questionwill it work for sqlite? Pinmemberlovingwind24-May-12 1:44 
GeneralMy vote of 5 Pinmemberwasiuddin13-Oct-11 8:07 
GeneralQuestions PinmemberBBBrrriiiaaannn10-Oct-09 11:41 
Generaluse this code for Silverlight 3 TreeView via MVVM PinmemberGreg Hazzard31-Jul-09 2:32 
GeneralIts a great technique, but... PinmemberAdrian Schröder19-Jul-09 21:00 
QuestionPlease advise me... PinmemberDevil_Ashutosh16-Jun-09 0:11 
AnswerRe: Please advise me... PinmemberWael Alghool19-Jun-09 9:05 
Unfortunately, this version of the code is not optimized, but I have a recent version "not uploaded yet" that is optimized for high performance, according to my busy schedule, I could upload the new version with in three weeks, but I think the following code may help you for time beings, you may need also to enhance this portion of the code by using parameterized query and removing un-wanted fields.
 
//Insert Single Node Directly To Tree -->
public override int AddAndUpdateNode(MpttTreeNode node)
{
if (!InternalBeginUpdate())
return -1;
 
if (node.ID > 0)
{//Updateing existing one, don't update left, right or parent fields
SqlCommand cmd = new SqlCommand(string.Format(@"
UPDATE
{0} SET Title=@Title, unitID=@unitID ,divID=@divID, LeafID=@LeafID, defaultContent=@defaultContent
WHERE
ID=@ID", ContentTableName), con);
cmd.Parameters.AddWithValue("@Title", node.Title);
cmd.Parameters.AddWithValue("@unitID", node.UnitID);
cmd.Parameters.AddWithValue("@divID", node.DivID);
cmd.Parameters.AddWithValue("@defaultContent", node.ContentType);
cmd.Parameters.AddWithValue("@LeafID", node.LeafID);
cmd.Parameters.AddWithValue("@ID", node.ID);
ExecuteNonQuery(cmd);
}
else
{//Adding new one
// Get parent of the new node
MpttTreeNode parent = GetNodeByID(node.ParentID);
int nextleafID = GetNextLeafID();
 
//Output, provides you access to inserted and deleted logical tables.
// ....... BUT ............
//there is a limitation, where you have no choice than to use a workaround of "scope_identity"
//The limitation is: you cannot using OUTPUT without INTO for table which has triggers
//DML "Data Manipulation Language", puts this restriction
//SET NOCOUNT ON insert into MyTable values(...) select scope_identity() as id
//........................
 
//Output, provides you access to inserted and deleted logical tables.
SqlCommand cmd = new SqlCommand(string.Format(@"
DECLARE @MyTableVar table( ID int);
INSERT INTO
{0} (parentID,Title,lft,rgt,leafID,isLeaf,unitID,divID,defaultContent)
OUTPUT INSERTED.ID INTO @MyTableVar
VALUES
(@ParentID,@Title,@Left,@Right,@LeafID,@IsLeaf,@UnitID,@DivID,@defaultContent);
SELECT ID FROM @MyTableVar;", ContentTableName), con);
//cmd.CommandType = CommandType.TableDirect;
cmd.Parameters.AddWithValue("@Title", node.Title);
cmd.Parameters.AddWithValue("@ParentID", node.ParentID);
node.Left = (parent==null ? 1:parent.Right); // node left equals parent node right
cmd.Parameters.AddWithValue("@Left", node.Left);
node.Right = node.Left + 1; // node right equals node left + 1
cmd.Parameters.AddWithValue("@Right", node.Right);
cmd.Parameters.AddWithValue("@LeafID", nextleafID);
cmd.Parameters.AddWithValue("@IsLeaf", node.IsLeaf);
cmd.Parameters.AddWithValue("@UnitID", node.UnitID);
cmd.Parameters.AddWithValue("@DivID", node.DivID);
cmd.Parameters.AddWithValue("@defaultContent", node.ContentType);
//Object obj = ExecuteScalar(cmd);
node.ID = (int)ExecuteScalar(cmd);
node.LeafID = nextleafID;
 
//Update Nodes With Rights greater than my node right
cmd = new SqlCommand(string.Format(@"update {0} set lft=lft+2 , rgt=rgt+2 WHERE lft>{1} AND rgt>{1}", ContentTableName, node.Right), con);
ExecuteNonQuery(cmd);
 
//Update Bread Crump Nodes
cmd = new SqlCommand(string.Format(@"update {0} set rgt=rgt+2 WHERE (lft<{1} AND rgt>={2}) or (id={3})", ContentTableName, node.Left, node.Right, node.ParentID), con);
ExecuteNonQuery(cmd);
 
}
InternalEndUpdate();
//return the ID of the inserted record
return node.ID;//
}

//Delete Node With its Children
public override void DeleteNode(int id)
{
if (!InternalBeginUpdate())
return;
SqlCommand cmd = new SqlCommand(string.Format("SELECT * FROM {0} WHERE ID={1}", ContentTableName, id), con);
List<MpttTreeNode> nodes = GetNodeCollectionFromReader(ExecuteReader(cmd));
if (nodes.Count > 0)
{
MpttTreeNode node = nodes[0];
int ChildernCount = (node.Right - node.Left -1)/2;
int Difference = 2*(1+ChildernCount);
// Delete Node and its Children
cmd.CommandText = string.Format("DELETE FROM {0} WHERE (ID={1}) or (ParentID = {1})", ContentTableName, id);
ExecuteNonQuery(cmd);
// update Nodes after this deleted node
cmd.CommandText = string.Format("UPDATE {0} SET lft=lft-{1}, rgt=rgt-{1} WHERE lft>{2} AND rgt>{2}", ContentTableName,Difference, node.Right);
ExecuteNonQuery(cmd);
// update breadcrump nodes
cmd.CommandText = string.Format("UPDATE {0} SET rgt=rgt-{1} WHERE (lft<{2} AND rgt>={3}) or (id={4})", ContentTableName, Difference, node.Left, node.Right, node.ParentID);
ExecuteNonQuery(cmd);
}
InternalEndUpdate();
}
 

public override List<MpttTreeNode> GetSiblings(int nodeID)
{
if (!InternalBeginUpdate())
return null;
SqlCommand cmd = new SqlCommand(string.Format("SELECT * FROM {0} WHERE ID={1}", ContentTableName, nodeID), con);
List<MpttTreeNode> nodes = GetNodeCollectionFromReader(ExecuteReader(cmd));
List<MpttTreeNode> list = null;
if (nodes.Count > 0)
{
MpttTreeNode node = nodes[0];
cmd.CommandText = string.Format("SELECT * FROM {0} WHERE parentID={1} and NOT ID={2}", ContentTableName, node.ParentID, node.ID);
list = GetNodeCollectionFromReader(ExecuteReader(cmd));
}
else
list = null;
InternalEndUpdate();
return list;
}
// Get BreadCrump nods // Parent nodes // Parent Nodes Path //
public override List<MpttTreeNode> GetBreadCrump(int nodeID)
{
if (!InternalBeginUpdate())
return null;
MpttTreeNode node = GetNodeByID(nodeID);
SqlCommand cmd = new SqlCommand(string.Format("SELECT * FROM {0} WHERE lft<{1} and rgt>{2} Order By ParentID", ContentTableName, node.Left,node.Right), con);
List<MpttTreeNode> nodes = GetNodeCollectionFromReader(ExecuteReader(cmd));
InternalEndUpdate();
 
return nodes;
}
//-----------------------------------
// Move node with children to other parent // drag drop tree nodes
public override void MoveNode(MpttTreeNode child, MpttTreeNode newParent)//int nodeID , int newParentID)
{
//Case of: child is the root of the tree
if (child.ParentID == 0)
return;
//Get the root in order for future rebuild after updating
List<MpttTreeNode> parentBreadCrumbs = GetBreadCrump(newParent.ID);
if (parentBreadCrumbs.Count <= 0)
return;
MpttTreeNode rootNode = parentBreadCrumbs[0];
//Check conflict
parentBreadCrumbs.Reverse();//make parents before childs
foreach (MpttTreeNode bcNode in parentBreadCrumbs)
{
//Case of conflict: if moved node go to be a child of one of its children
if (bcNode.ID == child.ID)
return;
}
//Update and rebuild all
if (!InternalBeginUpdate())
return;
//
SqlCommand cmd = new SqlCommand(string.Format("UPDATE {0} SET ParentID={1} WHERE ID={2}",
ContentTableName, newParent.ID,child.ID), con);
ExecuteNonQuery(cmd);
RebuildTree(rootNode.ID, 1);
//
InternalEndUpdate();
}
 
public MpttTreeNode GetRootNode(int nodeID)
{
if (!InternalBeginUpdate())
return null;
MpttTreeNode rootNode = null;
MpttTreeNode Mynode = GetNodeByID(nodeID);
if (Mynode.ParentID == 0)
return Mynode;
List<MpttTreeNode> nodes = GetBreadCrump(nodeID);
nodes.Reverse();
foreach (MpttTreeNode node in nodes)
{
if (node.ParentID == 0)
{
rootNode = GetNodeByID(node.ID);
break;
}
}
return rootNode;
}
GeneralI could not find a solution file Pinmemberasanka_nilath30-Apr-09 3:08 
GeneralRe: I could not find a solution file PinmemberWael Alghool30-Apr-09 6:39 
Generali'm searching for a solution with HierarchyID Pinmemberhapalu7-Apr-09 6:12 
GeneralRe: i'm searching for a solution with HierarchyID PinmemberWael Alghool10-Apr-09 4:58 
GeneralRe: i'm searching for a solution with HierarchyID Pinmemberhapalu15-Apr-09 22:06 
GeneralIts Great Sir. Pinmembervicky95-Feb-09 20:42 
GeneralRe: Its Great Sir. PinmemberWael Alghool7-Feb-09 22:41 
Generalgood job PinmemberEka Abdurachman17-Jan-09 21:52 
GeneralExcellent PinmemberDr.Luiji11-Dec-08 11:46 
GeneralRe: Excellent PinmemberWael Alghool11-Dec-08 22:43 
GeneralRe: Excellent PinmemberDr.Luiji12-Dec-08 1:19 
GeneralRe: Excellent Pinmembervicky95-Feb-09 20:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140814.1 | Last Updated 10 Dec 2008
Article Copyright 2008 by Wael Alghool
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid