Click here to Skip to main content
15,867,568 members
Articles / Programming Languages / C#
Article

Generic Tree <T> in C#

Rate me:
Please Sign up or sign in to vote.
4.70/5 (27 votes)
28 Jan 2006CPOL10 min read 352.1K   5.9K   107   63
A generic 1:(0..N) tree container with change events and automatic updating of a TreeView.

Image 1

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:

C#
// 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

PropertyTypeaccessdescription
ValueTget, setYour data value - whatever you want to store here.
ParentDTreeNode<T>getThe parent node - null, if this is the root node.
NodesDTreeNodeCollection<T>getCollection of child nodes (never null).
HasChildrenboolgettrue, if the node has any child (more efficient than Childs.Count==0, avoids creating the Childs collection for leaf nodes).
SiblingsNodeList<T>getThe collection this node is part of (null for a root node), equivalent to Parent.Childs.
RootTreeRoot<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.

IsRootboolgettrue, if the node is the root node, equivalent to Parent==null.
DepthintgetDepth 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:

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

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

DepthFirstEnumeratorIEnumerable<T>getdepth first, values
DepthFirstNodeEnumeratorIEnumerable<DTreeNode<T>>getdepth first, nodes
BreadhtFirstEnumeratorIEnumerable<T>getbreadth first, values
BreadhtFirstNodeEnumeratorIEnumerable<T>getbreadth first, nodes


General methods

RemoveRemoves 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)
IsAncesctorOfbool IsAncestorOf(DTreeNode<T> other)
returns true, if other is an ancestor (parent, grandparent, ..) of this. x.IsAncestorOf(x) returns false.
IsChildOfbool 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)
IsInLineWithIsInLineWith(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

GetNodePathICollection GetNodePath()returns the path from the root node to the current node in a collection of nodes.
GetElementNodePathICollection<T> GetElementNodePath()returns the path from the root node to the current node in a collection of values.
GetNodePathAsStringGetNodePathAsString(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).
GetIndexPathint[] 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).
GetIndexPathToint[] 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 <a href="http://msdn2.microsoft.com/en-US/library/system.collections.collectionbase_members.aspx" target="_blank">System.Collections.CollectionBase</a>, which implements important members (such as Count and RemoveAt), and the interfaces IList, ICollection and IEnumerable.

Public properties

OwnerNode<T>getThe Node<T> this collection belongs to (never null).
this[]Node<T>get, setNode<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

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

DTreeRoot<T> public interface

Public properties

.RootNode<T>getThe 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:

OnValueChangedA new value was assigned to node.Value.
OnValueAccessedA 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.
OnNodeChangedThe structure of the tree has changed.

All events use a System.EventHandler delegate:

C#
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:

NodeNode<T>getThe DTreeNode<T> for which the event fires.
ChangeENodeEventget

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.
IndexintgetIndex 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:

C#
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:

C#
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:

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

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

Node translation

SelectedNodeNode<T>get, setThe node which is selected in the tree. null for no selection.

GetDataNodeDTreeNode<T> GetDataNode(TreeNode viewNode)
returns the data node for a given view node, or null if viewNode was not found.
GetViewNodeTreeNode 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:

C#
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:

C#
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:

AutoSortCompareIComparer<T>get, setA 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

  • 31st 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).
  • 29th Jan , 2006
    • Added recursive iterators.
    • Added OnValueAccessed event.
  • 7th Jan, 2006
    • DTreeRoot (previously "Tree") moved into Node.
    • Changed some names (doh!).
    • Made FxCop almost happy.
  • 1st Jan, 2006
    • Initial version.

License

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


Written By
Klippel
Germany Germany
Peter is tired of being called "Mr. Chen", even so certain individuals insist on it. No, he's not chinese.

Peter has seen lots of boxes you youngsters wouldn't even accept as calculators. He is proud of having visited the insides of a 16 Bit Machine.

In his spare time he ponders new ways of turning groceries into biohazards, or tries to coax South American officials to add some stamps to his passport.

Beyond these trivialities Peter works for Klippel[^], a small german company that wants to make mankind happier by selling them novel loudspeaker measurement equipment.


Where are you from?[^]



Please, if you are using one of my articles for anything, just leave me a comment. Seeing that this stuff is actually useful to someone is what keeps me posting and updating them.
Should you happen to not like it, tell me, too

Comments and Discussions

 
GeneralWeb Tree view Pin
lastzerocool23-Jun-06 7:30
lastzerocool23-Jun-06 7:30 
GeneralRe: Web Tree view Pin
peterchen27-Jun-06 10:36
peterchen27-Jun-06 10:36 
GeneralWeb TreeView Pin
lastzerocool5-Jun-06 3:11
lastzerocool5-Jun-06 3:11 
GeneralPassword required Pin
Jian123456710-May-06 10:05
Jian123456710-May-06 10:05 
GeneralRe: Password required Pin
peterchen10-May-06 19:09
peterchen10-May-06 19:09 
GeneralRe: Password required Pin
jimmygyuma5-Apr-08 4:34
jimmygyuma5-Apr-08 4:34 
GeneralRe: Tags in DTree Pin
martintr5-Feb-06 20:23
martintr5-Feb-06 20:23 
GeneralRe: Tags in DTree Pin
peterchen14-Feb-06 6:07
peterchen14-Feb-06 6:07 
hi again,

I'm workign on a followup article, which would also explain your problem. However, due to "things" this takes longer than I wanted.

Could you solve your problem?
if not, maybe you can send me an example project where you try to use it, and I see what I can do?!

send a private e-mail, andI give you the address to reply to





Some of us walk the memory lane, others plummet into a rabbit hole

Tree<t> in C# || Fold With Us! || sighist

GeneralRe: Tags in DTree Pin
martintr14-Feb-06 10:31
martintr14-Feb-06 10:31 
GeneralRe: using Tags in DTreeNode Pin
martintr5-Feb-06 13:09
martintr5-Feb-06 13:09 
GeneralRe: using Tags in DTreeNode Pin
peterchen5-Feb-06 20:21
peterchen5-Feb-06 20:21 
GeneralRe: Trying to use Tags in XTree Pin
martintr5-Feb-06 10:30
martintr5-Feb-06 10:30 
GeneralRe: Trying to use Tags in XTree Pin
peterchen5-Feb-06 12:21
peterchen5-Feb-06 12:21 
GeneralHelp with adding Tags to TreeView Pin
martintr5-Feb-06 0:23
martintr5-Feb-06 0:23 
GeneralRe: Help with adding Tags to TreeView Pin
peterchen5-Feb-06 2:56
peterchen5-Feb-06 2:56 
GeneralFor a first time C# experiment... Pin
Nish Nishant6-Jan-06 2:42
sitebuilderNish Nishant6-Jan-06 2:42 
GeneralTree Templates Pin
Marc Clifton6-Jan-06 2:16
mvaMarc Clifton6-Jan-06 2:16 
GeneralRe: Tree Templates Pin
peterchen6-Jan-06 3:08
peterchen6-Jan-06 3:08 
GeneralRe: Tree Templates Pin
peterchen6-Jan-06 23:54
peterchen6-Jan-06 23:54 
GeneralNomenclature Pin
Shawn Poulson4-Jan-06 1:55
Shawn Poulson4-Jan-06 1:55 
GeneralRe: Nomenclature Pin
peterchen4-Jan-06 3:48
peterchen4-Jan-06 3:48 
GeneralRe: Nomenclature Pin
Shawn Poulson4-Jan-06 5:33
Shawn Poulson4-Jan-06 5:33 
GeneralRe: Nomenclature Pin
peterchen4-Jan-06 7:19
peterchen4-Jan-06 7:19 
GeneralRe: Nomenclature Pin
Shawn Poulson4-Jan-06 10:09
Shawn Poulson4-Jan-06 10:09 
GeneralRe: Nomenclature Pin
peterchen4-Jan-06 12:02
peterchen4-Jan-06 12:02 

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.