configurable-tree-traversal

Can do depth-first traversals like on this picture for abstract trees.

(source: https://en.wikipedia.org/wiki/Tree_traversal)

Examples

To run examples you'll need to have node and you'll need to run npm install.

tree-from-image-example.ts

npm run tsfile examples/tree-from-image-example.ts

1const treeData =
2  {
3    $d: 'F', $c: [
4      {
5        $d: 'B', $c: [
6          { $d: 'A', $c: [] },
7          {
8            $d: 'D', $c: [
9              { $d: 'C', $c: [] },
10              { $d: 'E', $c: [] }]
11          }]
12      },
13      {
14        $d: 'G', $c: [
15          null,
16          {
17            $d: 'I', $c: [
18              { $d: 'H', $c: [] }]
19          }]
20      }]
21  };
22
23const traversal = new DepthFirstTraversal({
24  traversableTree: {
25    makeRoot: () => treeData,
26    makeVertex: (childHint: any) => childHint
27  }
28});
29traversal.addVisitorFor(DepthFirstTraversalOrder.PRE_ORDER, (vertex) => reportVisit(DepthFirstTraversalOrder.PRE_ORDER, vertex.getData()));
30traversal.addVisitorFor(DepthFirstTraversalOrder.IN_ORDER, (vertex) => reportVisit(DepthFirstTraversalOrder.IN_ORDER, vertex.getData()));
31traversal.addVisitorFor(DepthFirstTraversalOrder.POST_ORDER, (vertex) => reportVisit(DepthFirstTraversalOrder.POST_ORDER, vertex.getData()));
32traversal.makeRunner().run();

Stdout

traversable-object-example.ts

npm run tsfile examples/traversable-object-example.ts

traversable-object-example-disable-subtree-traversal.ts

npm run tsfile examples/traversable-object-example-disable-subtree-traversal.ts

Same as traversable-object-example.ts, but uses DISABLE_SUBTREE_TRAVERSAL command on vertex B.

traversable-object-example-rewrite-vertex-hints.ts

npm run tsfile examples/traversable-object-example-rewrite-vertex-hints.ts

Same as traversable-object-example.ts, but uses REWRITE_VERTEX_HINTS_ON_PRE_ORDER command on vertex E.

traversable-object-iterable-example.ts

npm run tsfile examples/traversable-object-iterable-example.ts

rewrite-object-example.ts

npm run tsfile examples/rewrite-object-example.ts

Project Status

Not tested beyond examples given and never yet applied to real-life problems.

If for some reason you want to use this as a dependency, please use fixed version (remove ^ from version of configurable-tree-traversal in package.json)

TODO

1. Breadth-first
2. Add self-reference test
3. --
4. Async traversal
5. Implementation for FS (with a way to keep fs and tree in sync)
6. Unit tests
7. Freeze data at some point? make trees/vertices immutable?
8. Benchmarks
9. Breadth-first traversal