Tree<T>: Implementing a Non-Binary Tree in C#
Posted by Dan Vanderboom on March 15, 2008
[Updated 8/14/2014] The source code for this library can be found here at GitHub. Also check out my blog post announcing it.
[This is the first article in a series of intelligent data structures, which is continued here with KeyedList.]
I’ve always thought it was odd that the .NET Framework never shipped with a Tree or Tree class in its collection namespaces. Most of the other classic data structures are there: List, Dictionary, Stack, Queue, and so on. Where then is Tree? I have no idea, but finding myself in need of one, I decided to build one, and in doing so realized that it was a little trickier than I first imagined it would be. Certainly it isn’t difficult to get some kind of tree working, even without support for generics, but building one that is truly intuitive to use was a real challenge. In this article I will share what I came up with, and will illustrate the thought process behind each of the design decisions that I made as a study in object-oriented design and the use of some cool C# language features like generics constraints.
First, what is a tree data structure and what is it used for? A tree is, in layman’s terms, a collection of nodes (items) that are connected to each other in such a way that no cycles (circular relationships) are allowed. Examples abound in organization charts, family trees, biological taxonomies, and so forth. Trees are incredibly useful structures because they allow us to represent hierarchies and to compose complex structures out of basic parts and simple relationships. In the world of programming specifically, this provides a mechanism for extensibility across many domains, and a container to assist us in searching, sorting, compressing, and otherwise processing data in efficient and sophisticated ways. Trees are also a natural fit for use in the composite design pattern, where a group of objects can be treated (or processed) like a single object.
Just as it’s possible to implement recursive algorithms non-recursively, it’s also possible to create non-hierarchical data structures to store data that would more logically be stored in a tree. In these cases, your code is typically much more clear when organized in a tree, leading to greater maintainability and refactorability. Recursion itself, while not exceptionally common in every day programming tasks, plays a more important role in some interesting ways with trees and traversal patterns. Traversal is the term used to describe how nodes in a tree are visited. Later I’ll demonstrate some tree traversal techniques that you can use.
Binary vs. Non-Binary Trees
What are binary trees, and why the focus on non-binary trees? Binary trees are a special kind of tree in which each node can only have two children, often referred to as left and right child nodes. These special trees are very useful for sophisticated searching, sorting, and other algorithms. However, trees that allow any number of children seem to abound in more general, every-day programming scenarios, as you’ll see from examples below. In a follow-up article, I’ll demonstrate how you can create a BinaryTree class that inherits from Tree and applies the necessary restrictions and some useful abstractions. Below (figure 1) is a binary tree, which I present here to contrast with the non-binary trees that we’ll be covering in detail.
Figure 1. A generic binary tree.
For more information on implementing and using binary trees, see this article which is part of a larger series on data structures.
Examples of Non-Binary Trees
A simple example of a non-binary tree is the file system in any modern operating system. The diagram below (figure 2) illustrates a small part of the structure of the Windows file system. Folders can be nested inside other folders as deeply as needed, providing the ability to compose a complex organizational structure for storing files. The traversal path—from the root to some other node—can be represented by a canonical resource descriptor such as C:\Windows\system32.
Figure 2. The file system is a tree structure of folders containing other folders.
This hierarchical structure can be represented and visualized in different ways, though the underlying relationships are the same. The screenshot below (figure 3) is of Windows Explorer on my development computer. The control is the common TreeView, which supplies a way in this case for users to explore and interact with the tree data structure of the file system.
Figure 3. A tree view control in Windows Explorer provides access to a hierarchy of nested folders.
Another example is the organization of controls in a form (for Windows Forms) or in a window (for WPF). The next diagram (figure 4) depicts the relationship of controls containing child controls, which may in turn contain their own children, and so on.
Figure 4. A user interface is composed of a tree of controls that contain other controls.
This is also manifested through a user interface with the Document Outline window in Visual Studio, which is very useful for selecting deeply nested controls, or container controls that are otherwise difficult to select in the forms designer itself. This is shown in figure 5, where you can clearly see the different levels of all controls.
Figure 5. The document outline window in Visual Studio for a Windows Forms screen.
Defining the Basic Components
There is a lot of formal terminology in graph theory to contend with, but for our purposes, we only really need to be concerned with a few basic terms.
- Tree – This refers to a collection of nodes connected by parent-child relationships in a hierarchical structure.
- Parent – A node one level up from the current node.
- Child – A node one level down from the current node.
- Node – One item in a tree with an optional parent and zero or more children.
- Root Node – A special node with no parent. A tree can have only one root node.
- Subtree – A section of a larger tree including the non-root node of a larger tree, plus all of its children.
That’s not so bad, is it? In designing a reusable tree data structure, it’s important to establish a consistent and sensible pattern for semantics. In fact, coming up with good names for the components of our data structure may be the most difficult part. With poor identifiers, even simple structures can be confusing to those using it.
Begin with the End in Mind
I began with a quasi-test-driven development approach. I asked myself how I’d like the end result to look when consuming the new data structure. I knew from the start that a tree data structure that didn’t use generics wasn’t going to be very useful. Imagine this code:
Tree ObjectTree;
What is the type of each node in the tree? If I’m going to use this in different scenarios, the only answer is to make it an object, so that I could store whatever I liked in my tree, but this would require a lot of casting and a lack of type checking at compile type. So instead, using generics, I could define something like this:
Tree <string> StringTree;
This is much better, and leads to two more steps that we’ll need to take conceptually. The first one is that I will definitely want a tree of nodes for custom types in my software’s problem domain, perhaps Customer or MobileDevice objects. Like strings, these objects are (for our purposes here) simply dumb containers of data in the sense that they are unaware of the tree structure in which they reside. If we take this one level further, and consider custom types that are aware of their place within the tree (and can therefore particpate in much richer ways to compose hierarchical algorithms), we’ll need to consider how to make that awareness happen. I will explain this in more detail later in this article.
public class Tree : TreeNode
{
public Tree() { }
public Tree(T RootValue)
{
Value = RootValue;
}
}
This definition of Tree is really a matter of semantics and syntax preference. I’m creating an alias for the TreeNode type, claiming that a Tree is a node itself—the root node in a Tree, by convention. I call this a synonym type. Here’s a very simple example of its use:
Tree<string> root = new Tree<string>();
root.Value = “zero”;
int d0 = zero.Depth;
TreeNode<string> one = zero.Children.Add(“one”);
int d1 = one.Depth;
TreeNode<string> twoa = one.Children.Add(“two-a”);
TreeNode<string> twob = one.Children.Add(“two-b”);
TreeNode<string> twoc = one.Children.Add(“two-c”);
string twocstr = twoc.Value;
int
d2 = two.Depth;
You can tell a few things by looking at this code:
- The root node is defined as a Tree, but is manipulated like the other TreeNodes because it inherits from TreeNode.
- Each node’s value is stored in a property called Value, which has a type of T (using generics).
- A Depth property indicates how deeply in the tree the node is nested (the root has a depth of 0).
- The Add method in the Children TreeNode collection returns a TreeNode object, making it easier to create a new node and get a handle to it in the same statement.
Connecting Nodes to Their Parents & Children
The intelligence needed to make a Tree work resides in two classes: TreeNode and TreeNodeList. I could have used a standard collection type for TreeNodeList, but each TreeNode links to both Parent and Children nodes, which are two fundamentally different relationships; and I wanted parent and child nodes to connect and disconnect automatically behind-the-scenes—if you add a child to X, that child’s Parent property should automatically be set to X, and vice versa. That requires hooking into the Add method in a custom collection class to manage those relationships. TreeNodeList therefore looks like this:
public class TreeNodeList : List<TreeNode>
{
public TreeNode Parent;
public TreeNodeList(TreeNode Parent)
{
this.Parent = Parent;
}
public new TreeNode Add(TreeNode Node)
{
base.Add(Node);
Node.Parent = Parent;
return Node;
}
public TreeNode Add(T Value)
{
return Add(new TreeNode(Value));
}
public override string ToString()
{
return “Count=” + Count.ToString();
}
}
The ToString override is very important for making your debugging sessions more manageable. Without this kind of assistance, especially when troubleshooting recursive, hierarchical algorithms, you may go crazy digging through the debugger’s own tree view control to find what you’re looking for.
The Tree Node
The TreeNode itself gets a little tricky. If you update the Parent property because a node is going to be moved to another part of the tree, for example, you want to make sure that it gets removed from the Parent’s list of Children, and you also want to add it as a child to the new Parent. If the Parent was null, or is being set to null, then only one of those operations (remove or add) is necessary.
Here are the primary structural and payload-containing portions of this early version of the TreeNode class:
public class TreeNode : IDisposable
{
private TreeNode _Parent;
public TreeNode Parent
{
get { return _Parent; }
set
{
if (value == _Parent)
{
return;
}
if (_Parent != null)
{
_Parent.Children.Remove(this);
}
if (value != null && !value.Children.Contains(this))
{
value.Children.Add(this);
}
_Parent = value;
}
}
public TreeNode Root
{
get
{
//return (Parent == null) ? this : Parent.Root;
TreeNode node = this;
while (node.Parent != null)
{
node = node.Parent;
}
return node;
}
}
private TreeNodeList _Children;
public TreeNodeList Children
{
get { return _Children; }
private set { _Children = value; }
}
private T _Value;
public T Value
{
get { return _Value; }
set
{
_Value = value;
if (_Value != null && _Value is ITreeNodeAware)
{
(_Value as ITreeNodeAware).Node = this;
}
}
}
}
There are two ways we could find the Root node. The commented line shows a succinct way to walk the tree (recursively) toward successive parents until Parent is null. The actual implementation being used shows another way, using a simple while loop. I prefer this because in the event of debugging, it’s easy to step through a loop, and a little more difficult to jump through the same property on multiple, perhaps many, different instances of TreeNode. I follow the same pattern for the Depth property (below).
A tree structure isn’t very useful, however, unless it can carry some kind of payload. You want to build a tree of something, and it’s handy that we can use generics to tell the compiler that we want a Tree of strings (Tree), for example. That’s what the Value property is for, and why its type is the generic type parameter T.
To instantiate and initialize TreeNodes, you’ll need some constructors. Here are two of them I defined:
public TreeNode(T Value)
{
this.Value = Value;
Parent = null;
Children = new TreeNodeList(this);
}
public TreeNode(T Value, TreeNode Parent)
{
this.Value = Value;
this.Parent = Parent;
Children = new TreeNodeList(this);
}
The Tree Node Payload’s Awareness of its Place in the Tree
You probably noticed in the last section that the Value object is checked to see if it implements the ITreeNodeAware interface. This is an optional extensibility mechanism for custom classes that need to be aware of the tree so that payload objects can read or manipulate it in some way. In developing a data binding framework for Windows Forms that allows you to bind control properties to paths (“PurchaseOrder.Customer.Name”) instead of specific objects (PurchaseOrder.Customer, “Name”), as ASP.NET and WPF data binding works, I needed this ability and came to the conclusion that this would be a useful feature in general. Later in the article, I will magically transform the TreeNode and TreeNodeList classes in such a way that both this interface and the Value property become unnecessary.
Until then, here’s how the interface looks with an example class that uses it.
public interface ITreeNodeAware
{
TreeNode Node { get; set; }
}
public class Task : ITreeNodeAware<Task>
{
public bool Complete = false;
private TreeNode<Task> _Node;
public TreeNode<Task> Node
{
get { return _Node; }
set
{
_Node = value;
// do something when the Node changes
// if non-null, maybe we can do some setup
}
}
// recursive
public void MarkComplete()
{
// mark all children, and their children, etc., complete
foreach (TreeNode<Task> ChildTreeNode in Node.Children)
{
ChildTreeNode.Value.MarkComplete();
}
// now that all decendents are complete, mark this task complete
Complete = true;
}
}
Using the ITreeNodeAware interface means we have another step to make in our implementation, and adds some complexity to its use in terms of discoverability and implementation of the interface by consumers of the Tree structure in creating custom payload classes. By doing this, however, our Task objects will get injected with a Node property value when added to a Tree of Tasks. So the payload object will point to the node via the Node property, and the Node will point to payload object via its Value property. This is a lot of logic for such a simple relationship, but as we’ll see later, there is an elegant way around all of this.
Including Structure Helper Members
There are some common measurements of aspects of the tree’s nodes, as well as operations that you will typically want to perform on a tree or subtree, such as initialization, systematic traversal, pruning and grafting, disposal, and determination of depth, some of which I will discuss here.
Here is a property to determine your current nesting depth, which can be useful while debugging:
public int Depth
{
get
{
//return (Parent == null ? -1 : Parent.Depth) + 1;
int depth = 0;
TreeNode node = this;
while (node.Parent != null)
{
node = node.Parent;
depth++;
}
return depth;
}
}
Because the payload objects (referenced by the Value property) may require disposing, the tree nodes (and therefore the tree as a whole) is IDisposable. Different trees of objects may require being disposed in different orders, so I’ve created a TreeTraversalType, a DisposeTraversal property of this type to specify the order, and have implemented the Dispose method that takes this into consideration.
public enum TreeTraversalType
{
TopDown,
BottomUp
}
private TreeTraversalType _DisposeTraversal = TreeTraversalType.BottomUp;
public TreeTraversalType DisposeTraversal
{
get { return _DisposeTraversal; }
set { _DisposeTraversal = value; }
}
Here is one way to implement IDisposable that includes a property indicating whether a node has been disposed, invokes a Disposing event, and traverses the tree according to the value of DisposeTraversal.
private bool _IsDisposed;
public bool IsDisposed
{
get { return _IsDisposed; }
}
public void Dispose()
{
CheckDisposed();
OnDisposing();
// clean up contained objects (in Value property)
if (Value is IDisposable)
{
if (DisposeTraversal == TreeTraversalType.BottomUp)
{
foreach (TreeNode node in Children)
{
node.Dispose();
}
}
(Value as IDisposable).Dispose();
if (DisposeTraversal == TreeTraversalType.TopDown)
{
foreach (TreeNode node in Children)
{
node.Dispose();
}
}
}
_IsDisposed = true;
}
public event EventHandler Disposing;
protected void OnDisposing()
{
if (Disposing != null)
{
Disposing(this, EventArgs.Empty);
}
}
public void CheckDisposed()
{
if (IsDisposed)
{
throw new ObjectDisposedException(GetType().Name);
}
}
I overrode ToString in the TreeNodeList class above to display the count of children. I do the same thing for TreeNode, which as I mentioned earlier aids a great deal in debugging.
public override string ToString()
{
string Description = string.Empty;
if (Value != null)
{
Description = “[“ + Value.ToString() + “] “;
}
return Description + “Depth=” + Depth.ToString() + “, Children=”
+ Children.Count.ToString();
}
Notice how the Value property, if it’s set, gets included in the ToString value. If you’re looking at a TreeNode in the watch window, you’ll appreciate that your Value object can be represented without having to drill into anything. You can see at a glance what the payload is, how deep it is in the tree, and how many child nodes it has.
The Role of Generics in Representing Payloads
I have already supplied enough logic and sample code for a fully functioning tree data structure for use in the .NET Framework, which incidentally was developed in a Compact Framework project and will therefore work in any .NET environment. That being said, there are some syntactical inconveniences with the approach mentioned so far. Consider the Tree example above in a scenario where we want to access a parent node’s payload from a current node:
TreeNode<Task> CurrentTaskNode = /* get current task node */;
bool IsComplete = CurrentTaskNode.Parent.Value.Complete;
Note that Parent doesn’t return our object of type T, but instead gives us a TreeNode; and our CurrentTaskNode object is also a node object and not a task object. When we think about trees in theory, especially visually in the form of diagrams, the parent of a node is another node, meaning that parent and child are the same type of thing. In our simple implementation so far, however, the parent of a task is not another task, but rather a task-tree-node, which is not the same thing.
If we start from a Task object instead of a TreeNode, the syntax is worse:
Task CurrentTask = /* get current task */;
bool IsComplete = CurrentTask.Node.Parent.Value.Complete;
Notice how each time we access Node or Value, we’re weaving in and out between types. So we must manipulate this data structure and its payload all the while with explicit deference to the type disparity and dualism, and a careful naming of variables is important to avoid confusion between types (CurrentTaskNode vs. CurrentTask). When I first had this realization, it occurred to me why a Tree data type may have been missing from the original .NET Framework. I doubt very much that all the brilliant developers working on the base class libraries didn’t think to include such a useful structure, but perhaps the obvious implementations that came to mind seemed confusing and problematic for real-world use.
Fortunately, we now have capabilities in the CLR as of 2.0—and corresponding language features—that enable us to solve this problem elegantly. I’m referring to generics, and more specifically, to generic constraints.
The simplifying idea is that by creating a payload class that inherits from TreeNode, and applying a simple generic constraint to get around some casting problems that would normally prevent us from compiling, we can make our final syntax look like this:
Task MakeDinner = new Task();
Task PrepareIngredients = MakeDinner.Children.Add(new Task());
Task CookMeal = MakeDinner.Children.Add(new Task());
Task PreheatOven = CookMeal.Children.Add(new Task());
Task BakeAt350 = CookMeal.Children.Add(new Task());
Task Cleanup = MakeDinner.Children.Add(new Task());
bool IsAllDone = BakeAt350.Parent.Parent.Complete;
Notice that in the final statement, we don’t have to navigate from BakeAt350 to some different type object through a Node property, and that we can go directly from Parent to the Complete property. This is because our Task class is defined like this now:
public class Task : TreeNode<Task>
{
public bool Complete = false;
// recursive
public void MarkComplete()
{
// mark all children, and their children, etc., complete
foreach (Task Child in Children)
{
Child.MarkComplete();
}
// now that all decendents are complete, mark this task complete
Complete = true;
}
}
It’s been compressed! The Node property is no longer necessary (since the task is-a node, instead of being contained-by a node), and therefore the ITreeNodeAware interface can also be dispensed with. The MarkComplete method is different, too: we simply write Child.MarkComplete instead of Child.Value.MarkComplete, and we can loop through a collection of Task objects with the Children property directly, instead of going through a set of TreeNode objects in some external Node object.
In our consuming code above, we didn’t even have to mention the Tree or TreeNode type, but if we did declare a variable that way (for the sake of clarity), it would simply be a synonym of Task. It would look like this:
Tree<Task> MakeDinner = new Tree<Task>();
We could use TreeNode as well; it makes no difference. Task = Tree = TreeNode.
To make all of this magic happen, we need to define TreeNode with a generics constraint.
public class TreeNode : IDisposable where T : TreeNode
This tells the compiler that T must inherit from TreeNode, and therefore variables of type T are safe to manipulate as tree nodes. TreeNodeList requires the same constraint:
public class TreeNodeList : List<TreeNode> where T : TreeNode
This breaks us out of a restrictive pattern where normally a custom collection class is unable to richly manipulate the objects within it (unless the collection is instantiated directly from consumer code, which is not the case in this pattern). But because the collection class knows that all of its items will derive from TreeNode, it can manipulate them as tree nodes with no problem.
There is a price to pay for this convenience, however, which is that the tree is restricted to types that inherit from TreeNode. This means that a Tree is no longer possible. You will have to decide how you will likely use trees in your development to determine whether to design something like this into it. If you want this cleaner syntax but still need trees of primitive and other non-TreeNode-derived types, you can create a distinct SimpleTree for this purpose. It may even be possible for Tree to inherit from SimpleTree, hiding the Value property (with a private shadow method shown below) and adding the generic constraint.
Cleaning Up
Now that the basic functionality is in place, I decided to split the Tree class into two. SimpleTree represents a simple tree data structure that can contain as its Value any object; and ComplexTree, which uses the generic constraint described above and supports more complex hierarchical algorithms and tree-aware nodes. I really like the simplicity of the Tree name, but along with the need to support both simple and complex scenarios, there are two more reasons for this name-change decision.
First, in the System.Windows.Forms namespace, there is already a TreeNode class that corresponds to the TreeView control. If I had designed that control, I probably would have named it VisualTree and its node VisualTreeNode to distinguish it from a logical node, but as it is, dealing with two different TreeNode classes, even in different namespaces, could be confusing and messy. Second, the new Task Parallel Library (TPL) contains an implementation of a binary tree called Tree, which is a rather short-sighted name considering that all useful trees are not binary trees, as I’ve demonstrated in this article; BinaryTree would have been a much more appropriate name. Hopefully by the time TPL is released, this identifier will be updated to reflect this.
Conclusion
Elegant implementations of tree data structures in .NET Framework, though problematic in the past, are finally possible with the introduction of generics and generic constraints. With some careful syntax planning for consuming code, as well as experimentation with different language constructs, I hope I have shed some light on how these kinds of problems can be approached and solved.
In future articles, I will be exploring some techniques and specific uses for hierarchical algorithms. Some of the very problems that appear too difficult to solve without a background in mathmatics can be much more easily understood and mastered by using tree data structures and associated visualization techniques.
[This is the first article in a series of intelligent data structures, which is continued here with KeyedList.]
Critical Development 
Tarek said
Hi Dan,
Once again you have create a great post. Thank you very much.
Will you be posting the completed Tree class?
Kind Regards,
Tarek
Dan Vanderboom said
I’ll be posting a link to completed SimpleTree and Tree data structures in a Visual Studio project, along with some additional enhancements that I will probably explain in another article. I’ve been updating this article, and will continue to do so over the next few days, as I find and correct text, formatting, and code errors.
My guess is that I’ll make that available by the end of next weekend (3/23). I’ll include some unit test code as well to provide examples of its use and verify its correctness.
Tarek said
Hi Dan,
Sounds great. By the way, your blogs always look really magazine articles. Great work.
Kind Regards,
Tarek
Koki said
Hi Dan,
A fantastic article.
I need a structure to pass from DataAccessLayer (data is stored in SQL Server) to BussinessLayer, and finally to UI Components (Windows or Web Clients), so xml is only valid for TreeView of WebControls with XmlDataSource, to databind directly.
Besides, each one of the nodes has to store some fields so it can display information correctly. (image,expand,color,etc)
I am waiting for your code to study it.
I think that with your solution , my problems are solved.
Dan Vanderboom said
Koki, I couldn’t agree with you more. I think many things are enabled if we have access to a tree data structure that can make all of the transformation steps from the persistence layer, through the network (to a mobile device potentially), and into a controller or view object, bound to user interface controls in the latter case. A newer post I wrote on a Visual Studio Macro (to seek the current Solution Explorer item) uses a recursive algorithm, and I have several projects in the pipeline that also need to create and manipulate trees.
What I also need is a tree that can dynamically load its nodes, so you don’t have to load the whole structure at once, and it should be able to load them from across the network if necessary.
In just a few more days, I’ll have the rest of the unit tests written, and a couple of examples to demonstrate its use. As I refine it and add data binding to UI controls, dynamic loading, etc., I wlll either update this article or write more in a series on its development.
Stay tuned in the next few days for updates.
koki said
Very nice code !!
One cuestion, is serializable ComplexTree class ??
I can return a ComplexTree from server calling a WCF method, and use for example in a win forms client ??
Thank very much !!!
Dan Vanderboom said
Hi Koki,
First, the SimpleTree class can be made serializable with a small modification. By adding the [XmlIgnore] attribute to the Parent property of the SimpleTree class, you can see that it can be serialized. Using the sample data in the code I provided, I was able to do this:
StreamWriter sw = new StreamWriter(@”c:\SimpleTree.dat”);
XmlSerializer ser = new XmlSerializer(typeof(SimpleTree<string>),
new Type[] { typeof(SimpleTreeNode<string>) });
ser.Serialize(sw, MakeDinnerTree);
sw.Close();
I wasn’t sure if I’d be able to deserialize it with the Parent property unrepresented in the serialized stream, but by happy coincidence, I wrote this code and found that it did work.
StreamReader sr = new StreamReader(@”c:\SimpleTree.dat”);
XmlSerializer deser = new XmlSerializer(typeof(SimpleTree<string>),
new Type[] { typeof(SimpleTreeNode<string>) });
SimpleTree<string> deMakeDinnerTree = (SimpleTree<string>)deser.Deserialize(sr);
sr.Close();
And then I realized it was due to the way I implemented the Children collection. When you add a child, the parent gets hooked up automatically.
So your question is can you serialize ComplexTree objects. The answer is yes, if you make this modification, and also if the type described by type parameter T is also serializable. A ComplexTree<Task> might be, but a ComplexTree<Assembly> would not be.
I also added [XmlIgnore] to the DisposeTraversalType and DisposeTraversalDirection properties, because otherwise they would be serialized unnecessarily to every node, but you may want to convey this information once at the top of the serialized tree. For this reason, as well as for supporting binary serialization, I’ll be talking about adding custom serialization logic in a future article which will create a clean and simple way to serialize and clone tree data structures.
Steve Holle said
What change do you refer to here?
Steve Holle said
I tried adding this to the end of frmComplexTree_Load routine
StreamWriter sw = new StreamWriter(@”c:\\ComplexTree.dat”);
XmlSerializer ser = new XmlSerializer(typeof(ComplexTree),
new Type[] { typeof(ComplexTreeNode) });
ser.Serialize(sw, MakeDinner);
sw.Close();
This to class
public class ComplexTreeNode : IDisposable where T : ComplexTreeNode
{
private T _Parent;
[XmlIgnore()]
public T Parent
{
And get “There was an error generating the XML document”
The same procedure in the SimpleTree example works fine.
Any ideas?
Stromokocuur said
Please, send me the whole code of SimpleTree class to my mail address (stromokocuur@azet.sk). I have created a very similar Tree but I have problems with the serialization..Thanks
Dan Vanderboom said
The download link in the article is now working.
Hank said
Thank a lot for this great post! but where is the download link?
Hank said
Never mind, I found the link…
Adam said
Hi! How can I implement searching of minimum tree value ?
Dan Vanderboom said
Hi Adam,
Traversing through the tree to search for a specific value, such as a minimum value, is easy. In a follow-up article I’m working on, I’m adding custom iterators to the SimpleTree and ComplexTree types. Here’s an example of one of those iterators:
public IEnumerable<SimpleTreeNode<T>> DepthFirstEnumerator
{
get
{
return GetDepthFirstIterator(this);
}
}
private IEnumerable<SimpleTreeNode<T>> GetDepthFirstIterator(SimpleTreeNode<T> Root)
{
yield return Root;
foreach (SimpleTreeNode<T> child in Root.Children)
{
foreach (SimpleTreeNode<T> x in GetDepthFirstIterator(child))
{
yield return x;
}
}
}
This iterator can be looped over with foreach just like a normal flat collection. You can visit each node in turn, checking to see if it’s less than your minimum value, and if it is, update your minimum value, like this:
static int GetMinValue(SimpleTreeNode<int> Root)
{
int MinValue = Root.Value;
foreach (SimpleTreeNode<int> Node in Root.DepthFirstEnumerator)
{
if (Node.Value < Root.Value)
MinValue = Node.Value;
}
return MinValue;
}
And here’s the test code I used to build a tree of integers and call the GetMinValue method:
SimpleTreeNode<int> IntRoot = new SimpleTreeNode<int>(10);
IntRoot.Children.Add(3).Children.Add(15);
IntRoot.Children.Add(9);
IntRoot.Children.Add(1).Children.Add(0);
int min = GetMinValue(IntRoot);
Adam said
Thank you very much!
Josh said
First of all, good job!
I am wondering how I could implement something like an organizational hierarchy with this?
For example, let’s say I want to build a tree showing the organizational hierarchy of employees, using ManagerID and EmployeeID, from the AdventureWorks database. I am playing with some LINQ and I’m able to get the employees and determine a root node (the CEO), but now I want to build the remainder of the tree.
Once I have a tree built I want to traverse the tree either in its entirety or just from a specific point on the tree; however, I think I can extrapolate some of this from your response to Adam’s question.
Again, great job and I can’t wait to see your response and read your follow up article(s).
Richard said
Is it okay to use this in commercial projects? (what licence can I consider it to be?) Atm im doing some research into windows mobile and would like to add this code to the “interesting for later on list” so It would be nice to know if it can actually be used.
Dan Vanderboom said
By all means, folks, use this in your programs if you wish. Commercial applications or otherwise. I mean, don’t just sell what I wrote and claim it was your work, but if it’s included in part of a larger project, there aren’t any limitations. I haven’t yet decided on a specific license, and I realize I need to make a post about this very topic, but whatever it ends up being will be no more restrictive than what I’ve written here. Use it. That’s the point of me writing this! If you want to include a comment that provides a link to the original work, I would surely appreciate it, and it may be useful for future developers, as I write more on the topic and share future versions.
And I promise I will be writing a follow-up article soon, with updated source code and some nice new functionality.
Richard said
Late last night I hacked together a feature that flattens the tree to a list, its ugly so maybe you have a better way of doing it, basically I do alot of recursive get{} where lists of childs gets returned, iterated, added to current list and destroyed. It works but it just doesnt seem right with all that construction/deconstruction. I want to be able to flatten the tree and make sure childs are always “beneath” their parents.
Its not generalized yet but if you want I can post the code.
Tbh after some more thinking today I dont think a tree is the correct datastructure for me since I want to be able to represent a flow chart.
Dan Vanderboom said
Hi Richard. It sounds like you’re cloning each node, and creating a list of nodes that is therefore separate from the original tree. When you say you want to make sure children are always beneath their parents, do you mean that you want to sort the list in such a way that child nodes always come AFTER their parents?
As far as representing a flowchart goes, no, a tree data structure isn’t your best option because flowcharts aren’t strictly hierarchical. They can be, but often they have cycles. Your best bet is to go with a data structure similar to a tree, but more generalized. I’m speaking of a graph. Many of the patterns I’ve established for my Tree data structure also apply to graphs, though some of the terminology is different: instead of “children” per se, you have a collection of “other nodes”. And of course traversal of graphs is more complicated.
I’ve been meaning to write an article to add a Graph collection class, and this is a good reminder to take a look at those ideas again.
As far as flattening a tree (or graph), I came up with a neat little pattern I’m calling “predicate function iterator” that will traverse through a data structure in a configurable way, select only nodes that match an optional predicate, and then flatten it into a list that can be queried with LINQ.
Richard said
Yeah after in the list, but for now i´ve decided on a much simpler approach since the actual charts arent that big im just going to have them represented in a list.
As you may have guessed im not a C# developer but merely someone who´s trying to figure out if its the right/possible way to go.
Great site btw, will defineatly be recommending it to whomever gets to develop the application 🙂
Ali said
Hi,
Thanks a lot for this wonderful code. I’ve been looking for it for a long time!
I have a question which I could not find a way to do it: How can I let the children have more than one parent? I tried to modify the code but I’ve failed up to now. Can you help me please?
Dan Vanderboom said
Hi Ali,
What is your application? The only thing I can think of off-hand where you’d need multiple parents is representing, well, a family tree. 🙂 But am curious what you’re aiming for.
With a collection of parents, it actually becomes more of a graph than a tree. (But it sounds rather awkward to talk of one’s “family graph”.)
The pattern changes quite a bit by having multiple parents. Having assumed a single parent, when the parent of a node changes, the child is removed from the parent’s Children collection automatically. But with the possibility of having multiple parents, I would suggest methods to Attach and Detach a parent or child. When you attach a child node to a parent node, that parent’s children collection needs to be updated (same as before); and when you detach a child node, the parent pointer gets removed from the child node, and the child node gets removed from the list of Children in the parent node. And that’s all there is to it, really, as far as structure goes.
Do you need to limit the number of parents? If so, you’ll need to code for those constraints in your Attach and Detach methods.
When it comes to traversal, however, you have another issue. Trees are directed graphs, and they flow in one direction as they expand into children and grandchildren, etc. But in your scenario, you’d need an iterator that knows how to traverse to children, and then also back up to “other parents”; and because you can easily have cycles in the data structure, you’ll need some kind of bookkeeping mechanism (such as a simple List) to keep track of which one’s you’ve already visited (if (!VisitedNodes.Contains(node)) Visit(node);), so you don’t keep visiting the same nodes over and over again.
Ali said
Hi Dan,
Thank you very much for your comments.
My application is Association Rule Mining (ARM). In fact to reduce the number of extracted redundant rules I use algorithms which find the closed itemsets and then I extract association rules. To implement these algorithms I need nodes which can have several parents. 🙂
I’m a mechanical engineer but I hope that I will be able to implement your comments.:)
farrukh said
Nice and usefull article
How i get child from this tree
Dan Vanderboom said
Hi Farrukh,
It depends which child you want to get. You can create a variable to reference any node in the tree. You can loop through any node’s Children, and access each of those SimpleTreeNode or ComplexTreeNode objects. What is the problem you’re trying to solve with a tree?
Eric Morrison said
Dan,
Great job!
I’ve used and somewhat extended your Tree collection in a project that I’m currently working on. It’s been a great help.
I’ve added methods which parallel some of the methods exposed by XElement. I’ve also written a test project for SimpleTreeNode which you may or may not be interested in.
I have a couple of questions though and would like to discuss them with you.
Thanks in advance,
-Eric
fornetti said
I do not believe this
ralfie said
Hi,
I got a StackOverflowException when I tried to delete a Node (I think it’s a bug).
So I changed the code:
in “SimpleTreeNodeList.cs”:
public new void Remove(SimpleTreeNode Node)
{
if (Node != null)
{
Node.Parent = null;
}
base.Remove(Node);
}
to ->
public new void Remove(SimpleTreeNode Node)
{
base.Remove(Node);
if (Node != null)
{
Node.Parent = null;
}
}
and in “SimpleTreeNode.cs” in Property “public SimpleTreeNode Parent”:
if (_Parent != null)
{
_Parent.Children.Remove(this);
}
to ->
if (_Parent != null)
{
if (_Parent.Children.Contains (this))
_Parent.Children.Remove(this);
}
Now I can delete Nodes this way:
node.Value.Parent = Nothing
Or is there another way how to delete Nodes? Can you confirm my bug ?
Denis Vuyka said
Awesome article indeed! Do you have any updated version having full traversal directions support for searching the tree? Thanks.
Dan Vanderboom said
I am indeed working on a second version of the library with more traversal options, a real iterator, and more. I’ve been caught with a lot going on, so it may be a week or two out yet. Finishing the building of my new development machine, writing about it, am in the middle of about 12 books right now, and then there’s a social life somehow. 🙂
Thanks for the kind words… it encourages me to be distracted from other things to work on it more.
Dan Vanderboom said
Ralfie, it looks like you are correct. Nice catch! I’ll incorporate the fix into my new article, and will probably also repost this one for those who don’t find the new article.
leblanc meneses said
In wpf there is a logical tree and visual tree.
I understand its using a tree as its main data structure. The children must have a pointer to their parent also (to support event routing bubble up/down).
I’m trying to figure out how they managed to create the logical tree and visual tree.
Which would you think is the best approach???:
Solving it using an iterator. Finding the logical and visual by searching for nodes using a property value in the node. (node.TreeType & TreeType.LogicalNode) == 1 // is a logical node
possible problems:
visitors become bloated to transverse all nodes in logical and visual. if the tree was separated a visitor would be specific to the tree its transversing. LogicalTree, VisualTree, BothTree
api becomes ugly to set the flag; nodeboth.TreeType = (TreeType.LogicalNode << 1) | TreeType.VisualNode; // not nice for a parser creating the tree for you
cloning the tree is expensive – cloning would clone your object’s data not just pointers.
what i like is your friendly api .. as you construct the objects you are also creating the tree.
Solving it using nodes that contain a pointer vs inheriting as in your example(Task : ComplexTreeNode):
TreeNode
TreeNode parent
List<TreeNode> children
T reference
Now we can have different physical trees referencing the same data.
LogicalTree, VisualTree, BothTree
visitors are slimmer, deep copies won’t be expensive assuming reference doesn’t get copied, so you can create visitors that optimize the tree — possible AST optimization. the only problem with this is the programmers api. its simpler for a parser but not so handy for a human. you create the objects seperate then create the tree adding the object pointer (c#3.5 will make the syntax liveable).
I’ll like to see your take on implementing logical tree and visual tree as in wpf.
some other topics i’ll like your opinions on is:
i’m trying to figure out how an electronic circuit simulation tool is created. From a graph how can i simulate what current and voltage are on each line segment?
what are some examples of weighted graphs, optimizing using graphs (http://en.wikipedia.org/wiki/Karnaugh_map).
leblanc meneses said
My implementation using a node class.
TreeNode root = new TreeNode(new ConfigurationFile())
{
Children = new List<TreeNode>()
{
new TreeNode(new Communication())
{
Children = new List<TreeNode>()
{
new TreeNode(new Serial()),
new TreeNode(new Ethernet())
}
}
}
};
so my tree is doubly linked so i can support bubble up and bubble down.
public List<TreeNode> Children
{
get { return this.children; }
set
{
foreach (TreeNode child in this.children)
// old children become orphaned.
{
child.Parent = null;
}
foreach (TreeNode child in value)
// new children are adopted and give this as there parent node.
{
child.Parent = this;
}
this.children = value; }
}
willlem said
interface ITreeNode: IDisposable
{
ITreeNode Parent {get; set};
ITreeNode Root {get;}
IList Children {get;}
}
class SimpleTreeNode: ITreeNode
{
private T value;
T Value
{
get {return value;}
}
}
class SimpleTree : SimpleTreeNode
{
}
class ComplexTreeNode: ITreeNode
{
}
class ComplexTree: ITreeNode
{
}
Ramanujam said
Awesome article! Do you have any updated version having full traversal directions support for searching the tree. Is there any we can have grouping funtionality implemented in it. Thanks
Dan Vanderboom said
Hey Ramunujam,
I suppose I can dig up my finished traversal code for you. 🙂 As for grouping, what is your scenario, and how would you imagine grouping/collapsing branches? What would be the target shape of your object graph after grouping?
Mason said
This is a great article, sir.
Unfortunately, I loaded up your code and ran into the design feature that maintains that each node must be of the same type on your tree. I was under the mistaken assumption that I could create and mix/match nodes of any type that I derived from ComplexTreeNode.
That was surprising, and unfortunate.
Maybe there’s a simple fix for my problem, but I’m pretty new to C#, so I’m sure the fix won’t be as simple for me.
Again, thanks.
Dan Vanderboom said
Hi Mason,
You’re correct in observing that tree nodes, because they’re defined as generic types, must have a single generic type specified which applies automatically to all nodes. If you need to support different node types, one thing you can do is to derive each of the nodes from the same base class or interface, and then define your tree as ComplexTree or ComplexTree. You can then test for actual type with the “is” operator:
if (node is Son) {…} else if (node is Daughter) {…}
Ramanujam said
Hi Dan,
I was working on Generic Tree with grouping functionality in place. Say, if my nodes has Name, Department etc, then i can group the nodes based on the Department
Johnson Software
David Mangement
Jermey Software
Software
Johnson Software
Jermey Software
Management
David Management
Thanks
Ramanujam
John said
Hi Dan,
I downloaded and am trying to use this in my project, but have run into an issue which looks suspiciously like a bug. But I’m probably not using it correctly or something.
Example: I have a new tree, and I add 2 items to the root. I then take item A and set the parent to be item B. What I get is a stack overflow, which I traced out as follows:
The parent property first does this:
if (_Parent != null)
{
_Parent.Children.Remove(this);
}
which is this:
public new void Remove(SimpleTreeNode Node)
{
if (Node != null)
{
Node.Parent = null; <———– Setting the parent to null causes a fatal loop and eventual stack overflow
}
base.Remove(Node);
}
What I did was comment out the Node.Parent = null line, reasoning that the node is going to be removed, ergo the parent is irrelevant at that point. It seemed to fix my problem, but I’m worried I might be missing the big picture.
What do you think?
-John
Dan Vanderboom said
Hi John,
You are correct. This is a bug. The Remove shadow method of the SimpleTreeList and ComplexTreeList classes should be removed altogether, since this does create a StackOverflowException as you indicated. The last line of the Parent property updates _Parent to the new value. Thanks for pointing this out!
Dan
VitroBlue said
Sorry, i didn’t got this too well
how is the fix to this again?
public new void Remove(SimpleTreeNode Node)
{
base.Remove(Node);
}
just like this and that’s it?
oleop said
Great article.
I wonder what kind of adjustments should be done for this code to handle diferent types of objects in the same tree.
So, when one declares Task : ComplexTreeNode he should specify type in (it is Task in the exmaple).
But lets say nodes have different types? Should one define something like Task and then derive different subclasses or there is a more elegant solution?
Julien Couvreur said
Great article.
I think the “Begin with the End in Mind” approach is really important and I am glad to see such design articles and discussions explaining how to think about a usable interface.
Also, this is a good occasion to make use of the latest and greatest .Net improvements.
Josh Gough said
Hello, what a great article!
I see you mentioned this:
“This is an optional extensibility mechanism for custom classes that need to be aware of the tree so that payload objects can read or manipulate it in some way. In developing a data binding framework for Windows Forms that allows you to bind control properties to paths (“PurchaseOrder.Customer.Name”) instead of specific objects (PurchaseOrder.Customer, “Name”), as ASP.NET and WPF data binding works, I needed this ability and came to the conclusion that this would be a useful feature in general.”
I am wondering if this class could be useful to me in a project I’m working on.
I’ve also been reading about Modified Preorder Tree Traversal from this article:
http://www.sitepoint.com/print/hierarchical-data-database/
And this:
http://www.codeproject.com/KB/tree/Tree_Traversal.aspx?display=PrintAll
Those give me some ideas.
Your mention of forms intrigues me because it’s where I’m headed.
We need to be able to disable/hide different UI elements within an application. Imagine a form or page named PurchaseOrder, with a table named Customer, and a field named Name. Well, for each of these we need to specify basic CRUD operations.
A security role can have Read access to the page and Customer table/control, but we might want to deny Update rights to the Name field, for example.
My thinking was to use URL style syntax (similar to dot notation but more consistent with URIs and REST):
/PurchaseOrder/Customer/Name
Then apply the CRUD flags to this object path.
The thinking is that it would work similar to ASP.NET’s security in that if a given role has a top-level permission of CRUD = TTTT for /PurchaseOrder, then by default all fields and controls are accessible for the user with that role. However, if we overlay /Purchase/Customer/Name TTFF on top of this, then the Name field would be grayed out. And, during update, we will not populate the Name field on the entity object to be persisted to the DB.
The thinking on this is pretty clear, but I’m just wondering have you used your Tree in cases like this and what kind of utility does it bring to those situations.
If I didn’t use a tree, I’d likely have to hard-code the path inside of the table definition, but then I’d still have to split on “/” and look upward for matching parent rules.
Any ideas welcome.
Thank you!
Josh
Dan Vanderboom said
I think what I wrote is different from what you’re looking at. My solution isn’t about mapping from a database to a form in memory. Rather, it binds the data between model data with a reference stored in a Controller (or Presenter) and a View object (a Windows Form). So if you have a controller like conSellGoods, you might have a SalesOrder variable within that controller, and a view called vwSellGoods with some TextBox and ListBox controls and such on the form. What I wanted to make sure of was that the business logic of validating the model data happened in the controllers, and then I could build multiple views to connect to that. I wanted to bind the Text property of vwSellGoods.txtLastName to conSellGoods.SalesOrder.Header.LastName. I used the Tag property to set the property path “SalesOrder.Header.LastName”, and then parsed that to build a single tree to hold all of those paths. The nodes of that tree “watch” the values of their respective path parts, and if any watched value changes, it invalidates everything “deeper” in the tree, and that subtree is rebuilt.
Some of what you’re talking about, I believe is available to some extent in ADO.NET Data Services, by writing methods in the data service class. You can write predicates and determine, based on whatever criteria (credentials in the session, etc.) which types to provide access to, though I’m not sure if you can filter at the column level or return metadata about allowed actions…
Jane said
Great article. It helped when I did my project.
Now I have a problem with delete all nodes from the tree. How can I do it?
Thank you.
Romeo said
Hi, A great article indeed.
But I need a little help in traversing the tree in non-recursive fashion, I mean iterative traversal. Could you please post the iterative version for traversing?
Romeo said
Hi
Okay let it be. I figured out where I made the mistake. Sorry for bothering.
dmole said
Hi,
Great article, I’m using it in our project, however I have difficulty implementing binary serialization. Do you have a version of the source code which contains how to do binary serialization.
Thank you so much!
Dan Vanderboom said
@dmole: I wrote this to be compatible with Compact Framework, which doesn’t support binary serialization, and I haven’t attempted to serialize trees, although the binary serializer is pretty smart in dealing with object graphs. What specific problems are you having? Perhaps I can help.
Alfredo said
Hi,
I’m testing this interesting container trying to serialize/deserialize the “Task” class objects contained in the MakeDinner example, using the ComplexTree version. I’ve followed the suggestions reported above about the serialization (using XmlIgnore attribute), and also I’ve added a default constructor for the Task class: in this way the serialization seems works well. The problem arise when I try to deserialize from: the tree is constructed well except the parent of each node is set to null. Any suggestion?
Thank you.
Ali said
I wonder if there is any updates to fix this issue as I am facing same issue of Parent being null after deserialization.
Jon Turner said
Thank you so much for this contribution. The code walk thru and explanation of design considerations helped immensely. I noticed in one of your response, you stated you were working on an updated version with itteration/enumeration. Were you able to get that code posted. I sure would like to get on the list when it is available. Thanks again.
JP said
calling remove or setting the Parent cause a stack overflow. I saw some comments above about this issue but I wasn’t sure if the solution was correct. I was wondering if the source was updated.
coffka said
Hi Dan,
This is exactly what I was looking for – Thanks!
One quick question. I’ve read in the comments how to serialize/deserialize the SimpleTreeNode and it works great with my custom type, SimpleTreeNode. I’m trying to have an instance of serialize into my project’s Application Settings. Since I have a TypeConverter for my MyCustomType, I’ve been successful in serializing a generic list of my type (List) to the Application Settings but not so with the SimpleTreeNode i.e I cannot find System.Collections.Generic.SimpleTreeNode in the of settings types. Hope that makes sense.
Cheers!
coffka said
Wow. I made no sense here. Please ignore!
John said
This is a great article. I am trying to adopt the simpletree implementation here for my project. In my project, I have make the tree node listen to certain events, if the event happens, work load of a particular node will changes accordingly. In order to do that, I need to define a method to quickly find the node whose work load is changing, and then update the node (its work load). Do you have any advice, in terms of how this could be implemented efficiently? I changed the simpletreenodelist to inherit from Collection, to expose clearitem() virtual method.
Suresh said
Hai dan,
Can you please send me a pseudo code for finding a leaf nodes of a non binary tree?
Thanks in advance.
Regards,
Suresh Raju
Kumaraswamy said
Hi Dan,
is it possible to create a simple tree (taken from your eg) dynamically? if so then could you please tell me how?
Sham said
Hi Dan,
Great article and description on the code.
I was wondering whether you had posted the updated version of this as mentioned above with iteration & enumeration etc. I would like to look through that version also.
Please add me to your list when its available.
Thank you
Sham said
Hi Dan,
I was looking at your dispose method and I think I’m a bit confused.
When I call the the dispose method to dispose of the total tree it does not happen.
I call it as follows. Am I doing something wrong ? Is there another way to call this to dispose the total tree?
I have defined a tree object as ‘ChainTree’ ( just the name of the object) object and I’m calling the dispose as follows.
ChainTree.Dispose();
Am I missing something ?
BTW, Again thanks for posting such a great article.
Thank you
Noiloan said
Dear Dan,
Please check source download file again , I can not download it.May you send direct to email noi_loanxmen@yahoo.com.
Thanks
Günther said
Hi,
great post, but what is there ‘intelligent’?
Kind regards,
Günther
vextasy said
It looks to me as though the source file for this article has been hacked.
Dan Vanderboom said
Yeah, someone being very immature. I’ve fixed the link.
ALI said
Hi Dan
I am working now on Web Data Extraction project and the approach which i use is like this :
1- read the web page and remove unwanted data
2- build a DomTree contains the HTML elements.
I need to assigne with each element ( the Position for this element , how many childreen for this element )
assume that :
some words
AAAAA
bbbb
the information which i want to handle by the tree is :
element 1 : html number of childreen is 2
..etc
elem
what I would like to ask about is it poosible to use your code to do this job .
could give me hinte about how i will be able to do that ?
Dan Vanderboom said
Hi Ali,
What I’d do is define a DomNode class that contains all the information you want to store about each node, and then create a Tree collection. Additionally, if you want the DomNode to be aware of its place in the tree (including that node’s child nodes for a count), then implement the ITreeNodeAware interface. Like this (replace parentheses with angle brackets where it makes sense):
public class DomNode : ITreeNodeAware (DomNode)
{
public string Html;
public int Position;
public int ChildrenCount { get { return Node.Children.Count; } }
private TreeNode(DomNode) _Node;
public TreeNode(DomNode) Node
{
get { return _Node; }
set { _Node = value; }
}
}
… and then somewhere else:
private Tree(DomNode); // this var points to the root of the tree
SirAsad said
Hi Dan ,
Thanks For Greate Article ,
I want Use your Sample Application in My Project but we have a little Problem. You Use Names For Every Node in Declaration of TreeNodes . EX :
Task Root= new Task(“I am Root”);
OR
Task Child1 = Root.Children.Add(new Task(“I am Child Lvl 1”));
You Instancing From Task by Root And Child1.
This is my problem that my Node ‘s name is not given at first and i load nodes datas from database at Runtime So my Tree Build in Runtime . You Worked with Given Datas but for un-given datas what we do?
Thanks Lot;
Dan Vanderboom said
SirAsad,
Yes, I created variables for specific nodes for the purpose of example, but that need not be the case. In an application I’m currently building, I also am loading nodes from the database. What I recommend is creating a variable for your root node, point it to the object you instantiate from your database, and let all of the other nodes be referenced from the root. If you need to manipulate a non-root node, you can navigate through Children or perform some kind of search to obtain that node to work with, set a temporary variable to that discovered node, and work with it that way.
Does that make sense?
Ceyhun Ciper said
This is awesome!
No, it is gorgeous!
I can’t find enough superlatives for your effort.
And thanks for the very comprehensive and high-quality literature that you accompanied your technical endeavor with; I wish publishers were after your kind of writing and publish 100-page chef-d’oeuvres instead of 1000-page useless screen-shots or whatever.
Best Regards,
Ciper
allan said
can i use a non binary tree in making a program for df automaton?
Dan Vanderboom said
It’s not application specific, so I imagine you could use it. What’s DF automation?
o_o said
do you have an update of your code?
the code download has a couple of TODOs. BreadthFirst for example doesn’t iterate all descendants, or setting Parent to null leads to a stack overflow exception.
I fixed a couple of issues here and there but I was wondering whether you have finalized your code in the meantime.
cheers
Dan Vanderboom said
I don’t yet have an update, but I’ve had several requests lately, and there’s truly not much work left. I thought I’d leave these things as trivial work to be left to the reader 🙂 but I will take this as encouragement to complete it. Thanks for writing!
David Wright said
I was looking for an example of implementing Trees in C# and came across your site. I’m fairly new to C# (although not to programming), and am trying to understand the code so I typed it in from the listing here. The second ‘Add’ method for TreeNodeList doesn’t like the ” part. Complains that there is no ‘implicit reference conversion’ for T and IDisposable. I would have downloaded the code, but the link returns an error (500.19 Internal Server Error). Any help would be appreciated. Thanks.
Gregor Suttie said
Hi There
I tried to downloa dthe source for your non-binary tree article but i get an iis error – any chance you coudl email me the source please?
Many Thanks
Gregor
Ross said
Hi Dan,
Very helpful article!
There is a problem, however. The source download link seems to be broken.
error message:
“HTTP Error 500.19 – Internal Server Error
The requested page cannot be accessed because the related configuration data for the page is invalid.”
I look forward to seeing the source.
Cheers
Dan Vanderboom said
@everyone
I am working on the download link problem. They will unfortunately take a week or so to be restored. Sorry for the inconvenience!
holbox said
Hello!
thanks for your great code. very helpfull.
I m trying to use the ComplexTree, but i must do something wrong, for example if in your sample i m trying to create a ComplexTree it s throwing me a exception, is it normal? am i using it wrong?
here is my code :
ComplexTree taskTree = new ComplexTree(); <= throwing an exception here…
taskTree.Children.Add(new Task("task1");
thanks in advance for your answer!
Regards,
Alberic
Dan Vanderboom said
@holbox, is Task a class or a struct in your code?
Holbox said
Task is a class, i m using the task class in your sample code.
Holbox said
Hello,
Sorry for the delay, i answered right after i received your anser, but i think i must have done a mistake….
Because i wasn’t receiving any answers, i thought it was weird so i came on the website and just realized my reply didn’t appeared…
The Task class I’m using is the one you use in your sample project.
Regards,
Albéric
Jean-Sebastien said
I am trying to use the tree (I tried SimpleTree so far) with the XNA content pipeline, and it keeps complaining when serializing the tree. Anyone had any luck with the content pipeline?
Johnny said
I like this article a lot. Will someone please let me know where I can download the sample code? Thanks,
Johnny
Johnny said
Got the code. Thanks,
Johnny said
How do you access a node which only has a value? I am trying to remove/add a node. The following code is copied from the SimpleTree sample.
// declare a new tree
SimpleTree MakeDinnerTree = new SimpleTree();
// the tree will also be our root node
SimpleTreeNode root = MakeDinnerTree;
root.Value = “make dinner”;
SimpleTreeNode prepare = root.Children.Add(“prepare ingredients”);
prepare.Children.Add(“chop onions”);
prepare.Children.Add(“grate cheese”);
prepare.Children.Add(“measure milk”);
How do you remove “chop onions”? How do you add a child to “chop onions”?
Thank you so much.
Johnny
al said
Hi Dan, don’t know if you’re still checking comments on this or not…
I’ve been playing around with this code recently, it’s very handy for me – especially because of it’s serialisablity!
One of the things that I noticed is that i use members of the Children property, i have to do a cast – eg using your task example
Task noddy = Enid.Children[0]; //doesn’t work
Task noddy = (Task)Enid.Children[0]; //does work
(the same issue occurs using the simple version.)
I thought one of the points of using Generics is to avoid this kind of casting?
I guess it’s to do with the way the TreeNode and the TreeNodeList reference each other, but aren’t in the same class.
However my understanding of Generics is way too feeble to work out how to make it clear to the compiler that the child of a Task is itself a Task and not a ComplexTreeNode.
al
al said
that darn xtml..
that last word should have been ComplexTreeNode<Task>
al
Michel said
Hi Dave,
Great Article! Any updates on the custom serialization logic ? Are you still planning to write an article about that ?
Thanks,
Michel
Dan Vanderboom said
Hi Dave,
Yes I am still planning to update the project to include better serialization. I believe I gave some examples in one of the comments, and I’ll take another look at it, but I can’t promise when that will happen. Hopfully in the next month or so.
Interested said
Dan,
Any progress on serialization? I’m trying to return the simple tree in a WCF service, but encounter numerous serialization issues.
Thanks
Eric said
Hi,
Great article. Thanks for the effort you put into this. I have a question about a possible typo in some of the example code. I think I understand the intention, but only if there really is a mistake.
In the section “Begin with the End in Mid” there is a code sample that begins like so:
Tree root = new Tree();
root.Value = “zero”;
Should this instead be:
Tree zero = new Tree();
zero.Value = “zero”;
because later on in the code the variable named “zero” is referenced a couple of times. If that’s the case then I get it. Thanks again for the awesome article!
Eric said
I also just realized that the editor stripped out the “of type string” generic declaration on Tree because it didn’t like the brackets (my bad for not using the code tags), but I think you’ll see what I am referring to in the original code sample.
Henry Mayors said
All I can say is wow when I come here. I love your blog!
Michael Jennings said
Daaaaamn, this is a juicy article. I looked around trying to see if you posted any updates after the long back and forths, but I might have missed it… I would surely love to feel up whatever latest you got laying around, even if it is midway through some change that makes it incompilable… Would you be so kind as to email me or post the link?
Dan Vanderboom said
@mjennings – Thanks for the compliment. Is there any specific functionality you’re looking for? Are you referring to XML serialization? This is coming soon, perhaps as early as this weekend.
Gonzalo said
Great work!
Anyone has tried to databind the ComplexTree to a TreeView in WPF? I’m beginning with this and any ideas will be appreciated.
Thanks.
jailbreak iphone 3gs 4.0 said
Hi. I feel lucky to find out your blog.you are doing a great job here.thank you very much for sharing this informative topic.
Kevin said
Thanks a lot for a class piece of code.
pamkkkkk said
Hello Dan !
Thank you for your very good Article and this super Classes !
My intention is to store hirachical data into the Application Setting (user.config).
(storing TreeViews or Menu structures)
So i need a Class, wich is uncomplex serializeable.
In my research through the Internet, i found your good work!
Is there any Progress in serialization?
Thank you !
Frank Aurich said
Thanks for this insightful article!
I’ve tried to replicate the code from the blog post itself but am stuck with a couple of compiler errors when instantiating Task child nodes.
Unfortunately, the link to the source code is broken.
Could anyone provide another link for the source please?
Cheers!
Taco said
Thank you, you are filling a gap in the framework!
Tim said
Hello,
What a very interesting article and as a beginner, I love the working code to use as a sound base for further investigation.
Would the souce soon be available?
Simone Ferrari said
Hi, looking at the final code in the download what exactly is the use of ComplextTree??
It is never used, and infact if you try to create a ComplextTree it crashes with
Unable to cast object of type ‘System.Collections.Generic.ComplexTree`1[TreeDataStructure.Task]’ to type ‘TreeDataStructure.Task’.
Seer said
Simone I was jsut about to look into that error because i was getting it in my code as well. Guess i will just have to use an actual node instead of ComplexTree. Thanks for saving me some time.
Ian Powell said
I can’t seem to see the download link
Ian Powell said
Never mind found it => “Download the Source”
Mizan Rahman said
Hi there,
Thank you for this great work. But I have a bit different situation. I need all the nodes to be in a master list at all time while maintaining this hierarchical relation ship in a generic way. List must be in the same order as the tree structure.
Any suggestions or examples or sample as to how to go about desigining this data structure that will meet my need?
Thanks in advance.
Mizan
Dan Vanderboom said
Hi Mizan,
You could create a new List and then iterate over the whole tree with the appropriate traversal strategy with IEnumerable to get all the nodes into your flat List. Each node would then still be aware of its depth, parent, etc.
Best regards…
DotnetDeveloper said
Hi Dan,
The article is great, I feel like i understood but not sure completely and trying to figure out whether this code will work when the input is like a list of paths. Each time when i add it should check whether the parent exists, if not it should no add else should not add it. my structure would be some thing like this. So i have to build a tree or hirearchial structure c# object for this, this object will be an input for a Rad tree view control.
Country/Teams/USA/Soccer
Country/Teams/USA/FootBall
Countr/Teams/Usa/BasketBall
country/Teams/India/Cricket
countr/teams/India/Cricket/TeamA
country/teams/India/cricket/TeamB
countr/teams/India/Football/Region
countr/teams/India/Football/Region/District/…
country/teams/xyz/somegame
It would be great if you can send me a sample for this.
Andre van Dun said
Dear Dan, i tried to serialize a complextree but i got an error with: {“Unable to cast object of type ‘PMWorkbench.Project’ to type ‘System.Collections.Generic.ComplexTree`1[PMWorkbench.WBSItem]’.”} in this code:
StreamWriter sw = new StreamWriter(@”.\tree.xml”);
XmlSerializer ser = new XmlSerializer(typeof(ComplexTree), new Type[] { typeof(ComplexTreeNode) });
ser.Serialize(sw, project);
sw.Close();
The PMWorkbench.Project is a derived class from WBSItem : ComplexTreeNode (which is the original Task from your example code).
Can you send me a working example for serialization of a complex tree ? based on your example code ?
Bennett Dill said
Hi & thanks for the post, I knew I’d find something out there instead of doing a roll your own implementation of a hierarchy wrapper and your implementation is top notch 🙂
I needed a FindNode method and didn’t see one implemented in your code or the comments, so I finally broke down and wrote some code 😉 I thought I’d share it here just in case anyone else is looking for similar functionality. I’m only using the simple node, but I suspect it would port to the complex version very easily.
public SimpleTreeNode FindNode(Func predicate, TreeTraversalType traversalType, TreeTraversalDirection traversalDirection)
{
foreach (var node in GetEnumerable(traversalType, traversalDirection))
{
if (predicate(node.Value))
{
return node;
}
}
return null;
}
it can be used like this:
var parent = root.FindNode(x => { return x.CategoryId == item.ParentCategoryId; }, TreeTraversalType.BreadthFirst, TreeTraversalDirection.TopDown);
Thanks again!
Bennett Dill said
Reposting of code with HTML escaped greater than/less than to facilitate rendering of generics code:
public SimpleTreeNode<T> FindNode(Func<T, bool> predicate, TreeTraversalType traversalType, TreeTraversalDirection traversalDirection)
{
foreach (var node in GetEnumerable(traversalType, traversalDirection))
{
if (predicate(node.Value))
{
return node;
}
}
return null;
}
Kenny said
This is a really good tip especially to those new to the blogosphere.
Brief but very precise information Many thanks for sharing this one.
A must read post!
DHK said
Hi Dan,
I read through the great post (kudos!) and the majority of the comments. Good discussion too.
However, I couldn’t find the source at the GITHUB site: Everything seemed to be about a particular usage, not the pure implementation. Where is the needle in this haystack, please?
Dan Vanderboom said
https://github.com/danvanderboom/Xamarin-Forms-TreeView
Sorry for the long delay. I haven’t visited my blog in many months.
Cheers!
Geoff said
Hi Dan
Just downloaded this from GiTHub and found that none of the tests or demos use more than one class type in its tree.
I don’t see how to implement this as the parent (and root) won’t work with different types.
Could you advise as to whether you think it would be possible to have a TreeNode class where R=Root, P=Parent, N=Node, C=Children?
I have read elsewhere that this is not practical.
Possibly one way would be to separate the Value into a different generic and have the tree infrastructure constant.
Cheers
Geoff
Dan Vanderboom said
Hi Geoff,
The tree data structure used by this TreeView control depends on the composite pattern implemented by the recursive TreeNode class and tree data structure, which provides a common surface area at all levels of the tree, important for all of the data binding to work.
Depending on what your custom tree objects are used for and what their lifecycle needs are, you may be able to use the composite TreeNode approach, then use the root node’s iterator to construct a new tree using your custom-type-per-node-level. You could write an extension method like:
public static MyRootType ToMyTree(this TreeNode root)
{ … }
Because the nodes are observable, you could also respond to each change event in the tree and make corresponding changes in your custom-type-tree, if you need it to be in memory and active before it’s done being constructed in a UI.
You might also experiment with deriving your custom node classes from TreeNode, if possible. This reveals a possible limitation of basing the tree on TreeNode rather than an interface, which would free up your custom tree node classes so they can inherit from other base classes.
Best of luck,
Dan