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