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

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.