Implement a parent-child class hierarchy

Question

I'm finding it difficult to find a decent example on how to implement a parent-child hierarchy class. I have a treeView control that I want to convert into a class hierarchy, adding extra data to each node and be able to easely iterate over each parent's nodes using IEnumerable.

public IEnumerable<Node> GetAllChildsFromParent(Node parent)
{
    foreach (Node node in parent.NodeChildsCollection)
    {
        yield return node;
    }
}

I already have implemented the following piece of code but got stuck and don't really have a clue whether I am on the right track or not? How should I proceed to complete this ?

public class NodeChildsCollection : IEnumerable<Node>
{
    IList<Node> nodeCollection = new List<Node>();
    Node parent;

    public Node Parent
    {
        get { return parent; }
        set { parent = value; }
    }

    public NodeChildsCollection()
    {
    }


    public void AddNode(Node parent, Node child)
    {
        this.parent = parent;
        nodeCollection.Add(child);
    }

    #region IEnumerable<Node> Members

    public IEnumerator<Node> GetEnumerator()
    {
        foreach (Node node in nodeCollection)
        {
            yield return node;
        }
    }

    #endregion

    #region IEnumerable Members

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    #endregion
}

public class Node
{

    NodeChildsCollection nodeChildsCollection = new NodeChildsCollection();

    public Node Parent
    {
        get { return nodeChildsCollection.Parent; }
        set { nodeChildsCollection.Parent = value; }
    }


    public void AddChild(Node child)
    {
        nodeChildsCollection.AddNode(this, child);
    }
}

Answer 1

You're mixing the responsibilities of the Node with the responsibilities of the collection. See how you're setting the parent in the collection? It's not the collection that has a parent; its the node.

I'd structure my nodes like thus:

public class Node
{
  public Node Parent {get;set;} // null for roots

  public NodeCollection Children {get; private set;}

  public Node() 
  { 
    Children = new NodeCollection(); 
    Children.ChildAdded += ChildAdded;
    Children.ChildRemoved += ChildRemoved;
  };
  private void ChildAdded(object sender, NodeEvent args)
  {
    if(args.Child.Parent != null)
      throw new ParentNotDeadYetAdoptionException("Child already has parent");
    args.Child.Parent = this;
  }
  private void ChildRemoved(object sender, NodeEvent args)
  {
    args.Child.Parent = null;
  }
}

And the NodeCollection would look like

public class NodeCollection : INodeCollection {/*...*/}

and INodeCollection would be:

public interface INodeColleciton : IList<Node>
{
  event EventHandler<NodeEvent> ChildAdded;
  event EventHandler<NodeEvent> ChildRemoved;
}

The collection responsibilities are on the Child collection property of the Node. You can, of course, have node implement INodeCollection, but that's a matter of programming tastes. I prefer to have the Children public property (its how the framework is designed).

With this implementation you don't need to implement a "GetChildren" method; the public Children property provides them for all.

Answer 2

I found the this blog article quite useful when attempting to solve the same problem.

Answer 3

If you want to separate the notion of a tree-like data structure from the specific data being stored, make it a general purpose container by making it generic.

Also, if the tree has a single root, a treenode is itself a collection of treenodes, so (like any collection) the method for adding an item should be called Add. Making the child collection a separate object would only make sense if you often have collections of trees. This occurs in TreeViews in the Windows UI because the root of a TreeView contains multiple nodes rather than a single root treenode. However, in something like the XML or HTML DOM, there's always a single root, and so I think something simpler is appropriate.

Finally, you don't need to implement the IEnumerable stuff with yield return - just forward to a standard container's implementation.

public class TreeNode<TValue> : IEnumerable<TreeNode<TValue>>
{
    private List<TreeNode<TValue>> _children = new List<TreeNode<TValue>>();

    public TreeNode<TValue> Parent { get; private set; }

    public void Add(TreeNode<TValue> child)
    {
        _children.Add(child);
        child.Parent = this;
    }

    public void Remove(TreeNode<TValue> child)
    {
        _children.Remove(child);
        child.Parent = null;
    }

    public IEnumerator<TreeNode<TValue>> GetEnumerator()
    {
        return _children.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return _children.GetEnumerator();
    }      
}

In fact you could make it implement IList<TreeNode<TValue>> and forward all the methods on to the list, with appropriate manipulation of the Parent property whenever adding/removing children.