Click here to Skip to main content
11,486,023 members (76,841 online)
Click here to Skip to main content

Tagged as

Tree Structures and Navigation

, 29 Nov 2013 CPOL 5.2K 7
Rate this:
Please Sign up or sign in to vote.
Code Location The code for this blog post can be downloaded from TreeTestsCode.zip. Introduction CodeProject 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 st

Code Location

The code for this blog post can be downloaded from TreeTestsCode.zip.

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 Tree Nodes. From any Tree Node one should be able to find its unique parent Tree Node (if it exists) or its collection of child Tree Nodes (if they exist). The above Tree definition allows to find all the Tree Nodes of a Tree recursively, the following information is given:

  • A Tree Node to start navigation.
  • A function that for any Tree Node returns its parent Tree Node or null (if it has no parent).
  • A function that for any Tree Node 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 Tree Node 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 agument 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 anscestors 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 ascestor).
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) fascilitates 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 anscestors 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 explanotary 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 explanotary and have preffix 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:

License

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

Share

About the Author

Nick Polyak
Architect AWebPros
United States United States
I have 15 years of experience developing enterprise software, starting from C++ and Java on UNIX and moving towards C# on Windows platforms.
I am fascinated by the new .NET technologies especially WPF, Silverlight and LINQ.
Recently I decided to make a move and start my own contracting consulting and mentoring company AWebPros.
I can be contacted via my web site awebpros.com or through my blog at nickssoftwareblog.com

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150520.1 | Last Updated 29 Nov 2013
Article Copyright 2013 by Nick Polyak
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid