WPF Tree Data Structure

Introduction

.NET contains several types of collections for storing elements - List, LinkedList, Dictionary, etc. A common question that comes up from many developers is, "Where is the Tree collection?" .NET doesn't include a Tree because there are too many variations to consider. However, I think we can create something that works for many hierarchical data structures.

This post is going to cover a lot of topics from generics to WPF to drag drop! You may see where I'm going with this already and you might have the correct assumption. WPF data binding is great for almost any collection - even a TreeView control is trivial to bind to. However, the trouble comes when you actually want to manipulate the data. TreeView doesn't even allow data binding to SelectedItem. So begins the hours of googling and stringing together spaghetti code to get your TreeView control to manipulate your model.

Google no further. This is just about everything you'll need to get your TreeView drag and drop ready.

The Data Structure

Let's consider the desired behavior of a Tree data structure. Here are some obvious things we need to be able to do.

• Recursive tree nodes with children
• Nodes have a reference to parents
• Nodes are re-parented when moved to another node

Here are some less obvious things to consider.

• A node cannot be added to itself as a child
• A node cannot be added to any of it's descendants as a child

Let's jump right into the design. Here is the beginning of the SimpleTree class.

/// <summary>
/// Represents a simple generic tree.
/// </summary>
/// <typeparam name="T">Type of elements in tree</typeparam>
public class SimpleTree<T> where T : SimpleTree<T>
{
    #region Member Variables
        
    // List of children
    private readonly ObservableCollection<T> _children =
      new ObservableCollection<T>();
    #endregion

We use generics a little differently here. We place a constraint on T where T should be a SimpleTree. That means that our elements in our collection should extend SimpleTree. This is usually not a problem since we can create a ViewModel class for our view. Also notice that the children live in an ObservableCollection. We aren't beating around the bush here. We need good data binding support right off the bat.

#region Properties

private SimpleTree<T> _parent;
/// <summary>
/// Gets the parent node.
/// </summary>
public SimpleTree<T> Parent
{
    get { return _parent; }
    private set { _parent = value; }
}

/// <summary>
/// Gets the children for this tree.
/// </summary>
public ReadOnlyObservableCollection<T> Children
{
    get { return new ReadOnlyObservableCollection<T>(_children); }
}
#endregion

We only have two properties Parent and Children. The setter on Parent is private and the Children are readonly. This is because we need to handle the adding and removing of the children explicitly. Now this is where some people might take a different design approach. You could create your own Collection that overrides ObservableCollection and manages the reparenting. This may be better in some cases since some WPF controls, like DataGrid, can instantiate a new ViewModel and add it to your collection for you.

Now let's take a look at our functions. This is where we handle all our Tree logic like reparenting and adding children. We also added some helper methods to find elements in a tree.

#region Functions

/// <summary>
/// Gets a child at the specified index.
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public T this[int i]
{
 get { return _children[i]; }
}

/// <summary>
/// Add a child node to the tree.  Checks to see if self exists
/// in descedants as to prevent circular references.
/// </summary>
/// <param name="node"></param>
public T AddChild(T node)
{
 // check to see if node is self
 if (node == this)
 {
     throw new Exception("Cannot add self to children.");
 }

 // check to see if node is in children
 if (this == node.Parent)
 {
     throw new Exception("Node already exists in children.");
 }

 // check to see if the node is an ancestor
 T parent = (T)this.Parent;
 while (parent != null)
 {
  if (parent == node)
  {
             throw new Exception("Node is an ancestor to this node.");
  }
  parent = (T)parent.Parent;
 }

 if (node.Parent != null)
 {
  node.Parent.RemoveChild(node);
 }
 node.Parent = this;

 _children.Add(node);
 return node;
}

/// <summary>
/// Removes child node from tree.  Sets the parent of the node to null.
/// </summary>
/// <param name="node">Node to remove</param>
/// <returns>True if removed. False if not.</returns>
public bool RemoveChild(T node)
{
 if (_children.Remove(node))
 {
  node.Parent = null;
  return true;
 }
 else
 {
  return false;
 }
}

/// <summary>
/// Traverses all of the tree nodes executing the specified action. Visitor pattern.
/// </summary>
/// <param name="action">Action to execute.</param>
public void Traverse(Action<T> action)
{
 action((T)this);
 foreach (var c in _children)
 {
  c.Traverse(action);
 }
}

/// <summary>
/// Finds a node using the specified predicate.
/// </summary>
/// <param name="predicate">Predictate</param>
/// <returns>First node where predicate is true.</returns>
public T Find(Predicate<T> predicate)
{
 if (predicate((T)this))
 {
  return (T)this;
 }
 foreach (var c in _children)
 {
  var found = c.Find(predicate);
  if (found != null)
  {
   return found;
  }
 }
 return null;
}

/// <summary>
/// Finds the specified node in the descendants.
/// </summary>
/// <param name="tree">Node to search for.</param>
/// <returns>Found node.  Null if not found in descendants.</returns>
public T Find(T tree)
{
 if (tree == this)
 {
  return (T)this;
 }
 foreach (var c in _children)
 {
  var found = c.Find(tree);
  if (found != null)
  {
   return found;
  }
 }
 return null;
}

#endregion

Using

Using the simple tree is as simple as extending SimpleTree. Here is an example of the ubiquitous Person class, which is quite appropriate since people may have children.

public class Person : SimpleTree<Person>
{
    public string Name { get; set; }

    public override string ToString()
    {
        return Name;
    }
}

WPF

Now, as I promised, let's discuss how we can make a Drag and Drop TreeView. I suppose this could be it's own blog post so I won't go into too much detail. I'll just post some code and touch on the main points.

Here is a TreeView in xaml showing how to bind our SimpleTree of Person's.

<TreeView x:Name="_tree"
          ItemsSource="{Binding}"
          AllowDrop="True"
          MouseLeftButtonDown="OnBeginDrag"
          Drop="OnDrop"
          DragEnter="OnDragEnter"
          MouseMove="OnDrag">
    <TreeView.ItemTemplate>
        <HierarchicalDataTemplate ItemsSource="{Binding Children}">
            <TextBlock Text="{Binding Name}"/>
        </HierarchicalDataTemplate>
    </TreeView.ItemTemplate>
</TreeView>

You've probably noticed the Event handlers. Don't get scared! It's OK to have event handlers in WPF. The WPF police aren't going to get you. It does require the view to "know" about the ViewModel. This is where you could create an IPersonViewModel interface or something for extra credit. I've come to realize that at some point complex applications are coupled somewhere so refactor if you have to.

To begin dragging we need to capture the start point. Then when we start dragging we simple check if the left mouse button is down and that we aren't already dragging. Then we check to see if we've moved the minimum drag distance start the drag.

Point _startPoint;
bool _isDragging;
private void OnBeginDrag(object sender, MouseButtonEventArgs e)
{
     _startPoint = e.GetPosition(_tree);
}

private void OnDrag(object sender, MouseEventArgs e)
{
     if (e.LeftButton == MouseButtonState.Pressed && !_isDragging)
     {
        Point position = e.GetPosition(null);
        if (Math.Abs(position.X - _startPoint.X) > SystemParameters.MinimumHorizontalDragDistance ||
            Math.Abs(position.Y - _startPoint.Y) > SystemParameters.MinimumVerticalDragDistance)
        {
            StartDrag(e);
        }
    } 
}

In the StartDrag method is where we start to get intimate with our ViewModel. Notice that it knows about the Person! At least WPF provides excellent support for this by getting the underlying object by calling SelectedItem.

private void StartDrag(MouseEventArgs e)
{
     _isDragging = true;
     Person person = <span style="font-size: 9pt;">e.Data.GetData(e.Data.GetFormats()[0])</span><span style="font-size: 9pt;"> as Person;</span>

     if (person != null)
     {
        DragDropEffects de = DragDrop.DoDragDrop(_tree, person, DragDropEffects.Move);
     }
     _isDragging = false;
}

Here is the DragEnter method to set the effects. This also "helps" with making sure we are dealing with the correct data type.

private void OnDragEnter(object sender, DragEventArgs e)
{
      var person = e.Data.GetData(e.Data.GetFormats()[0]) as Person;
      if (person == null)
      {
          e.Effects = DragDropEffects.None;
      }
}

The DROP! This is where the magic starts to happen. We already have a reference to the dragged object, but we need to get a reference to the target object. Once we have the target, we can call AddChild. Again, it feels like we know a little too much about the ViewModel, but it's OK!

private void OnDrop(object sender, DragEventArgs e)
{
    var person = e.Data.GetData(e.Data.GetFormats()[0]) as Person;

    if (person != null)
    {
        var target = GetItemAtLocation(e.GetPosition(_tree)) as Person;

 if (target != null)
 {
     try
     {
    target.AddChild(person);
     }
     catch
     {
  // failed to reparent child
     }
 }
    }
}

We get the reference to the target object by using current location. This is also where we could check for Above or Below to allow reordering. But we are not doing that here.

private Person GetItemAtLocation
{
    Person foundItem = default(Person);
    HitTestResult hitTestResults = VisualTreeHelper.HitTest(_tree, location);

    if (hitTestResults.VisualHit is FrameworkElement)
    {
        object dataObject = (hitTestResults.VisualHit as
           FrameworkElement).DataContext;

        if (dataObject is Person)
        {
            foundItem = (Person)dataObject;
        }
    }

    return foundItem;
}

Unit Testing

Just to prove that our SimpleTree works, let's add some unit testing.

public class TestPerson : SimpleTree<TestPerson>
{
  public string Name { get; set; }
}


[TestClass]
public class SimpleTree_UnitTest
{
[TestMethod]
public void Can_Create_Tree()
{
 // Arrange
 TestPerson tree = new TestPerson(){ Name = "Root" };

 // Act

 // Assert
 Assert.IsNotNull(tree);
 Assert.AreEqual(0, tree.Children.Count);
}

[TestMethod]
public void Can_Add_Children()
{
 // Arrange
 TestPerson tree = new TestPerson(){ Name = "Root" };

 // Act
 TestPerson child1 = tree.AddChild(new TestPerson(){ Name = "Child 1" });
 TestPerson child2 = tree.AddChild(new TestPerson(){ Name = "child 2" });

 // Assert
 Assert.IsNotNull(tree);
 Assert.AreEqual(2, tree.Children.Count);
 Assert.AreEqual(tree, child1.Parent);
 Assert.AreEqual(tree, child2.Parent);
}


[TestMethod]
public void Can_Find_Child()
{
 // Arrange
 TestPerson tree1 = new TestPerson(){ Name = "Root 1" };
 TestPerson tree2 = new TestPerson(){ Name = "Root 2" };

 // Act
 TestPerson child1 = tree1.AddChild(new TestPerson(){ Name = "Child 1" });
 TestPerson child2 = tree2.AddChild(new TestPerson(){ Name = "child 2" });

 TestPerson found = tree1.Find(x => x.Name.Equals("Child 1"));


 // Assert
 Assert.AreEqual(child1, found);
 Assert.AreEqual(1, tree1.Children.Count);
 Assert.AreEqual(1, tree2.Children.Count);
}

[TestMethod]
public void Can_Move_Child()
{
 // Arrange
 TestPerson tree1 = new TestPerson(){ Name = "Root 1" };
 TestPerson tree2 = new TestPerson(){ Name = "Root 2" };

 // Act
 TestPerson child1 = tree1.AddChild(new TestPerson(){ Name = "child 1" });
 TestPerson child2 = tree2.AddChild(new TestPerson(){ Name = "child 2" });

 tree2.AddChild(child1);

 // Assert
 Assert.AreEqual(tree2, child1.Parent);
 Assert.AreEqual(0, tree1.Children.Count);
 Assert.AreEqual(2, tree2.Children.Count);
}

[TestMethod]
public void Can_Remove_Child()
{
 // Arrange
 TestPerson tree1 = new TestPerson(){ Name = "Root 1" };
 TestPerson tree2 = new TestPerson(){ Name = "Root 2" };

 // Act
 TestPerson child1 = tree1.AddChild(new TestPerson(){ Name = "child 1" });

 tree1.RemoveChild(child1);

 // Assert
 Assert.AreEqual(null, child1.Parent);
 Assert.AreEqual(0, tree1.Children.Count);
}

[TestMethod]
public void Can_Find_Node()
{
 // Arrange
 TestPerson tree1 = new TestPerson() { Name = "Root 1" };

 // Act
 TestPerson child1 = tree1.AddChild(new TestPerson(){ Name = "child 1" });
 TestPerson child2 = tree1.AddChild(new TestPerson(){ Name = "child 2" });

 TestPerson found = tree1.Find(child1);

 // Assert
 Assert.AreEqual(found, child1);
 Assert.AreEqual(tree1, found.Parent);
 Assert.AreEqual(2, tree1.Children.Count);
}

[TestMethod]
public void Cannot_Add_Self()
{
 // Arrange
 TestPerson tree1 = new TestPerson() { Name = "Root 1" };
 TestPerson child1 = tree1.AddChild(new TestPerson(){ Name = "child 1" });

 // Act

 try
 {
  tree1.AddChild(tree1);
  Assert.Fail();
 }
 catch (AssertFailedException ex)
 {
  Assert.Fail("Should thrown an exception.");
 }
 catch (Exception ex)
 {
  // expected this exception
 }

 // Assert
 Assert.AreEqual(1, tree1.Children.Count);
}

[TestMethod]
public void Cannot_Add_Self_Children()
{
 // Arrange
 TestPerson tree1 = new TestPerson() { Name = "Root 1" };
 TestPerson child = tree1.AddChild(new TestPerson() { Name = "child" });
 TestPerson grandchild = child.AddChild(new TestPerson() { Name = "grandchild" });

 // Act

 try
 {
  tree1.AddChild(child);
  Assert.Fail();
 }
 catch (AssertFailedException ex)
 {
  Assert.Fail("Should thrown an exception.");
 }
 catch (Exception ex)
 {
  // expected this exception
 }

 // Assert
 Assert.AreEqual(1, tree1.Children.Count);
}

[TestMethod]
public void Can_Promote_Child()
{
 // Arrange
 TestPerson tree1 = new TestPerson() { Name = "Root 1" };
 TestPerson child = tree1.AddChild(new TestPerson() { Name = "child" });
 TestPerson grandchild = child.AddChild(new TestPerson() { Name = "grandchild" });

 // Act
 try
 {
  tree1.AddChild(grandchild);
 }
 catch (Exception ex)
 {
  Assert.Fail("Should not have thrown an exception promoting child.");
 }

 // Assert
 Assert.AreEqual(2, tree1.Children.Count);
}
}