Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Traversing Hierarchies
// Depth first traversal algorithm.
//
// (credit to Alexander Stepanov in Elements Of Programming)
//
// One of the benefits is that the visitor can implement pre or post traversal algorithms, and combine them in one single piece.
//
// @generic in T, the node value type
func traverse_children_recursively(tree_root: T*, step_visitor: func(step: TraversalStep, node: T*))
{
step_visitor(TraversalStep_PRE, tree_root);
last_child := children_last(tree_root);
child := children_first(tree_root);
while (child != last_child) {
traverse_children_recursively(child, step_visitor);
child = next_child(child);
}
step_visitor(TraversalStep_POST, tree_root);
}
enum TraversalStep
{
TraversalStep_PRE,
TraversalStep_POST,
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.