Tree Structures and Navigation

• Download source code

Introduction

I continue a series of blog posts about implementing WPF concepts outside of WPF.

This post talks about generic Tree structures in C#. The relationship with WPF will become clearer once we start talking about Routed Events outside of WPF (hopefully in the next post).

In his great LINQ TO VISUAL TREE and LINQ to Tree – A Generic Technique for Querying Tree-like Structures articles, Colin Eberhardt talks about queries various Tree structures using LINQ. In order to fit the Tree structure into his framework, the user of the code should either build an adaptor satisfying ILinqToTree interface for the tree nodes, or generate such adaptor and the corresponding LINQ functions using VisualStudion T4 templates.

Here I am defining a Tree structure without resorting to adapter interface and using delegates instead. This makes it more generic and makes it possible to apply the concept to a very wide class of objects without T4 template generation.

What is a Tree?

A Tree is a set of objects called the TreeNodes. From any TreeNode, one should be able to find its unique parent TreeNode (if it exists) or its collection of child TreeNodes (if they exist). The above Tree definition allows to find all the TreeNodes of a Tree recursively, the following information is given:

• A TreeNode to start navigation.
• A function that for any TreeNode returns its parent TreeNode or null (if it has no parent).
• A function that for any TreeNode returns a collection of its children (it might be null or empty collection if no such children exist).

Translating the above into C# (or any other object oriented language that allows delegates or lambdas) we can write that the Tree can be defined by one TreeNode object or a generic type TreeNode and two delegates:

Func<TreeNode, TreeNode> ToParentFunction

and:

Func<TreeNode, IEnumerable<TreeNode>> ToChildrenFunction

Note, also, that for navigating up the Tree only ToParentFunction is required while for navigating down the Tree – only ToChildrenFuncion.

The Tree API

Based on the discussion above, I created a generic API for navigating up and down the Tree using C# extension functions. The API is located within NP.Paradigms.TreeUtils static class under NP.Paradigms project. The available functions are very similar to those from Colin Eberhardt’s articles, the difference is that one extra argument is required – the function for navigation up or down a Tree:

/// Returns a collection of all ancestors of a node.
public static IEnumerable<NodeType> Ancestors<NodeType>
(
this NodeType node,
Func<NodeType, NodeType> toParentFunction
)

/// Returns the node itself and all its ancestors a part of a collection.
public static IEnumerable<NodeType> Ancestors<NodeType>
(
this NodeType node,
Func<NodeType, NodeType> toParentFunction
)

/// returns itself and all its descendants as part of a collection
/// of TreeChildInfo object that contain the node itself and the 
/// distance from to original node (called Level). 
/// Original node passed as an argument to this function 
/// has its level specified by the level argument (the default is 0)
/// its children will have Level property set to 1, grandchildren - to 2 etc.
public static IEnumerable<TreeChildInfo<NodeType>> SelfAndDescendantsWithLevelInfo<NodeType>
(
this NodeType node,
Func<NodeType, IEnumerable<NodeType>> toChildrenFunction,
int level = 0
)

/// Returns the descendants nodes with level info (just like SelfAndDescendantsWithLevelInfo)
/// only within the original node itself. 
public static IEnumerable<TreeChildInfo<NodeType>> DescendantsWithLevelInfo<NodeType>
(
this NodeType node,
Func<NodeType, IEnumerable<NodeType>> toChildrenFunction
)

/// Returns the original node and its descendants as part of a collection
public static IEnumerable<NodeType> SelfAndDescendants<NodeType>
(
this NodeType node,
Func<NodeType, IEnumerable<NodeType>> toChildrenFunction
)

/// Returns the descendants of an original node as a collection
public static IEnumerable<NodeType> Descendants<NodeType>
(
this NodeType node,
Func<NodeType, IEnumerable<NodeType>> toChildrenFunction
)
{
return node.DescendantsWithLevelInfo
(toChildrenFunction).Select((treeChildInfo) => treeChildInfo.TheNode);
}

/// Returns the ancestors of the current node (starting from the Root node) 
/// and the current node's descendants. Level specifies the 
/// distance from the Root Node (top node)
public static IEnumerable<TreeChildInfo<NodeType>> AncestorsAndDescendants<NodeType>
(
this NodeType node,
Func<NodeType, NodeType> toParentFunction,
Func<NodeType, IEnumerable<NodeType>> toChildrenFunction
)

/// returns all the nodes of the tree except for the
/// original node itself, its descendents and ancestors (the top node is still returned
/// even thought it is an ancestor).
public static IEnumerable<TreeChildInfo<NodeType>> AllButAncestorsAndDescendants<NodeType>
(
this NodeType node, 
Func<NodeType, NodeType> toParentFunction,
Func<NodeType, IEnumerable<NodeType>> toChildrenFunction
)

The last two functions AncestorsAndDescendants and AllButDescendantsAndAncestors do not have analogues in Colin Eberhardt’s articles, but are still pretty useful sometimes.

Non-Visual Tree Usage Example

The usage example can be found under project TreeTests (do not forget to make this project a start up project within the solution).

In the Main function of this project (located within Program.cs file, we build a tree out of TestTreeNode objects. Each TestTreeNode object contains a Parent property specifying the parent of the node, Children collection specifying the children of the node and NodeInfo property – which is simply a string that should uniquely identify the node. Function AddChild(string childNodeInfo) facilitates building the tree. It adds a child node setting its NodeInfo property to the passed string parameter and setting its Parent property to the current node.

Here is how we build the tree:

#region Start building tree out of TestTreeNodes objects
TestTreeNode topNode = new TestTreeNode { NodeInfo = "TopNode" };

TestTreeNode level2Node1 = topNode.AddChild("Level2Node_1");
TestTreeNode level2Node2 = topNode.AddChild("Level2Node_2");

TestTreeNode level3Node1 = level2Node1.AddChild("Level3Node_1");
TestTreeNode level3Node2 = level2Node1.AddChild("Level3Node_2");

TestTreeNode level3Node3 = level2Node2.AddChild("Level3Node_3");
TestTreeNode level3Node4 = level2Node2.AddChild("Level3Node_4");
#endregion End tree building

The functions to go up and down the tree are specified in the following way:

// to parent function
Func<TestTreeNode, TestTreeNode> toParentFn =
(treeNode) => treeNode.Parent;

// to children function
Func<TestTreeNode, IEnumerable<TestTreeNode>> toChildrenFn =
(treeNode) => treeNode.Children;

Finally, we print ancestors and descendents of the nodes:

Console.WriteLine("Print ancestors of node level3Node3");

foreach (var treeNode in level3Node3.Ancestors(toParentFn))
Console.WriteLine("\t" + treeNode.NodeInfo);

Console.WriteLine("\n");

Console.WriteLine("Print self and ancestors of node level3Node3");
foreach (var treeNode in level3Node3.SelfAndAncestors(toParentFn))
Console.WriteLine("\t" + treeNode.NodeInfo);

Console.WriteLine("\nPrint whole tree");

foreach (var treeNodeInfo in topNode.SelfAndDescendantsWithLevelInfo(toChildrenFn))
{
// shift the string by the level number plus 1 tabs
string tabs = new string('\t', treeNodeInfo.Level + 1);

Console.WriteLine(tabs + treeNodeInfo.TheNode.NodeInfo);
}

Here are the printed results:

Print ancestors of node level3Node3
Level2Node_2
TopNode

Print self and ancestors of node level3Node3
Level3Node_3
Level2Node_2
TopNode

Print whole tree
TopNode
Level2Node_1
Level3Node_1
Level3Node_2
Level2Node_2
Level3Node_3
Level3Node_4

Note that when we print the top node of the tree and its descendents (the last print out), we shift the descendents to the right by placing Tab characters in front of the strings. The number of those tab characters equals to the Level property of the corresponding TreeNodeInfo object so that the farther the nodes are from the top node, the farther to the right they will appear.

WPF Visual and Logical Trees Usage Examples

WPF VisualTreeHelper and LogicalTreeHelper classes can furnish us with delegates to go up and down visual and logical trees correspondingly. Project NP.Paradigms.Windows contains VisualTreeUtils and LogicalTreeUtils static classes providing LINQ functions for Visual an Logical trees correspondingly. They are simply wrappers around NP.Paradigms.TreeUtils class described above.

VisualTreeHelper operates on objects of FrameworkElement class. Because of this, all the VisualTreeUtils functions operate on FrameworkElement objects. Here is how we define the ToParentFunction and ToChildFunction for the VisualTreeUtils class:

static Func<FrameworkElement, FrameworkElement> toParentFunction =
(obj) => VisualTreeHelper.GetParent(obj) as FrameworkElement;

static Func<FrameworkElement, IEnumerable<FrameworkElement>> toChildrenFunction =
(parentObj) =>
{
int childCount = VisualTreeHelper.GetChildrenCount(parentObj);

List<FrameworkElement> result = new List<FrameworkElement>();
for (int i = 0; i < childCount; i++)
{
result.Add(VisualTreeHelper.GetChild(parentObj, i) as FrameworkElement);
}

return result;
};

The extension method of VisualTreeUtility class are self explanatory and correspond to the TreeUtils class methods one to one except that they start with prefix Visual to avoid the name clashes.

When it come to LogicalTreeHelper, some of the children that it returns might not be of FrameworkElement type. If fact, contents of the Buttons or of TextBlock or other objects can be simply strings. Because of that, we define all of our extension methods on plain objects. Here is how the ToParentFunction and ToChildFunction are defined for the logical tree:

static Func<object, object> toParentFunction =
(obj) =>
{
if ( !(obj is DependencyObject) )
{
return null;
}

return LogicalTreeHelper.GetParent(obj as DependencyObject);
};

static Func<object, IEnumerable<object>> toChildrenFunction =
(parentObj) =>
{
if (!(parentObj is DependencyObject))
{
return null;
}

return LogicalTreeHelper.GetChildren(parentObj as DependencyObject).Cast<object>();
};

The extension methods of the LogicalTreeUtils class are also self explanatory and have prefix Logical to avoid the name clashes.

The usage example for VisualTreeHelper and LogicalTreeHelper methods is located under VisualTreeTests project. The function MainWindow_Loaded gets the tree nodes for the visual and logical trees of ElementToDisplay grid that contains a TextBlock and a Button. The collections of tree nodes are converted into collections of TreeNodeDisplayer objects that transform the tree nodes into indented strings: FrameworkElements are displayed by their type name in parentheses followed by name and other objects are simply converted to strings using ToString() method. The indentation is related to their level within the tree (how far they are from the root node of the tree). The visual and logical trees are displayed under the ElementToDisplay:

CodeProject