Traversal
By Ryan Sandor Richards
Introduction
The tree traversal is a fundamental problem in computer science and it occurs in many contexts (e.g. compilers). This library aims to make them easier to write and read in JavaScript.
Usage
Traversal works by holding the computational state of a tree traversal in the form of an JavaScript class. The library exposes a single factory method, traversal()
, that creates a new instance and allows you to override its default behaviors.
Here's an example of how it might be used:
// 1. Require the libraryvar traversal = ; // 2. Format a tree using nest objectsvar myTree = name: 'root' left: name: 'left child' right: name: 'right child' ; // 3. Build a traversal that prints out node names and// recursively follows the `left` and `right` properties.var logger = ; // 4. Execute the traversal by calling `walk`logger;
This particular traversal would output the following:
root
left child
right child
Documentation
traversal( [ helpers ] )
Instantiates a new tree traversal object.
Parameters
- Array
helpers
(optional) - List of node properties for which to make helper methods.
Example
var myTraversal = type'root' { console; } ;
.walk(tree)
Perform the traversal on a given tree.
Parameters
- Object tree - Root node of the tree to traverse.
Example
// Setup the traversalvar total = 0;var myTraversal = ; // Perform the tree traversal, or "walk" a tree...myTraversal; // Outputs 60console;
.visit(fn)
Define the default visit function, which performs some operation on a node when it is visited during the traversal.
Parameters
- function
fn(node, recur, depth)
- Function to apply when visiting a node during a traversal.node
is the node being visited,recur
is a method that can be called to recur on child nodes, anddepth
is the depth in the tree at the given node.
Examples
// Traverse a binary tree and sum the value of each nodevar sum = ;
// Traverse a tree and log each node using whitespace to denote depth ;
.preorder(propertyName, ...)
Adds node property names to the traversal that should be recursively traversed after the node has been visited (read more about preorder traversals).
Parameters
- string... propertyName - One or more property names that should be automatically recurred upon when performing the traversal.
Examples
// Automatically traverse the left and right properties of each node. ;
// You can even traverse arrays!
.postorder(properName, ...)
Adds node property names to the traversal that should be recursively traversed before the node has been visited (read more about postorder traversals).
Parameters
- string... propertyName - One or more property names that should be automatically recurred upon when performing the traversal.
Examples
// Postorder visit the left and right properties of each node ;
// Postorder traverse an array of nodes
.property(propertyName, propertyValue, fn)
Defines a new visitor that only applies to nodes that have a given property set
to the given value. If node
is the node currently being visited in the
traversal, then this will only apply if node[propertyName] === propertyValue
.
Parameters
- String
propertyName
- Name of the property for which to define the custom visitor function. - mixed
properyValue
- Value of the propery for which to apply the custom visitor function. - function fn - The visitor function to apply when
node[propertyName] === propertyValue
Example
// Traversal that treats node.type === 'root' as a special case ;
.addPropertyHelper(propertyName)
Adds a new method to the traversal that makes it easier to define specific
property visitors (as you would with .property
).
Parameters
- String
propertyName
- Name of the property for which to make the helper. Cannot be a reserved or already taken name on the traversal (e.g.visit
).
Example
// Create a type property helper for a traversal // Use it to create special visit functions type'root' { console } type'number' { console; };
recur.each(nodes)
Recurs further in the traversal for each node in a given array.
Parameters
- Array nodes - Array of nodes to traverse.
Example
;
recur.stop
Stops automatic recursion defined by .preorder
or .postorder
.
Example
type'trinary' { recur; recur; };
recur.setReduce(fn)
Sets the reduce function for .each
.
Parameters
- function fn - Function to use during reduce after
.each
.
Example
// Sets value to 10var value = ;
recur.setReduceInitial(value)
Sets the initial value for the reduce used during .each
Parameters
- mixed value - Initial value for the reduce.
License
MIT