RecentIy I needed to find a specific TreeNode in a TreeView control. I expected that would be easy with LINQ, but quickly realized that there is no method in the .NET framework that will let me traverse all nodes of a hierarchy. I decided to create one myself.
I started by trying out how I would expect to use it. I quickly landed on a syntax like this:
var q = from node in root.FlattenHierarchy() select node; |
How would the hierarchy be flattened? Well, implemented as an extension method, the method would look like this:
public static class LinqToHierarchical { public static IEnumerable FlattenHierarchy(this TreeNode node) { yield return node; if(node.Nodes != null) { foreach(var child in node.Nodes) { foreach(var childOrDescendant in child.FlattenHierarchy()) { yield return childOrDescendant; } } } } } |
The above code works, and there are no problems with it if you know beforehand what kind of hierarchy you’re going to work with. In the code above, it works well with the nodes of a Windows Forms TreeView control.
Yet still, I’m not satisfied. Can I make a generic extension method that will flatten any hierarchy? Even those not made up of TreeNode objects?
To do that, we need to analyze which parts of the method needs to be swapped out. That would be the TreeNode’s Nodes property. Can we acccess that in an other way? Yes, I think a delegate can help us, so lets give it a try:
public static IEnumerable FlattenHierarchy(this T node, Func<T, IEnumerable> getChildEnumerator) { yield return node; if(getChildEnumerator(node) != null) { foreach(var child in getChildEnumerator(node)) { foreach(var childOrDescendant in child.FlattenHierarchy(getChildEnumerator)) { yield return childOrDescendant; } } } } |
Now, that wasn’t difficult. But did we just complicate the usage of our extension method? Yes, we did. When we’re going to flatten a hierarchy, we’ll have to tell where to find the children. Not to hard though, since we can use a lambda expression for that. Here’s how we use it now:
var q = from node in root.FlattenHierarchy(x => x.Nodes) select node; |
Now we’re able to use it with any hierarchy. Some samples include:
//The filesystem var q = from directory in new DirectoryInfo(@"c:\").FlattenHierarchy(x => x.GetDirectories()) select directory; //XML (Yeah, I know: xml.Descendants() will also flatten this...) var xml = XElement.Load(@"filename.xml"); var q = from element in xml.FlattenHierarchy(x => x.Elements()) select element; //Control tree in Windows Forms or in ASP.NET var q = from control in Controls.FlattenHierarchy(x => x.Controls) select control; |
Now, where can you go from here? I think what we have here is quite usefull as is, but some ideas include;
- Limit traversal on depth level
- Include leaf nodes of types that don’t include a subnode collection
- Traverse one level at a time, instead of traversing down each branch as we find them
Converted to vb.net…
Imports System.Runtime.CompilerServices
Imports System.IO
Public Class Form1
Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
Dim ctrls = From ctrl In CType(Me, Control).FlattenHierarchy(Function(x As Control) x.Controls.Cast(Of Control)())
Select ctrl
Dim directories = From directory In New DirectoryInfo(“C:\temp”).FlattenHierarchy(Function(x As DirectoryInfo) x.GetDirectories())
Select directory.FullName
End Sub
End Class
Module X
_
Public Function FlattenHierarchy(Of T)(ByVal node As T, ByVal getChildEnumerator As System.Func(Of T, IEnumerable(Of T))) As IEnumerable(Of T)
Dim q As New List(Of T) From {node}
Dim children As IEnumerable(Of T) = getChildEnumerator(node)
If children IsNot Nothing Then
For Each child As T In children
For Each childOrDescendant In child.FlattenHierarchy(getChildEnumerator)
q.Add(childOrDescendant)
Next
Next
End If
Return q
End Function
End Module
What I cant find is a way to traverse a tree with a “Next” and “Previous” button.
I can do it to a certian degree, but it has problems.
The problem occurs when you step into a child. For example.
+MyDVDs
–Awaydays
–Dog Days
–Die Hard Series
—-Die Hard 1
—-Die Hard 2
—-Die Hard 3
–Get Smart
–Happy Gilmore
How can I click “Next” and have it traverse down the tree, one step at a time, and then at any point, traverse back up the tree?
Please help.
I should have given the additional level of the drive. It is the drive level that really complicates things:
E:\DVDs
–Awaydays
–Dog Days
–Die Hard Series
—-Die Hard 1
—-Die Hard 2
—-Die Hard 3
–Get Smart
–Happy Gilmore
F:\DVDs
I have tried using a recursive call down the tree and storing that in a List(of T), but the problem comes in trying to assign the Selected method to the List…
TreeView1.Selected = t_myDVDs.MovieName
Should I store a List(of Nodes) perhaps?
By traversing the List instead of the tree, it would seem to make the “Previous” trip back up the tree less complicated, yes?
Please help. I have been fighting this for days.
Hi Gary!
Putting the results in a list, would allow you to walk to next or previous node with the indexer. But part of your problem is that you don’t have the depth/level of the original node.
Well, this article is really about flattening the hierarchy, so any information about depth or level in the hierarchy will be lost.
You can however modify my code, and add a level counter mechanism to it. The steps would be something like this:
1. Take in an aditional parameter to the FlattenHierarchy method. (int depth)
2. On both yield return statements you could return a new object that has both the depth+1 and the data to return.
3. Modify the calls to the FlattenHierarchy method to include current depth.
Hope this helps you on your way!
Yes, the problem for the way I am doing it now is not knowing until runtime how deep the levels go.
I was a “C” programmer for more than a decade but have become much more comfortable using VB.net.
I like the idea of having recursive calls because then I dont have to code for each level, but am struggling with your suggestion of how to return the depth.
Would it be just add one to the current depth on each return?
Could you post a little snippet (in vb 2010) of how that would be done?
I am really intrigued by your concept of flatting the hiearachy. Seems much more elegant than the way I am doing it now but keeping track of which level I am in and reading the next node to see if there are any children. The way I am doing it now, I have to know ahead of time how many levels to program for. Ugh…
Any futher help would be very much appreciated.
Hi Gary!
I did your homework (in C#) ;) I made a new class LevelAndData, which is used both internally in the new
FlattenHierarchyWithLevels
method and as the return type.I think this does what you ask:
Here’s how to use it:
You’ll need to VB-ify it yourself. Hope it helps!
How can you use it with the Controls collection of the System.Web.UI.Control class?
It does not expose an sub-list, but the elements exposed by the Controls colection expose the Controls property.
In MSDN it says that the Control class exposes a Controls collection. The example in the last codeblock in the article should work!
This looks pretty good. I couldn’t figure out how to work this out where the root element is not a hierarchical type. In my case a ProjectTemplate has a Folders collection and the Folder objects in the Folders collections also contain collections of folders.
Can someone improve upon my solution as I worked it out below to make it a little more elegate(ie remove the result list from the recursive function.
public static class ProjectTemplateExtensions
{
public static IEnumerable RazorTemplates(this ProjectTemplate projectTemplate)
{
var razorTemplates = new List();
foreach (var folder in projectTemplate.Folders)
{
PopulateRazorTemplates(folder, ref razorTemplates);
}
}
public static void PopulateRazorTemplates(Folder folder, ref List razorTemplates)
{
razorTemplates.AddRange(folder.RazorTemplates);
foreach (var childFolder in folder.Folders)
{
PopulateRazorTemplates( childFolder, ref razorTemplates);
}
}
}