Std.Tree
Tree is a particular subtype of a graph for which each node has only one predecessor, and there is only one path between tree root and any other node. Here is an example of a tree:
(A) | +-------+-------+ | | | (B) (C) (D) | +-------+-------+ | | | (E) (F) (G) | (H)
type 'a t = 'a tree
val children : 'a t -> 'a -> 'a Regular.Std.seq
children tree x
returns all immediate successors of node x
. For example, children of node A
is a sequence of B,C,D
. But node B
doesn't have any children at all.
val parent : 'a t -> 'a -> 'a option
parent tree n
returns an immediate parent of a given node. Returns None
only if n
is a tree root. For example, parent of F
is C
. And A
doesn't have a parent.
val ancestors : 'a t -> 'a -> 'a Regular.Std.seq
ancestors tree n
returns a sequence of all ancestors of node n
. An ancestor of a node is either a parent or an ancestor of the parent. For example, ancestors of G
are C
and D
. The root node is the only one, that has an empty set of ancestors.
val descendants : 'a t -> 'a -> 'a Regular.Std.seq
descendants tree n
returns a set of all descendants of a given node n
. Descendant is either a child or a descendant of a child. For example, all nodes in the example tree
(except the roots itself) are descendants of the root A
. The descendants of C
are E,F,G,H
.
val is_child_of : 'a t -> parent:'a -> 'a -> bool
is_child_of tree parent child
returns true
if child is one of children tree root
val is_ancestor_of : 'a t -> child:'a -> 'a -> bool
is_ancestor_of tree child x
returns true, if x
is one of the ancestors of a child
node.
val is_descendant_of : 'a t -> parent:'a -> 'a -> bool
is_descendant_of ~parent tree x
is true
for all x
that are descendants of a parent
node.
val to_sequence : 'a t -> 'a Regular.Std.seq
to_sequence tree
enumerates nodes of a tree
in an unspecified order.
val pp : 'a Regular.Std.printer -> 'a t Regular.Std.printer
pp pp_elt
creates a pretty-printer for a node, based on element's pretty-printer pp_elt
. The tree is printed in a dot format, for the ease of visualization. Example:
let pp_int_tree = Tree.pp Int.pp
Note: For all instatiations of Graph
interface in the Graphlib
library printable versions of tree
, partition
, group
etc are provided. For example, for Graphlib.Int.Bool
graph the printable version of a tree
is available under Graphlib.Int.Tree
. All instantiated pretty-printers are automatically installed once the library is loaded into the toplevel.