Building Trees from Lists in .NET

작성자 admin 작성일자 12th 6월 2017

Is your email address OK? You are signed up for our newsletters but your email address is either unconfirmed, or has not been reconfirmed in a long time. Please click here to have a confirmation email sent so we can confirm your email address and start sending you newsletters again. Alternatively, you can update Treelistyour subscriptions.

Download source code for .NET 2.0 projects – 3.29 KB
(A single CS file to be included in your .NET 2.0 project)
Download source code for .NET 3.5 projects – 3.29 KB
(A single CS file to be included in your .NET 3.5+ project)

Who Is This Article For?

This article is aimed at .NET developers who need to build a tree (or forest) of objects by loading an array or list of rows from a database, and converting them to a tree structure in memory to use or display.

Introduction

Storing hierarchical data in a database is a very common requirement, whether it be product categories, sports tournaments, or staff hierarchies. Over the years, I have had to create, store in a database and display trees many times, and my method has evolved from having fixed-size hierarchies, to abstract classes providing tree functionality, and finally to the method described in this article. This article describes a very simple way to load data from a table, and convert it into a tree in C# code for .NET 2.0+.
While other articles have been written on the subject, the following goals are not always met:

You should not need to extend an abstract class, because your data class may already extend another class
You shouldn’t need to convert your class to be a partial class
You shouldn’t need to change your database table: as long as it uses the standard parent ID column referring to its own primary key, it should work
There shouldn’t need to be any type-casting of parent or child objects
It should be easy to use

The answer is to define an interface – in this case called ITreeNode<t /> – and then have a utility method to build a tree from that. This article assumes that you have a class defined to hold a single node (e.g. a Categoryobject), and that when you get a list of nodes from the database each reference to a parent has been instantiated as an object with its ID set, but without a reference to the fully populated parent object, nor its children.

An Example

Let’s look at the very common “Category” entity, used to categorise products. The database table looks like the following:
Let’s assume that there are just 8 rows in the database, which break the products into two main categories – “Hardware” and “Software” – and then further sub-categories. In this case “Operating Systems” and “Developer Tools” come under “Software”; “Monitors” and “Peripherals” under “Hardware”, and finally “Keyboards” and “Mice” under “Peripherals”, giving the following category hierarchy:
In the database, the rows are as follows:
In order to display this information on a website, you create a “Category” class:

Hide Shrink

Copy Code

public class Category
{
    private int _id;
    private string _name;
    private Category _parent;
    private List<Category> _children;
    public int Id
    {
        get { return _id; }
        set { _id = value; }
    }
    public string Name
    {
        get { return _name; }
        set { _name = value; }
    }
    public Category Parent
    {
        get { return _parent; }
        set { _parent = value; }
    }
    public List<Category> Children
    {
        get { return _children; }
        set { _children = value; }
    }
}

A method is also needed to retrieve all the categories from the database. This will be a “flat” list of each category, i.e. the _parent field will point to an object which only has its ID populated, and _children will be null. A possible example of this method is shown here:

Hide Copy Code

static List<Category> GetListFromDatabase(DbConnection con) {
    DbCommand cmd = con.CreateCommand();
    cmd.CommandText = "SELECT Id, Name, ParentID FROM Category";
    cmd.CommandType = CommandType.Text;
    DbDataReader reader = cmd.ExecuteReader();
    List<Category> categories = new List<Category>();
    foreach (DbDataRecord row in reader) {
        Category c = new Category();
        c.Id = (int)row["Id"];
        c.Name = (string)row["Name"];
        if (row["ParentID"] != DBNull.Value)
        {
            c.Parent = new Category();
            c.Parent.Id = (int)row["ParentID"];
        }
        categories.Add(c);
    }
    reader.Close();
    return categories;
}

Once having a list of objects in memory, the ITreeNode interface comes in handy. The first step is to implement this interface:

Hide Copy Code

public class Category : ITreeNode<Category> {
// contents of class remain as above, because the 
// interface is implemented by the Id, Parent, and 
// Children properties
}

The interface requires that we have one property referring to the parent of the category (where null represents a root-level node), and an IList pointing to the children.
Now we can call the TreeHelper utility methods to convert the flat array returned from GetListFromDatabase into a fully populated hierarchy:

Hide Copy Code

IList<Category> topLevelCategories =
    TreeHelper.ConvertToForest(GetListFromDatabase());

The variable topLevelCategories contains two Categories: “Software” and “Hardware”.

Printing Out All Nodes using Nested HTML <ul> and <li> Tags

Using a recursive method, you can easily print out, for example, the full category hierarchy in nested <ul> tags, as follows:

Hide Copy Code

void Page_Load(object sender, EventArgs e) {
    IList<Category> topLevelCategories =
        TreeHelper.ConvertToForest(Category.GetListFromDatabase());
    Response.Write("<ul>");
    foreach(Category topLevelCategory in topLevelCategories) {
        RenderCategory(topLevelCategory);
    }
    Response.Write("</ul>");
}
void RenderCategory(Category category) {
    Response.Write("<li>" + category.Name);
    if (category.Children.Count > 0) {
        Response.Write("<ul>");
        foreach(Category child in category.Children) {
            RenderCategory(child);
        }
        Response.Write("</ul>");
    }
    Response.Write("</li>");
}

This will render the following output:

Software
- Operating Systems
- Developer Tools
Hardware
- Monitors
- Peripherals
  - Keyboards
  - Mice

Searching For a Single Category in the Tree

Hide Copy Code

// in a website, this may use the ASP.NET Cache object.
List<Category> categories = GetCategories();
int categoryId = int.Parse(Request.Params["categoryId"]);
Category currentCategory =
    TreeHelper.FindTreeNode(categories, categoryId);

Printing Breadcrumbs

Continuing the example above, this is how the bread crumbs for the current category could be printed:

Hide Copy Code

Category currentCategory = GetCategory();
foreach(Category category in
    TreeHelper.Iterators.FromRootToNode(currentCategory))
{
    Response.Write(" / " + category.Name);
}

If the current category was “Keyboards”, this would render the following HTML:

Hide Copy Code

/ Hardware / Peripherals / Keyboards

Tree Helper

The TreeHelper utility class contains numerous other useful methods – such as GetDepth and HasHierarchyLoop – and iterators – such as DepthFirstTraversal, BreadthFirstTraversal, ClimbToRoot, FromRootToNode, and Siblings.
Check out the fully-documented source code for the full details.

Using Extension Methods and “LINQ to Trees”

If you are using a .NET 3.5 solution, you are able to take advantage of extension methods. This has the effect of implementing methods in interface declarations (which is not possible in older versions of C#), which is probably the most useful aspect of extension methods, and indeed was the reason they were invented.
An example using extension methods:

Hide Copy Code

List<Category> categories = GetCategories().ConvertToForest();
Category current = categories.FindCategory(3);
foreach(Category descendent in current.DepthFirstTraversal()) {
    Response.Write("Depth of " + descendent.Name + ": " + descendent.GetDepth();
}

Remember, ConvertToForest, FindCategory, DepthFirstTraversal and GetDepth are not implemented by the Category class, it simply “inherits” these methods from the TreeHelper class, simply by implementing ITreeNode<T>.
Extension methods go hand-in-hand with LINQ. Yes, strictly speaking, this is simply “LINQ to Objects” rather than “LINQ to trees”, but regardless, it is a new way to query your trees:

Hide Copy Code

List<Category> categoryList = Category.GetCategories();
// Get all categories which are not top level categories, 
// and retrieve only the name.
var nonRootCategories =
    from c in categoryList.DepthFirstTraversalOfList()
    where c.Parent != null
    select new { Name = c.Name };
// Get all categories at Depth 2, ordered by name, and
// get the whole category object.
var level2Categories =
    from c in categoryList.DepthFirstTraversalOfList()
    where c.GetDepth() == 2
    orderby c.Name ascending
    select c;