Tree structures in ASP.NET and SQL Server

Introduction

Trees can be an intuitively simply way of organising large amounts of information. We're exposed to them everywhere - from directories in file systems and categories in a web directory to hierarchies in organisations and family trees! Something like XML handles hierarchical data well, but if you've got a database full of data we want to associate with the tree - for example, a table full of articles - splitting our data store between XML and something like SQL Server isn't a particularly elegant option. Unfortunately, relational SQL doesn't make it especially easy to store these structures in such a way that we can perform useful (and efficient) operations over the trees.

This article looks at one way to represent trees in .NET - and how to map them to a table in SQL Server and back again - which should hopefully take the pain out of storing trees and manipulating them from .NET. Our aim will be to create an ASP.NET page that provides some standard "web directory" features including

  • Breadcrumbs
  • Listing sub-nodes in the current section
  • Indicating some of the children of these child nodes

whilst ensuring that we have zero limitations on the number of items in the tree, or its depth.

A diagram displaying the structure of the table, with these fields: id (int, primary key), parentId (int), name (varchar), depth (int), lineage (varchar).

I've referenced many articles on the subject in order to implement the SQL Server portion of this - in particular, Maintaining Hierarchies and More Trees & Hierarchies in SQL - so many thanks to those authors. I hope this proves to be a useful extension to their discussions, rather than just a rehash of old material! Naturally, any mistakes in the implementation I show here are mine alone - but please do point them out to me.

Representing trees in .NET

To start with, its probably useful to remind ourselves what exactly a tree is (!). Each element in a tree is known as a node - each node has zero or more child nodes, and the one at the top - with no parent - is the root of the tree. .NET doesn't currently have a built-in datatype for representing trees, but it's fairly straightforward to to create our own. We'll simply create a class to represent each "node" in the tree - which will consist of the following.

Property Name Data Type Description
UniqueID int A unique identifier for the node in this tree. As we're looking to store the tree in a relational database, this maps nicely to a primary/identity key, so we'll use an integer here. If we are creating a new TreeNode object that has not yet been associated with a unique identifier, this value will be zero.
ParentID int Used to identify the parent node of this object by storing the unique id of the parent. A parent ID of zero indicates that the node has no parent (ie it is a root node).
Name string A text value (not necessarily unique) to be associated with this node.
Children ArrayList<TreeNode> A collection of TreeNode objects that are children of this node. This will not necessarily contain all children that are in the original tree stored in our relational database - but will be populated appropriately depending on which queries we run.

The simple class shown below encapsulates this.

[Serializable]
public class TreeNode
{
    private int _uniqueID;
    private string _name;
    private int _parentID;
    private int _depth;
    private ArrayList _children;
    public TreeNode() { }
    public TreeNode(string name, int parentID) : this(0,name,parentID,-1)
    {
    }
    public TreeNode(int uniqueID, string name, int parentID, int depth)
    {
        _uniqueID = uniqueID;
        _name = name;
        _parentID = parentID;
        _depth = depth;
    }
    /// <summary>
    /// Gets or sets the unique ID associated with this category
    /// </summary>
    /// <remarks>Once a non-zero ID has been set, it may not be modified.</remarks>
    public int UniqueID
    {
        get { return _uniqueID; }
        set
        {
            if (_uniqueID == 0)
                _uniqueID = value;
            else
                throw new Exception("The UniqueID property cannot be modified once it has a non-zero value");
        }
    }
    public int Depth
    {
        get { return _depth; }
    }
    /// <summary>
    /// Gets or sets the label for this node
    /// </summary>
    public string Name
    {
        get { return _name; }
        set { _name = value; }
    }
    /// <summary>
    /// The ID of the parent node
    /// </summary>
    public int ParentID
    {
        get { return _parentID; }
        set { _parentID = value; }
    }
    /// <summary>
    /// Gets the children TreeNode objects for this category
    /// </summary>
    /// <remarks>In .NET 2.0, this can be modified to use generics, and have type ArrayList&lt;TreeNode></remarks>
    public ArrayList Children
    {
        get { return _children; }
        set { _children = value; }
    }
}

We're not going to actually use this class to create standalone tree structures along the lines we would if were were adding elements to, say, a TreeView control. The TreeNode's will be used to represent what we have stored in the database as a tree. However, if we want to add a TreeNode to the structure, the request is going to be made directly to the database - and the change will be reflected in a future request on the state of the tree structure. Likewise, if we modify the Name or ParentId of a TreeNode object, we'll need to tell the database that we've made this change.

You might also like...

Comments

About the author

James Crowley

James Crowley United Kingdom

James first started this website when learning Visual Basic back in 1999 whilst studying his GCSEs. The site grew steadily over the years while being run as a hobby - to a regular monthly audien...

Interested in writing for us? Find out more.

Contribute

Why not write for us? Or you could submit an event or a user group in your area. Alternatively just tell us what you think!

Our tools

We've got automatic conversion tools to convert C# to VB.NET, VB.NET to C#. Also you can compress javascript and compress css and generate sql connection strings.

“There are only two kinds of languages: the ones people complain about and the ones nobody uses” - Bjarne Stroustrup