API

Iterator to visit the leaves of a tree, e.g. for the tree

Any[1,Any[2,3]]
├─ 1
└─ Any[2,3]
   ├─ 2
   └─ 3

we will get [1,2,3].

Iterator to visit the nodes of a tree, guaranteeing that children will be visited before their parents.

e.g. for the tree

Any[1,Any[2,3]]
├─ 1
└─ Any[2,3]
   ├─ 2
   └─ 3

we will get [1, 2, 3, [2, 3], [1, [2, 3]]].

Iterator to visit the nodes of a tree, guaranteeing that parents will be visited before their children.

Optionally takes a filter function that determines whether the iterator should continue iterating over a node's children (if it has any) or should consider that node a leaf.

e.g. for the tree

Any[Any[1,2],Any[3,4]]
├─ Any[1,2]
|  ├─ 1
|  └─ 2
└─ Any[3,4]
   ├─ 3
   └─ 4

we will get [[[1, 2], [3, 4]], [1, 2], 1, 2, [3, 4], 3, 4].

Invalidation

Modifying the underlying tree while iterating over it, is allowed, however, if parents and sibling links are not explicitly stored, the identity of any parent of the last obtained node does not change (i.e. mutation is allowed, replacing nodes is not).

Iterator to visit the nodes of a tree, all nodes of a level will be visited before their children

e.g. for the tree

Any[1,Any[2,3]]
├─ 1
└─ Any[2,3]
   ├─ 2
   └─ 3

we will get [[1, [2,3]], 1, [2, 3], 2, 3].

WARNING: This is $O(n^2)$, only use this if you know you need it, as opposed to a more standard statefull approach.

Indicates that this tree stores parent links explicitly. The implementation is responsible for defining the parentind function to expose this information.

Indicates that this tree stores sibling links explicitly, or can compute them quickly (e.g. because the tree has a (small) fixed branching ratio, so the current index of a node can be determined by quick linear search). The implementation is responsible for defining the relative_state function to expose this information.

TreeCharSet

Set of characters (or strings) used to pretty-print tree branches in print_tree.

children(x)

Return the immediate children of node x. You should specialize this method for custom tree structures. It should return an iterable object for which an appropriate implementation of Base.pairs is available.

The default behavior is to assume that if an object is iterable, iterating over it gives its children. If an object is not iterable, assume it does not have children.

Example

struct MyNode{T}
    data::T
    children::Vector{MyNode{T}}
end
AbstractTrees.children(node::MyNode) = node.children

nodetype(tree)

A trait function, defined on the tree object, specifying the types of the nodes. The default is Any. When applicable, define this trait to make iteration inferrable.

Example

struct IntTree
    num::Int
    children::Vector{IntTree}
end
AbstractTrees.children(itree::IntTree) = itree.children
AbstractTrees.nodetype(::IntTree) = IntTree

This suffices to make iteration over, e.g., Leaves(itree::IntTree) inferrable.

print_tree(tree; kwargs...)
print_tree(io::IO, tree; kwargs...)
print_tree(f::Function, io::IO, tree; kwargs...)

Print a text representation of tree to the given io object.

Arguments

• f::Function - custom implementation of printnode to use. Should have the signature f(io::IO, node).
• maxdepth::Integer = 5 - truncate printing of subtrees at this depth.
• indicate_truncation::Bool = true - print a vertical ellipsis character beneath truncated nodes.
• charset::TreeCharSet - TreeCharSet to use to print branches.

Examples

julia> print_tree(stdout, Dict("a"=>"b","b"=>['c','d']))
Dict{String,Any}("b"=>['c','d'],"a"=>"b")
├─ b
│  ├─ c
│  └─ d
└─ a
   └─ b

julia> print_tree(stdout, '0'=>'1'=>'2'=>'3', 2)
'0'
└─ '1'
    └─ '2'
        ⋮

julia> print_tree(stdout, Dict("a"=>"b","b"=>['c','d']);
        charset = TreeCharSet('+','\\','|',"--","⋮"))
Dict{String,Any}("b"=>['c','d'],"a"=>"b")
+-- b
|   +-- c
|   \-- d
\-- a
   \-- b

printnode(io::IO, node)

Print a single node. The default is to show a compact representation of node. Override this if you want nodes printed in a custom way in print_tree, or if you want your print function to print part of the tree by default.

Examples

struct MyNode{T}
    data::T
    children::Vector{MyNode{T}}
end
AbstractTrees.printnode(io::IO, node::MyNode) = print(io, "MyNode($(node.data))")

Default charset argument used by print_tree.

Charset using only ASCII characters.