Previous installments

General Data Structures

[ Note : This post feels a little like CS101 - but I felt it necessary to discuss the basic tree concepts before we move on to some of the more specialized trees like search trees.  ]

The GeneralTree<T> class in NGenerics provides a way of defining tree structures in a simple, recursive way. It has a simple, recursive definition :

400: Invalid request

Visually, we can represent it, well, as a tree : 

In contrast to some of the more specialized tree structures (like binary trees and search trees), the GeneralTree enforces no constraints on the structure of the tree - each tree node can have as many children as you have memory, and can be in any order.  What are general trees useful for?  Generally, these data structures are used to imply some relationship between objects without having these relationships encoded in the object itself.  Once we have these relationships set up, we can start traversing the tree in all kinds of interesting ways.

The Visitor Pattern

The visitor pattern provides a way of  separating the acting logic from the actual structure being traversed.  Almost all data structures in NGenerics can accept a visitor instance for traversing the structure, either via the Accept extension method on IEnumerable<T>, or through specialized traversal methods on the data structures themselves.  A visitor needs to implement the IVisitor<T> interface :

400: Invalid request

When traversing a data structure, the Visit member gets called on the visitor with the current instance being visited.  A rather contrived example of a visitor is a SummingVisitor :

400: Invalid request

The HasCompleted property provides a way for the visitor to stop traversing the structure.  This might be useful in visitors that search for specific items, and would like to quit after they've found what they're looking for. Tree Traversals There are two ways of traversing trees - breadth-first traversal, and depth-first traversal.   Both of these are implemented in NGenerics utilizing the visitor pattern.  Breadth-first traversal visits each node on a level before moving on to the next level.  In our example tree above, breadth first traversal would result in the following order of visitations :  

Depth-first traversal, on the other hand, will result nodes being visited from top to bottom in the tree.   There are three types of depth-first traversal routines :

  • Pre-order traversals : the root node is visited, then the child nodes (left to right).
  • In-order traversals: only makes sense in binary trees - the left node will be visited, then the root node, and then the right node.
  • Post-order traversals: the child nodes will be visited before the root node (left to right).

For these traversal types, NGenerics defines the InOrderVisitor, PostOrderVisitor, and PreOrderVisitor classes that custom visitors can inherit from.  Traversing our sample tree in pre-order fashion will be performed as such :

An ubiquitous use for pre-order traversals is in the evaluation of expression trees. On the other hand, a post-order visitor will visit the tree in the following order :

More GeneralTree<T> Goodness

Apart from having ICollection<T> semantics and enabling traversals of the tree structure, the GeneralTree class offers several other useful methods :

  • Ancestors : Retrieve all ancestors of the current node as a path through the tree.
  • Descendants : Retrieve all descendants of the current node as a path through the tree.
  • Each node keeps track of both the parent and the childnodes, and enables easy detaching and and re-attaching of nodes to any parent node.
  • TreeNodes can be sorted on a child node level (i.e. all children of a specific node), or recursively through the tree.