Generic Tree <T> in C#

• Download demo project - 59.3 Kb

Preface

System.Collections.Generic lacks a container I need fairly often: a 1:N tree for storing hierarchical data. PH.DataTree provides this in a set of classes described below.

With the third update, there are already other tree containers offered on CP. What makes this one stand out:

• Convenient creation: After creating the root node, you always add values, not nodes.
• Change events for the tree structure and the contained value.
• A controller class to display the DTreeNode data in a Win Forms TreeView automatically, allowing a true model-view-controller structure (that is easy to use).
• Many common tasks, such as depth/breadth-first enumeration, and working with node paths.

Contents

• DTreeNode<T>

  Represents a tree node with a parent and 0..N child nodes. The node holds a single value of type T. For a root node, the parent is null.

• DTreeNodeCollection<T>

  Represents the list of child nodes. Every Node<T> has one. Since each tree starts with a DTreeNode, you cannot create the collection yourself.

• DTreeRoot<T>

  Provides the change events for a tree. The Root property of each DTreeNode that belongs to the same tree returns the same DTreeRoot instance. (Imagine the root node "has" a DTreeRoot, and all child nodes reference this instance.)

• DTreeBuilder<T>

  A helper class to quickly initialize some tree structure. Nothing special, see the unit test for an example.

• DTreeEventArgs<T>

  Holds event information for tree changes.

• TreeViewController<T>

  A controller class that maps a root DTreeNode<T> to a Windows.Forms.TreeView. Changing the DTreeNode<T> will automatically update the TreeView (almost always, anyway) - The sample application (xtree) demonstrates this.

• ITreeNodeMapper, TreeNodeDefaultMapper<T>

  Helper for TreeViewController, translating a data tree node (your type) into a TreeView node (i.e. which text, which image, etc.).

Example - building a tree

The following code builds a small tree of strings:

// assumes: using ph.tree

DTreeNode<string> root = new DTreeNode<string>();
DTreeNode<string> temp;

temp = root.Nodes.Add("Hello");
temp.Nodes.Add("olleH");

temp = root.Nodes.Add("World");
temp.Nodes.AddRange(new string[] 
        { "dWorl", "ldWor", "rldWo", "orldW" } );

Notice that for adding, you don't need to create nodes (except the root node). You just need to add elements of your data type T.

DTreeNode<T> public interface

General properties

Property	Type	access	description
Value	T	get, set	Your data value - whatever you want to store here.
Parent	DTreeNode<T>	get	The parent node - null, if this is the root node.
Nodes	DTreeNodeCollection<T>	get	Collection of child nodes (never null).
HasChildren	bool	get	true, if the node has any child (more efficient than Childs.Count==0, avoids creating the Childs collection for leaf nodes).
Siblings	NodeList<T>	get	The collection this node is part of (null for a root node), equivalent to Parent.Childs.
Root	TreeRoot<T>	get	Root gives access to a single root object per tree (i.e. a root node has its own instance, and all child nodes inherit it from their parent). The root node provides events like OnValueChanged and OnNodeChanged.
IsRoot	bool	get	true, if the node is the root node, equivalent to Parent==null.
Depth	int	get	Depth of this node: 0 for root node, 1 for direct root child etc.

Recursive iteration

The following properties return the recursive depth-first or breadth-first enumeration of either the values, or the elements. They can be used like this:

foreach(string s in rootNode.DepthFirstEnumerator) { ... }

The implementation was pried from Max Hajeks article [^] - thanks Max!

DepthFirstEnumerator	IEnumerable<T>	get	depth first, values
DepthFirstNodeEnumerator	IEnumerable<DTreeNode<T>>	get	depth first, nodes
BreadhtFirstEnumerator	IEnumerable<T>	get	breadth first, values
BreadhtFirstNodeEnumerator	IEnumerable<T>	get	breadth first, nodes

General methods

Remove	Removes the current node (and all children) from its parent. You can't do that for a root node! Note: for adding items, see DTreeNodeCollection<T> (accessible through DTreeNode<T>.Nodes)
IsAncesctorOf	bool IsAncestorOf(DTreeNode<T> other) returns true, if other is an ancestor (parent, grandparent, ..) of this. x.IsAncestorOf(x) returns false.
IsChildOf	bool IsAncestorOf(DTreeNode<T> other) returns true, if other is a child (or grandchild, ...) of this. x.IsChildOf(x) returns false. x.IsAncestorOf(y) <==> y.IsChildOf(x)
IsInLineWith	IsInLineWith(DTreeNode<T> node) returns true, if node and this are in a line of inheritance (node is an ancestor or child of this). x.IsInLineWith(x) returns true.

Node path support

GetNodePath	ICollection GetNodePath()returns the path from the root node to the current node in a collection of nodes.
GetElementNodePath	ICollection<T> GetElementNodePath()returns the path from the root node to the current node in a collection of values.
GetNodePathAsString	GetNodePathAsString(char separator, NodeToString<T> toString) GetNodePathAsString(char separator) returns the path from the root node to the current node. toString is a delegate translating your type T into a string (the default is T.ToString).
GetIndexPath	int[] GetIndexPath() returns an array with the child node indices that lead from the root to the node in question. The index path can be used in a call to GetNodeAt to retrieve the same node again (as long as the nodes haven't been removed or inserted before the respective nodes).
GetIndexPathTo	int[] GetIndexPathTo(DTreeNode<T> node) Like GetIndexPath, but from the current node to the node specified.
GetNodeAt	DTreeNode<T> GetNodeAt(int index) Returns the child node at the given index, equivalent to this.Nodes[index]. DTreeNode<T> GetNodeAt(IEnumerable<int> index) DTreeNode<T> GetNodeAt(params int[] index) Walks down the tree using child node indices (i.e. x.GetNodeAt(1,2,3) is equivalent to x.Nodes[1].Nodes[2].Nodes[3]) You can also use the return value of GetIndexPath for this.

DTreeNodeListCollection<T> public interface

The DTreeNodeCollection allows adding, modifying and accessing the child nodes of a given node. It inherits from "http://msdn2.microsoft.com/en-US/library/system.collections.collectionbase_members.aspx" target="_blank">System.Collections.CollectionBase, which implements important members (such as Count and RemoveAt), and the interfaces IList, ICollection and IEnumerable.

Public properties

Owner	Node<T>	get	The Node<T> this collection belongs to (never null).
this[]	Node<T>	get, set	Node<T> this[int index] { get; set; }Type safe indexer for the child nodes. You can only assign a root node or a node with the same parent node.

Public methods

Add	Node<T> Add(T value) Appends a node holding the given value, and returns the new node.
AddRange	void AddRange(IEnumerable<T> range)Appends multiple child nodes holding the given values.
InsertAt	Node<T> InsertAt(int index, T value)Inserts a child node at the given position, and returns the new node.
InsertRangeAt	Node<T> InsertRangeAt(int index, T value)Inserts multiple child nodes at the given position.
InsertBefore	Node<T> InsertBefore(Node<T> insertPos, T value)Inserts a new node holding the given value before the insertPos node, and returns the new node.
InsertAfter	Node<T> InsertAfter(Node<T> insertPos, T value)Inserts a new node holding the given value after the insertPos node, and returns the new node.
IndexOf	int IndexOf(Node<T> node)Returns the index of the given node, or -1 if the node is not in the collection.
Remove	void Remove(Node<T> node) removes the given node, if it is in the collection.

DTreeRoot<T> public interface

Public properties

.Root

Node<T>

get

The root node of the data.

Remember that a Node<T> is a perfectly valid data representation of a tree of T's. The reason for tree's existence are the events:

OnValueChanged	A new value was assigned to node.Value.
OnValueAccessed	A get access is about to occur for node.Value. The event fires before the value is accessed (so the event handler may modify the value). See below for more details.
OnNodeChanged	The structure of the tree has changed.

All events use a System.EventHandler delegate:

delegate System.EventHandler(object sender, System.EventArgs e)

The DTreeRoot object is passed as sender. The EventArgs e is actually a DTreeEventArgs<T> object with the following members:

Node	Node<T>	get	The DTreeNode<T> for which the event fires.
Change	ENodeEvent	get	Describes what happened with the node: ValueChanged: a new value was assigned to Node.Value. ValueAccessed: get access to Node.Value. NodeChanged: the node was replaced by a new one (typically by node.Childs[indx] = something). Note that this may be caused by the assignment of a whole sub tree, and that the value at this "tree location" has probably changed even though OnValueChanged didn't fire. ChildOrderChanged: Order of child nodes has changed (not used yet) ChildAdded: A child node was added at position index. ChildRemoved: A child node was removed from position index. This event does not fire for NodeList<T>.Clear()! ChildsCleared: All child nodes were removed.
Index	int	get	Index of the child node (for ChildAdded, ChildRemoved).

OnValueChanged - a little weakness

OnValueChanged works perfectly well if T is a value type. However, imagine the following reference type:

class MyNode
{
  public int Count = 0;
};

Tree<MyNode> tree = new Tree<MyNode>();
tree.Root.Childs.Add(new MyNode());
tree.Root.Childs[0].Value = new MyNode(); // fires 

                                          // OnValueChanged

tree.Root.Childs[0].Value.Count = 23;     // does not fire!

In the last line, Node.Value sees only a get call, and in turn does not fire the OnValueChanged event.

You may consider using the OnValueAccessed event for a workaround: for the last line, OnValueAccessed fires. This happens before the actual assignment, but you can store the affected nodes in a list, and use some lazy update mechanism to update the view.

TreeViewController<T>

If Node<T> is the core of these classes, TreeViewController<T> is a little gem. It provides both an example of what you can do with the events fired by Tree<T>, and also makes writing the example application wonderfully easy.

To connect a Tree with a TreeView, you need to instantiate a TreeViewController:

treeViewController = new TreeViewController<string>(treeView1, data);

where data is a Tree<string> and treeView1 is your trusty System.Windows.Forms.TreeView. The TreeViewController subscribes to the tree events and subsequently updates the tree whenever you operate on data:

data.Root.Childs.Add("Hello World!");

A new node, labeled "Hello World" is displayed immediately.

Node translation

SelectedNode

Node<T>

get, set

The node which is selected in the tree. null for no selection.

GetDataNode	DTreeNode<T> GetDataNode(TreeNode viewNode) returns the data node for a given view node, or null if viewNode was not found.
GetViewNode	TreeNode GetViewNode(DTreeNode<T> dataNode) returns the view node for a given data node, or null if dataNode was not found. Note: The implementation uses a recursive search.

Customizing the TreeNodes look

How is the TreeNode populated? You not only want to add strings - but also images, and control the label of your own node classes, etc.

TreeViewController accepts an optional third constructor parameter:

public TreeViewController(TreeView view, 
       DTreeNode<T> data, ITreeNodeMapper nodeMapper)

Implementing ITreeNodeMapper gives you control over two things:

• How to populate a TreeNode from your own node data type T.
• How to get from the TreeNode to the Node<T>.

Let's have a look at the default implementation:

public class TreeNodeDefaultMapper<T> : ITreeNodeMapper
{
   public void UpdateNode(object dataNode, TreeNode treeNode)
   {
      Node<T> dn = (Node<T>) dataNode;
      treeNode.Tag = dn;
      treeNode.Text = dn.Value.ToString();
   }

   public object GetNodeInfo(TreeNode treeNode)
   {
      return treeNode.Tag;
   }
}

UpdateNode populates a TreeNode from a Node<T> (dataNode). The default implementation stores the Node<T> as tag, and uses the generic Value.ToString() to determine the label. In your own implementation, you can set images, checkboxes and more!

GetNodeInfo helps to implement the mapping from TreeNode to Node<T> - by default, it just returns TreeNode.Tag.

Automatic sorting

Did you notice how the "Sort Order" selection from the sample application works? You can specify different sort criteria for the individual levels. All the sorting takes place while refreshing the tree, the original data in Node<T> is not affected. The usage is simple:

AutoSortCompare

IComparer<T>

get, set

A comparer for the sort order.

When you assign a new comparer, the tree is updated automatically. Also, when you insert new nodes, they respect the sort order. To display the items in original order, set AutoSortCompare to null.

Plans

I am thinking about adding the following things - feel free to comment:

• "Action Templates" for the TreeView.
• Better performance for remove (compared to detach).

  Currently, remove acts as detach, which is fairly expensive (a new root object is created and set for the child tree starting at the removed node, because the caller might still hold an external reference to the node removed).

• Some non-XML serialization. ([Serializable] sucks, I've not attempted to implement it for the time being. But if you ask for it, you will get it.)
• Sorting / automatic sorting of nodes to be added.
• Allowing a delegate for TreeViewController.AutoSortCompare.
• Sibling navigation (First, Last, Previous, Next).
• Feeding the TreeView "on demand".
• NDoc for the documentation (doesn't work yet for generics).

History

• 31^st Jan, 2006
  • Added unit tests for DTreeNode<T>.
  • Added GetIndexPath, GetIndexPathTo, GetNodeAt.
  • Added DTreeBuilder<T> (not documented here, helper class for quickly building simple trees).
• 29^th Jan , 2006
  • Added recursive iterators.
  • Added OnValueAccessed event.
• 7^th Jan, 2006
  • DTreeRoot (previously "Tree") moved into Node.
  • Changed some names (doh!).
  • Made FxCop almost happy.
• 1^st Jan, 2006
  • Initial version.