This project provides a:
- .Net Standard Library (1.4, 1.6, 2.0) or a
- .Net framework 4.0 Library
with Generic methods to traverse k-ary trees in different orders (Post-Order, Pre-Order, Level-Order) of traversal. This implementation includes scalable algorithms that return IEnumerable<T> to make parsing large tree structures a piece of cake, as well, as Generic Exception handling to ensure that traversal algorithms complete despite unexpected errors on some nodes.
Review demo projects:
- in this solution,
- WPF FilterTreeView sample application, and read
- Advanced WPF TreeViews Part 3 of n
- Advanced WPF TreeViews Part 4 of n to learn more details.
Implementing something as complicated as a Post-Order traversal algorithm requires just:
- a project reference,
- a LINQ statement to find each set of children in the tree,
- and a simple for each loop to implement the operation on each tree node:
Console.WriteLine("(Depth First) PostOrder Tree Traversal V3");
items = TreeLib.Depthfirst.Traverse.PostOrder(root, i => i.Children);
foreach (var item in items)
{
Console.WriteLine(item.GetPath());
}This pattern leads to a clear-cut separation of:
- the traversal algorithm and
- the operations performed on each tree node (e.g.:
Console.WriteLine(item.GetPath());).
The project in this repository contains a demo console project to demo its usage in more detail.
See TreeLib.BreadthFirst.Traverse.LevelOrder implementation for:
- Trees with 1 root node (expects 1 <T> root item as parameter)
- Trees with multiple root nodes (expects an IEnumerable<T> root item as parameter)
- Generic Level-Order function and DemoDirectoryTreeTraversal
See TreeLib.BreadthFirst.Traverse.PreOrder implementation for:
- Trees with 1 root node (expects 1 <T> root item as parameter)
- Trees with multiple root nodes (expects IEnumerable<T> root as parameter)
- Generic Pre-Order function and DemoDirectoryTreeTraversal
See TreeLib.BreadthFirst.Traverse.Postorder implementation for:
- Trees with 1 root node (expects 1 <T> root item as parameter)
- Trees with multiple root nodes (expects IEnumerable<T> root item as parameter)
- Generic Post-Order function and DemoDirectoryTreeTraversal
-
Read about Generic Tree and Linked List Traversal in C# to understand the usefulness of Generic traversal methods.
-
Watch the Binary tree traversal: Preorder, Inorder, Postorder video to better understand what is what (and why these Traversal Order Names make some sense):
-
Look into data structure books online Introduction to Trees, Binary Search Trees or offline Algorithms by Robert Sedgewick and Kevin Wayne, if you still need more background on tree structures