TreeViewWalker - Simplifying Recursion

• Download source code - 20.3 KB

Introduction

Working with the TreeView control usually requires the use of recursion (when a method calls itself). Some developers have a difficult time writing or maintaining recursive methods. The utility class presented in this article, TreeViewWalker, was created to help abstract recursion away from the business logic; creating a more palatable TreeView programming model.

The net result of using this class is that the application developer does not need to deal with the added complexity inherent in recursive methods.

Background

The TreeViewWalker uses two concepts that the developer must be aware of: sibling and descendant nodes. If you are not familiar with these concepts, the following explanations should clarify them for you.

Sibling Nodes

A node is in the same TreeNodeCollection as all of its siblings. In the screenshot at the top of the article, "Lunch" and "Dinner" are siblings. "Ham Sandwich" and "Risotto" are not, since they belong to different TreeNodeCollections.

Descendant Nodes

A descendant is in the Nodes collection of another node, or one of that node's children, or one of the children's children, etc. In the screenshot above, "Apple Sauce" is a descendant of "Meals", "Lunch" and "Food". "Bread and Butter" is not a descendant of "Lunch".

Using the Code

TreeViewWalker is pretty simple to use. You create an instance of the class, specify the TreeView it will navigate, hook the ProcessNode event, and then call the ProcessTree method. For example:

TreeViewWalker treeViewWalker = 
                          new TreeViewWalker( this.treeView );
treeViewWalker.ProcessNode += 
    new ProcessNodeEventHandler( treeViewWalker_ProcessNode );
treeViewWalker.ProcessTree();

The ProcessNode event will fire for every TreeNode that the TreeViewWalker encounters. The nodes are navigated in a top-down fashion, wherein the ProcessNode event will fire for a node's next sibling after all of the node's descendants. To put this in more concrete terms, take a look at the screenshot of the demo application at the top of this article. The ProcessNode event is raised for the first few nodes in this order: "Meals", "Lunch", "Food", "Ham Sandwich", "Apple Sauce", "Drinks", "Iced Tea", "Dinner", etc.

The final step to using this class is creating a method to handle the ProcessNode event. Below is an example of such a method, which happens to toggle the Checked property of each TreeNode in the tree:

private void treeViewWalker_ProcessNode( object sender, 
                                     ProcessNodeEventArgs e )
{
    e.Node.Checked = ! e.Node.Checked;
}

The ProcessNodeEventArgs class exposes several properties that you can use while processing the nodes in a tree:

• Node - Returns the TreeNode to process.
• ProcessDescendants - Gets/sets a value which determines whether the ProcessNode event should be raised for the descendant nodes of the current TreeNode. The default value is true. If StopProcessing is set to true, this property is ignored.
• ProcessSiblings - Gets/sets a value which determines whether the ProcessNode event should be raised for unprocessed sibling nodes of the current TreeNode. The default value is true. If StopProcessing is set to true, this property is ignored.
• StopProcessing - Gets/sets whether the ProcessNode event should be raised for any of the remaining nodes in the TreeView. If this property is set to true, the ProcessDescendants and ProcessSiblings properties are ignored.

Suppose you are certain it is not necessary to have the TreeViewWalker recurse over the descendants of a node. In that situation, you can set the ProcessDescendants property to false, as seen in the following example:

private void treeViewWalker_ProcessNode_HighlightFoodNodes( 
                       object sender, ProcessNodeEventArgs e )
{
    if( e.Node.FullPath.IndexOf( "Food" ) > -1 )
    {
        e.Node.BackColor = Color.LightGreen;
    }
    else if( e.Node.Text == "Drinks" || e.Node.Text == "Dessert" )
    {
        // There is no need to process any nodes 
        // in the "Drinks" or "Dessert" branches
        // so tell the TreeViewWalker to skip them.
        e.ProcessDescendants = false;
    }
}

If there is no need for the TreeViewWalker to recurse over the siblings of a node, then set the ProcessSiblings property to false, as seen in the following example:

private void treeViewWalker_ProcessNode_HighlightSecondNodeInEachNodeIsland(
                                       object sender, ProcessNodeEventArgs e)
{
    if( e.Node.Index == 1 )
    {
        e.Node.BackColor = Color.LightGreen;
        // Once the second node in a node island 
        // has been highlighted, there is no need
        // to process any of the other nodes in 
        // that island, so tell the TreeViewWalker
        // not to fire the ProcessNode event for the siblings.
        e.ProcessSiblings = false;
    }
}

If you want the TreeViewWalker to stop navigating the tree altogether, simply set the StopProcessing property to true, like so:

private void treeViewWalker_ProcessNode_HighlightAsparagusNode( 
                           object sender, ProcessNodeEventArgs e )
{
    if( e.Node.Text == "Asparagus" )
    {
        e.Node.BackColor = Color.LightGreen;

        // Tell the TreeViewWalker to stop navigating 
        // the tree since the "Asparagus" node was found.
        e.StopProcessing = true;
    }
}

If you only want to process a particular node branch in the tree, then call the ProcessBranch method of TreeViewWalker and pass in the TreeNode which should be the root of the branch. The demo application available at the top of this article demonstrates that.

Advanced Usage

So far, I have only shown you how to use the TreeViewWalker in simple scenarios. Now that you know why the class is used and what it exposes, let's take a look at a more sophisticated way to leverage it. This sample demonstrates how to use the TreeViewWalker when the nodes in a TreeView are populated in a load-on-demand style. It provides the user with a TextBox to supply a search string and four Buttons for navigating the nodes in the tree whose text contains the search string. The nodes in the tree represent a subset of the directories found in the user's machine.

As the screenshot above shows, there are four navigation buttons; equivalent to First, Previous, Next, and Last. The Previous and Next buttons search for the previous or next node, respectively, relative to the TreeView's selected node. Since the nodes are loaded on-demand, and the searching logic must navigate through every logical node in the tree, the dynamic node loading must occur in the ProcessNode event handling methods. To put this another way, since the TreeView will not always contain every node that must be searched, the nodes must be dynamically loaded as the search executes.

Fields

Each Button has a TreeViewWalker associated with it. There are also two helper fields used while the search executes, as seen below:

// Each search button has an associated TreeViewWalker.
// They are configured in InitializeAdvancedDemo().
private TreeViewWalker tvWalkerFirst;
private TreeViewWalker tvWalkerPrev;
private TreeViewWalker tvWalkerNext;
private TreeViewWalker tvWalkerLast;

// Helper variables used while searching the tree.
private TreeNode matchingNode;
private bool processedSelectedNode;

Find First Match

Let's take a look at what happens when the user clicks the "First" Button. As soon as a TreeNode is found whose text contains the search string, that node is selected and the TreeViewWalker is told to stop the navigation process. If a node is not a "match", then it is necessary to inspect its descendants for a match. However, since the nodes are being loaded on-demand, it is possible that the node's children have not been loaded yet. If that is the case, the node's children are loaded so that the TreeViewWalker will fire the ProcessNode event for them:

private void btnFirst_Click(object sender, System.EventArgs e)
{
    this.tvWalkerFirst.ProcessTree();
}

private void tvWalkerFirst_ProcessNode(object sender, 
                                       ProcessNodeEventArgs e)
{
    // As soon as a node is found whose text matches 
    // the search string, that node should be selected 
    // and the TreeViewWalker should stop walking down
    // the tree.
    if( this.ContainsSearchText( e.Node ) )
    {
        this.treeAdvanced.SelectedNode = e.Node;
        e.StopProcessing = true;
    }
    else if( this.HasDummyNode( e.Node ) )
        this.LoadDirectoryNodes( e.Node );
}

Find Previous Match

When the user clicks the "Previous" Button, there is a little more logic involved. The basic idea is that we allow the ProcessNode event to fire for every node until it reaches the selected node. When the selected node is processed, then the last matching node discovered is considered the "previous" node (relative to the selected node):

private void btnPrev_Click(object sender, System.EventArgs e)
{
    this.matchingNode = null;            
    this.tvWalkerPrev.ProcessTree();
}

private void tvWalkerPrev_ProcessNode(object sender,
                                      ProcessNodeEventArgs e)
{
    // If we have walked all the way down to the selected 
    // node then the most recently discovered matching node 
    // is the "previous" node, and it should be selected.
    if( e.Node == this.treeAdvanced.SelectedNode )
    {
        if( this.matchingNode != null )
            this.treeAdvanced.SelectedNode = this.matchingNode;
        e.StopProcessing = true;
        return;
    }
    
    if( this.ContainsSearchText( e.Node ) )
        this.matchingNode = e.Node;

    if( this.HasDummyNode( e.Node ) )
        this.LoadDirectoryNodes( e.Node );
}

Find Next Match

Searching for the "next" node uses the opposite logic from looking for the "previous" node. Instead of stopping the search when the selected node is processed, the search for a matching node begins after the selected node is processed:

private void btnNext_Click(object sender, System.EventArgs e)
{
    this.processedSelectedNode = false;
    this.tvWalkerNext.ProcessTree();
}

private void tvWalkerNext_ProcessNode(object sender, 
                                      ProcessNodeEventArgs e)
{
    if( e.Node == this.treeAdvanced.SelectedNode )
        this.processedSelectedNode = true;                
    
    // If we have already processed the selected node and 
    // the current node matches the search text, then we
    // have found the "next" node and it should be selected.
    if( this.processedSelectedNode               &&
        e.Node != this.treeAdvanced.SelectedNode &&
        this.ContainsSearchText( e.Node ) )
    {
        this.treeAdvanced.SelectedNode = e.Node;
        e.StopProcessing = true;
        return;
    }
    
    if( this.HasDummyNode( e.Node ) )
        this.LoadDirectoryNodes( e.Node );
}

Find Last Match

Searching for the "last" matching node involves searching the entire tree and then selecting the last node that was found whose text contains the search string. This operation is the most expensive in terms of time, since all of the nodes must be loaded before the operation terminates:

private void btnLast_Click(object sender, System.EventArgs e)
{
    this.Cursor = Cursors.WaitCursor;

    this.matchingNode = null;
    this.tvWalkerLast.ProcessTree();
    if( this.matchingNode != null )
    {
        // 'matchingNode' now points to the last node whose 
        // text contains the search string.
        this.treeAdvanced.SelectedNode = this.matchingNode;
    }

    this.Cursor = Cursors.Default;
}

private void tvWalkerLast_ProcessNode(object sender, 
                                      ProcessNodeEventArgs e)
{
    if( this.ContainsSearchText( e.Node ) )
        this.matchingNode = e.Node;
    
    if( this.HasDummyNode( e.Node ) )
        this.LoadDirectoryNodes( e.Node );
}

While the technique presented above might not be the most efficient way to search a TreeView, it is certainly one of the simplest. Using the TreeViewWalker simplifies the programming model, and allows for a natural division of the different searching routines into separate methods. Hopefully, this sample demonstrates the flexibility and power of the TreeViewWalker, and sheds some light on how it can be used in more sophisticated scenarios.

Points of Interest

In case you are interested in how the TreeViewWalker works, this method is where all of the heavy lifting is done:

private bool WalkNodes( TreeNode node )
{
    // Fire the ProcessNode event.
    ProcessNodeEventArgs args = 
        ProcessNodeEventArgs.CreateInstance( node );
    this.OnProcessNode( args );

    // Cache the value of ProcessSiblings since 
    // ProcessNodeEventArgs is a singleton.
    bool processSiblings = args.ProcessSiblings;

    if( args.StopProcessing )
    {
        this.stopProcessing = true;
    }
    else if( args.ProcessDescendants )
    {
        foreach( TreeNode childNode in node.Nodes )
            if( ! this.WalkNodes( childNode ) || 
                  this.stopProcessing )
                break;
    }

    return processSiblings;
}

History

• 4^th February, 2006
  • Article created
• 12^th February, 2006
  • Added the ProcessSiblings
• 18^th February, 2006
  • Added the "Background" and "Advanced usage" sections