Click here to Skip to main content
15,870,130 members
Articles / Programming Languages / C#

Simple Generic Tree

Rate me:
Please Sign up or sign in to vote.
4.25/5 (15 votes)
6 Sep 2012CPOL4 min read 43.4K   943   24   6
Simple Generic Tree in c#
C#
public abstract class TreeNodeBase<T> : ITreeNode<T> where T : class, ITreeNode<T>

Introduction

I wanted to create an abstract base class for an existing tree class. This seemed like a quick copy and paste job but turned out to be not as simple as I first thought.

The base class had to be able to do all of the basic tree handling such as Add Child Nodes, Get the Root of the Tree, Get the Parent of the current Node, etc. The concrete class had to be able to extend and use the base class tree functionality, and I didn't want any casting. I wanted a base class that implemented all of the standard functionality of a tree as opposed to a set of interfaces.

Background

After copying the existing class to form the basis of the abstract base class, I quickly cut out the code that was specific to the concrete class, thus leaving the basic tree code. I quickly turned this into a generic class of T and then this is when the fun started. I started to hit a few problems at this stage, so thought I would check out CodeProject. I quickly found some other articles, but they did not fulfill all of my criteria. They were typically a wrapper class for the node, so the concrete class was not aware of the tree.

Getting Started

After a couple of false starts I thought I would try something that I wasn't sure was possible using Generics. I decided to have the concrete class inherit from a generic class of itself. It seemed to compile OK, so I thought I would continue down this path and see where it took me.

So the start of my Generic tree looked like this:

C#
//------------------------------------------------------------------------------
/// <summary>
/// Generic Tree Node base class
/// </summary>
/// <typeparam name="T"></typeparam>
//------------------------------------------------------------------------------
public abstract class TreeNodeBase<T>  
 //------------------------------------------------------------------------------
/// <summary>
/// Concrete class that inherits from the TreeNode Base 
/// </summary>
//------------------------------------------------------------------------------
public class SpecialTreeNode : TreeNodeBase<SpecialTreeNode>

OK, time to put some meat on the bone. I added in properties for the list of child nodes and the parent node plus a name of the current node. Things looked good. I continued, and implemented properties for IsLeaf and IsRoot and still looking good.

So my base class now looked something like this:

C#
//------------------------------------------------------------------------------
/// <summary>
/// Generic Tree Node base class
/// </summary>
/// <typeparam name="T"></typeparam>
//------------------------------------------------------------------------------
public abstract class TreeNodeBase<T> 
{

    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    /// <param name="name"></param>
    //------------------------------------------------------------------------------
    protected TreeNodeBase(string name)
    {
        Name = name;
        ChildNodes = new List<T>();
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// Name
    /// </summary>
    //------------------------------------------------------------------------------
    public string Name
    {
        get;
        private set;
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// Parent
    /// </summary>
    //------------------------------------------------------------------------------
    public T Parent
    {
        get;
        set;
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// Children
    /// </summary>
    //------------------------------------------------------------------------------
    public List<T> ChildNodes
    {
        get;
        private set;
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// True if a Leaf Node
    /// </summary>
    //------------------------------------------------------------------------------
    public bool IsLeaf
    {
        get { return ChildNodes.Count == 0; }
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// True if the Root of the Tree
    /// </summary>
    //------------------------------------------------------------------------------
    public bool IsRoot
    {
        get { return Parent == null; }
    }
}

Problem 1: this

I went to add a method to add a child node to the current node, but quickly found my first problem. I couldn't set the new child node's parent to this because it could not cast this to type T.

C#
//------------------------------------------------------------------------------
/// <summary>
/// Add a Child Tree Node
/// </summary>
/// <param name="child"></param>
//------------------------------------------------------------------------------
public void AddChild(T child)
{
    child.Parent = this;  // Cant do this as cannot cast this to Type T
    ChildNodes.Add(child);
}

//------------------------------------------------------------------------------
/// <summary>
/// Add a collection of child Tree Nodes
/// </summary>
/// <param name="children"></param>
//------------------------------------------------------------------------------
public void AddChildren(IEnumerable<T> children)
{
    foreach (T child in children)
        AddChild(child);
}

This was resolved by getting this from a property implemented in the concrete class.

In the base class:

C#
//------------------------------------------------------------------------------
/// <summary>
/// this
/// </summary>
//------------------------------------------------------------------------------
protected abstract T MySelf
{
    get;
}

The implementation in the concrete class:

C#
protected override SpecialTreeNode MySelf
{
    get { return this; }
}

So now wherever the base class need this, I could use MySelf.

C#
public void AddChild(T child)
{
    child.Parent = MySelf;
    ChildNodes.Add(child);
}

Problem 2: what is T

I went to implement the next method which was to get the root node from the current node, but the Parent node is of type T and type T has an unknown implementation in the base class.

C#
//------------------------------------------------------------------------------
/// <summary>
/// Get the Root Node of the Tree
/// </summary>
//------------------------------------------------------------------------------
public T GetRootNode()
{
    if (Parent == null)
        return MySelf;

    return Parent.GetRootNode();  // T does not contain a definition for GetRootNode
}

To solve this problem was to basically solve the puzzle. I implemented a generic interface for the properties and methods the base class need to know about. The nice bit is that the base class implements the interface which allows the base class to know about itself (if you know what I mean).

The interface

C#
//------------------------------------------------------------------------------
/// <summary>
/// 
/// </summary>
/// <typeparam name="T"></typeparam>
//------------------------------------------------------------------------------
public interface ITreeNode<T>
{

    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    //------------------------------------------------------------------------------
    T Parent { get; set; }

    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    //------------------------------------------------------------------------------
    bool IsLeaf { get; }

    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    //------------------------------------------------------------------------------
    bool IsRoot { get; }

    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    //------------------------------------------------------------------------------
    T GetRootNode();

    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    //------------------------------------------------------------------------------
    string GetFullyQualifiedName();
}

The base class declaration now looks like this:

C#
public abstract class TreeNodeBase<T> : ITreeNode<T> where T : class, ITreeNode<T>

which allowed me to complete the base class methods. It now looked like this:

C#
//------------------------------------------------------------------------------
/// <summary>
/// Generic Tree Node base class
/// </summary>
/// <typeparam name="T"></typeparam>
//------------------------------------------------------------------------------
public abstract class TreeNodeBase<T> : ITreeNode<T> where T : class, ITreeNode<T>
{

    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    /// <param name="name"></param>
    //------------------------------------------------------------------------------
    protected TreeNodeBase(string name)
    {
        Name = name;
        ChildNodes = new List<T>();
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// Name
    /// </summary>
    //------------------------------------------------------------------------------
    public string Name
    {
        get;
        private set;
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// Parent
    /// </summary>
    //------------------------------------------------------------------------------
    public T Parent
    {
        get;
        set;
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// Children
    /// </summary>
    //------------------------------------------------------------------------------
    public List<T> ChildNodes
    {
        get;
        private set;
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// this
    /// </summary>
    //------------------------------------------------------------------------------
    protected abstract T MySelf
    {
        get;
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// True if a Leaf Node
    /// </summary>
    //------------------------------------------------------------------------------
    public bool IsLeaf
    {
        get { return ChildNodes.Count == 0; }
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// True if the Root of the Tree
    /// </summary>
    //------------------------------------------------------------------------------
    public bool IsRoot
    {
        get { return Parent == null; }
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// List of Leaf Nodes
    /// </summary>
    //------------------------------------------------------------------------------
    public List<T> GetLeafNodes()
    {
        return ChildNodes.Where(x => x.IsLeaf).ToList();
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// List of Non Leaf Nodes
    /// </summary>
    //------------------------------------------------------------------------------
    public List<T> GetNonLeafNodes()
    {
        return ChildNodes.Where(x => !x.IsLeaf).ToList();
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// Get the Root Node of the Tree
    /// </summary>
    //------------------------------------------------------------------------------
    public T GetRootNode()
    {
        if (Parent == null)
            return MySelf;

        return Parent.GetRootNode();
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// Dot separated name from the Root to this Tree Node
    /// </summary>
    //------------------------------------------------------------------------------
    public string GetFullyQualifiedName()
    {
        if (Parent == null)
            return Name;

        return string.Format("{0}.{1}", Parent.GetFullyQualifiedName(), Name);
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// Add a Child Tree Node
    /// </summary>
    /// <param name="child"></param>
    //------------------------------------------------------------------------------
    public void AddChild(T child)
    {
        child.Parent = MySelf;
        ChildNodes.Add(child);
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// Add a collection of child Tree Nodes
    /// </summary>
    /// <param name="children"></param>
    //------------------------------------------------------------------------------
    public void AddChildren(IEnumerable<T> children)
    {
        foreach (T child in children)
            AddChild(child);
    }
}

The only thing that I am not entirely happy with is that the parent has a public setter due to the interface.

Concrete class specialisation

To prove that it fulfills all of my original criteria, I had to add some specialisation to my concrete class and see that I could truly leverage the base class from it. So I added a property called IsSpecial and a couple of methods to get the special nodes (i.e., child nodes where IsSpecial is true), and another method to get the special leaf nodes. This would prove that it new about the tree and could make use of the base class properties.

C#
//------------------------------------------------------------------------------
/// <summary>
/// 
/// </summary>
//------------------------------------------------------------------------------
public class SpecialTreeNode : TreeNodeBase<SpecialTreeNode>
{
    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    /// <param name="name"></param>
    //------------------------------------------------------------------------------
    public SpecialTreeNode(string name)
        : base(name)
    {
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    //------------------------------------------------------------------------------
    protected override SpecialTreeNode MySelf
    {
        get { return this; }
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    //------------------------------------------------------------------------------
    public bool IsSpecial
    {
        get;
        set;
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    /// <returns></returns>
    //------------------------------------------------------------------------------
    public List<SpecialTreeNode> GetSpecialNodes()
    {
        return ChildNodes.Where(x => x.IsSpecial).ToList();
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    /// <returns></returns>
    //------------------------------------------------------------------------------
    public List<SpecialTreeNode> GetSpecialLeafNodes()
    {
        return ChildNodes.Where(x => x.IsSpecial && x.IsLeaf).ToList();
    }

    //------------------------------------------------------------------------------
    /// <summary>
    /// 
    /// </summary>
    /// <returns></returns>
    //------------------------------------------------------------------------------
    public List<SpecialTreeNode> GetSpecialNonLeafNodes()
    {
        return ChildNodes.Where(x => x.IsSpecial && !x.IsLeaf).ToList();
    }
}

Using the code

To use the base class, simply create a concrete class and inherit from the TreeNoderBase class where the generic type is your concrete class.

C#
public class SpecialTreeNode : TreeNodeBase<SpecialTreeNode>

You should now have a fully functioning tree that you can begin to specialise. (From above) I implemented the SpecialTreeNode class and performed a few tests to see that it all checked out.

You can see the tests in the source code, but here are the results:

Points of interest

I like that the class inherits from a generic class of itself. I also like that base class relies on the generic interface to know about itself so that it can implement the interface. It is all very circular but quite pretty in the end.

History

  • v1.0 12 March 2012: Initial release.

License

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


Written By
United Kingdom United Kingdom
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralMy vote of 3 Pin
Vitaly Tomilov6-Sep-12 11:47
Vitaly Tomilov6-Sep-12 11:47 
GeneralRe: My vote of 3 Pin
alc_aardvark11-Sep-12 7:25
alc_aardvark11-Sep-12 7:25 
GeneralRe: My vote of 3 Pin
Thornik26-Sep-21 8:08
Thornik26-Sep-21 8:08 

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

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