How to code a truly generic tree using Generics

Question

Lets say I have a Node class as follows:

    class Node<T>
    {
        T data;
        List<Node<T>> children;
        internal Node(T data)
        {
            this.data = data;
        }

        List<Node<T>> Children
        {
            get
            {
                if (children == null)
                    children = new List<Node<T>>(1);

                return children;
            }
        }

        internal IEnumerable<Node<T>> GetChildren()
        {
            return children;
        }

        internal bool HasChildren
        {
            get
            {
                return children != null;
            }
        }

        internal T Data
        {
            get
            {
                return data;
            }
        }



        internal void AddChild(Node<T> child)
        {
            this.Children.Add(child);
        }

        internal void AddChild(T child)
        {
            this.Children.Add(new Node<T>(child));
        }

    }

The problem is that each and every node of the tree is confined to a single type. However, there are situations where the root node is of one type, which has children of another type which has children of a third type (example documents-->paragraphs-->lines-->words).

How do you define a generic tree for such cases?

Answer 1

If you want a strict hierarchy of types you could declare them like this:

class Node<T, TChild> {...}

Node<Document, Node<Paragraph, Node<Line, Word>>>

I did not claim it would be pretty. :)

Answer 2

If you're not limited to C# 2.0, and can go C# 3.0 then Expression Trees may be the way to go.

Have a look at this as an example "Tree<T>: Implementing a Non-Binary Tree in C#"

...there are many similar one's out there.

Answer 3

Have all of your sub-objects implement a specific eg IDocumentPart then declare Node

Answer 4

How do you define a generic tree for such cases?

I wouldn't try to in the first place. If what I wanted to model was:

• I have a list of documents
• A document has a list of paragraphs
• A paragraph has a list of words

then why do you need generic nodes at all? Make a class Paragraph that has a List<Word>, make a class Document that has a List<Paragraph>, and then make a List<Document> and you're done. Why do you need to artificially impose a generic tree structure? What benefit does that buy you?

Answer 5

I have been reluctant to offer the code example attached, feeling that I don't have a strong sense, yet, of the "norms" of StackOverFlow in terms of posting code that may be "speculative," and, feeling that this particular frolic is some form of "mutant species" escaped from the laboratory on "The Island of Dr. Moreau" :) And, I do think the answer by Eric Lippert above is right-on.

So please take what follows with "a grain of salt" as just an experiment in "probing" .NET inheritance (uses FrameWork 3.5 facilities). My goal in writing this (a few months ago) was to experiment with an Abstract Class foundation for Node structure that implemented an internal List<> of "itself," then implement strongly-typed classes that inherited from the Abstract class ... and, on that foundation, build a generalized Tree data structure.

In fact I was surprised when I tested this, that it worked ! :)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

// experimental code : tested to a limited extent
// use only for educational purposes

namespace complexTree
{
    // foundation abstract class template
    public abstract class idioNode
    {
        // a collection of "itself" !
        public List<idioNode> Nodes { private set; get; }

        public idioNode Parent { get; set; }

        public idioNode()
        {
            Nodes = new List<idioNode>();
        }

        public void Add(idioNode theNode)
        {
            Nodes.Add(theNode);
            theNode.Parent = this;
        }
    }

    // strongly typed Node of type String
    public class idioString : idioNode
    {
        public string Value { get; set; }

        public idioString(string strValue)
        {
            Value = strValue;
        }
    }

    // strongly typed Node of type Int
    public class idioInt : idioNode
    {
        public int Value { get; set; }

        public idioInt(int intValue)
        {
            Value = intValue;
        }
    }

    // strongly type Node of a complex type
    // note : this is just a "made-up" test case
    // designed to "stress" this experiment
    // it certainly doesn't model any "real world"
    // use case
    public class idioComplex : idioNode
    {
        public Dictionary<idioString, idioInt> Value { get; set; }

        public idioComplex(idioInt theInt, idioString theString)
        {
            Value = new Dictionary<idioString, idioInt>();
            Value.Add(theString, theInt);
        }

        public void Add(idioInt theInt, idioString theString)
        {
            Value.Add(theString, theInt);
            theInt.Parent = this;
            theString.Parent = this;
        }
    }

    // special case the Tree's root nodes
    // no particular reason for doing this
    public class idioTreeRootNodes : List<idioNode>
    {
        public new void Add(idioNode theNode)
        {
            base.Add(theNode);
            theNode.Parent = null;
        }
    }

    // the Tree object
    public class idioTree
    {
        public idioTreeRootNodes Nodes { get; set; }

        public idioTree()
        {
            Nodes = new idioTreeRootNodes();
        }
    }
}

So, to the test : (call this code from some EventHandler on a WinForm) :

    // make a new idioTree
    idioTree testIdioTree = new idioTree();

    // make a new idioNode of type String
    idioString testIdioString = new idioString("a string");

    // add the Node to the Tree
    testIdioTree.Nodes.Add(testIdioString);

    // make a new idioNode of type Int
    idioInt testIdioInt = new idioInt(99);

    // add to Tree
    testIdioTree.Nodes.Add(testIdioInt);

    // make another idioNode of type String
    idioString testIdioString2 = new idioString("another string");

    // add the new Node to the child Node collection of the Int type Node
    testIdioInt.Nodes.Add(testIdioString2);

    // validate inheritance can be verified at run-time
    if (testIdioInt.Nodes[0] is idioString) MessageBox.Show("it's a string, idiot");

    if (!(testIdioInt.Nodes[0] is idioInt)) MessageBox.Show("it's not an int, idiot");

    // make a new "complex" idioNode
    // creating a Key<>Value pair of the required types of idioNodes
    idioComplex complexIdio = new idioComplex(new idioInt(88), new idioString("weirder"));

    // add a child Node to the complex idioNode
    complexIdio.Add(new idioInt(77), new idioString("too weird"));

    // make another idioNode of type Int
    idioInt idioInt2 = new idioInt(33);

    // add the complex idioNode to the child Node collection of the new Int type idioNode
    idioInt2.Nodes.Add(complexIdio);

    // add the new Int type Node to the Tree
    testIdioTree.Nodes.Add(idioInt2);

    // validate you can verify the type of idioComplex at run-time
    MessageBox.Show(" tree/2/0 is complex = " + (testIdioTree.Nodes[2].Nodes[0] is idioComplex).ToString());

If the "smell" of this code is as bad as the fruit that here in Thailand we call the "durian" : well, so be it :) An obvious possible "weirdness" in this experiment is that you could have references to the same Node in more than one place in the tree at the same time.