AbstractTrees.jl

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).

API overview

  • print_tree pretty prints an arbitrary tree data structure.
  • Tree is 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).
  • ShadowTree is a tree object that combines two trees of equal structure into a single tree (indexing always produces another ShadowTree, but setindex! with tuples is allowed). Useful for adding annotation nodes to other trees without modifying that tree structure itself.
  • Leaves is an iterator to visit the leaves of a tree in order.
  • PostOrderDFS is 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.
  • PreOrderDFS is same as PostOrderDFS but visits parents before their children.
  • StatelessBFS iterates over a tree level-by-level, but does not keep state (causing this to be $O(n^2)$, but able to handle changing trees).
  • treemap maps each node of a tree to obtain a new tree.
  • treemap! maps each node of a tree in place.

Traits

Examples

The examples folder contains a number of usage examples of varying complexity.