Previous instalments
General Data Structures
[ Note : This post feels a little like Computer Science 101 - 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 :
public class GeneralTree
{
T nodeData;
List childNodes;
}
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 have no constraints on the number of children or order of those child nodes. General trees are useful for expressing 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 provides a way of separating the acting logic from the traversal logic of the structure. 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 adhere to the IVisitor<T> interface :
public interface IVisitor
{
bool HasCompleted { get; }
void Visit(T obj);
}
When traversing a data structure the Visit member gets called on the visitor with each visited instance. A rather contrived example of a visitor is a SummingVisitor:
public class SumVisitor : IVisitor
{
public void Visit(int obj)
{
Sum += obj;
}
public bool HasCompleted
{
get { return false; }
}
public int Sum
{
get; private set;
}
}
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 these implementations in NGenerics make use of 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, will result in visiting nodes from top to bottom in the tree. There are three types of depth-first traversal routines that visit the nodes in different orders:
- Pre-order traversals: root -> left child -> right child
- In-order traversals: used in binary trees - left child -> root node -> right child.
- Post-order traversals: left child -> right child -> root
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 result in the following order of visitation:
An ubiquitous use for pre-order traversals is in the evaluation of expression trees.
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 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 child nodes and enables easy detaching and re-attaching of nodes to any parent node.
- We can sort TreeNodes on a child level (i.e. all children of a specific node) or recursively through the tree.
Photo by Bart Zimny on Unsplash