Click here to Skip to main content
Click here to Skip to main content
Go to top

Generic Tree <T> in C#

, 28 Jan 2006
Rate this:
Please Sign up or sign in to vote.
A generic 1:(0..N) tree container with change events and automatic updating of a TreeView.

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 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

  • 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)

Share

About the Author

peterchen
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

 
QuestionGreat job. I took the code and exported to a C# 4.5 application. Pinmemberabel406g5-Aug-13 5:33 
QuestionWpf, Serialization PinmemberWarren C Harding20-May-13 18:14 
QuestionJava PinmemberRasha887617-Feb-13 23:00 
Questionproblem on insert without implementing list Pinmemberphoebuspf20-Jan-12 13:05 
QuestionBottom up approach PinmemberStephen Po2-Aug-11 10:01 
GeneralBugs in DTreeNode PinmemberMember 41572917-Apr-11 1:28 
GeneralAny update with objects serialization Pinmemberdmole1-Apr-09 17:58 
GeneralCollectionBase inside TreeNodeCollection PinmemberDawkins18-Dec-08 22:52 
GeneralRe: CollectionBase inside TreeNodeCollection Pinmemberpeterchen19-Dec-08 2:19 
QuestionSorting Pinmemberjimmygyuma14-Apr-08 6:05 
GeneralRe: Sorting Pinmemberpeterchen14-Apr-08 8:05 
GeneralRe: Sorting Pinmemberjimmygyuma14-Apr-08 14:10 
GeneralRe: Sorting Pinmemberpeterchen19-Dec-08 2:20 
QuestionPassword???? Pinmemberjimmygyuma4-Apr-08 13:00 
AnswerRe: Password???? Pinmemberpeterchen4-Apr-08 20:59 
GeneralRe: Password???? PinmemberXeorge23-Apr-13 9:22 
Questioncollection view of selected node controller PinmemberSazuke-kun9-Nov-07 12:18 
AnswerRe: collection view of selected node controller PinmemberSazuke-kun9-Nov-07 21:46 
GeneralRe: collection view of selected node controller PinmemberSazuke-kun9-Nov-07 21:58 
GeneralA Digital Space Universe PinmemberMonzerEmam18-Oct-07 10:39 
GeneralSerialization Pinmemberchaturvedi_amitabh18-Jul-07 0:56 
If I have hierarchy of classes and I create the tree with Base class then it does not serialize and give the exception that the Value property can't be reflected.
 
Even with binary serialization it does not work.
GeneralDisabling TreeView Painting PinmemberLisburn Lad8-Dec-06 2:50 
QuestionProblems with download link PinmemberAlex the Marrch Ca'at6-Nov-06 10:21 
AnswerRe: Problems with download link Pinmemberbernatsky.zoltan23-Nov-06 21:39 
GeneralDu bist so... PinmemberJoergen Sigvardsson13-Oct-06 9:10 

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

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

| Advertise | Privacy | Mobile
Web01 | 2.8.140905.1 | Last Updated 28 Jan 2006
Article Copyright 2006 by peterchen
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid