This package provides several utilities for working with tree-like data structures. Most importantly, it defines the
children method that any package that contains such a data structure may import and extend in order to take advantage of any generic tree algorithm in this package (or other packages compatible with this package).
print_treepretty prints an arbitrary tree data structure.
Treeis a simple wrapper around an arbitrary object that allows tree-indexing into that object (i.e. indexing with collections of indices specifying the child index at every level).
ShadowTreeis a tree object that combines two trees of equal structure into a single tree (indexing always produces another
setindex!with tuples is allowed). Useful for adding annotation nodes to other trees without modifying that tree structure itself.
Leavesis an iterator to visit the leaves of a tree in order.
PostOrderDFSis a depth-first search (i.e. will visit node's children before it's lexicographically following siblings) that guarantees to visit children before their parents.
PreOrderDFSis same as
PostOrderDFSbut visits parents before their children.
StatelessBFSiterates over a tree level-by-level, but does not keep state (causing this to be $O(n^2)$, but able to handle changing trees).
treemapmaps each node of a tree to obtain a new tree.
treemap!maps each node of a tree in place.
AbstractTrees.nodetype(tree)can be defined to make iteration inferable.
AbstractTrees.ParentLinkscan be defined to return
AbstractTrees.StoredParents()if a tree type stores explicit links to a parent;
AbstractTrees.SiblingLinks, when set to
AbstractTrees.StoredSiblings(), serves the same role for siblings. See their docstrings for more information.
The examples folder contains a number of usage examples of varying complexity.