Ordered Rooted Trees

AUTHORS:

  • Florent Hivert (2010-2011): initial revision
  • Frederic Chapoton (2010): contributed some methods
sage.combinat.ordered_tree.LabelledOrderedTree

Labelled ordered trees.

A labelled ordered tree is an ordered tree with a label attached at each node.

INPUT:

  • children – a list or tuple or more generally any iterable of trees or object convertible to trees
  • label – any Sage object (default: None)

EXAMPLES:

sage: x = LabelledOrderedTree([], label = 3); x
3[]
sage: LabelledOrderedTree([x, x, x], label = 2)
2[3[], 3[], 3[]]
sage: LabelledOrderedTree((x, x, x), label = 2)
2[3[], 3[], 3[]]
sage: LabelledOrderedTree([[],[[], []]], label = 3)
3[None[], None[None[], None[]]]
sage.combinat.ordered_tree.LabelledOrderedTrees

This is a parent stub to serve as a factory class for trees with various label constraints.

EXAMPLES:

sage: LOT = LabelledOrderedTrees(); LOT
Labelled ordered trees
sage: x = LOT([], label = 3); x
3[]
sage: x.parent() is LOT
True
sage: y = LOT([x, x, x], label = 2); y
2[3[], 3[], 3[]]
sage: y.parent() is LOT
True
sage.combinat.ordered_tree.OrderedTree

The class of (ordered rooted) trees.

An ordered tree is constructed from a node, called the root, on which one has grafted a possibly empty list of trees. There is a total order on the children of a node which is given by the order of the elements in the list. Note that there is no empty ordered tree (so the smallest ordered tree consists of just one node).

INPUT:

One can create a tree from any list (or more generally iterable) of trees or objects convertible to a tree. Alternatively a string is also accepted. The syntax is the same as for printing: children are grouped by square brackets.

EXAMPLES:

sage: x = OrderedTree([])
sage: x1 = OrderedTree([x,x])
sage: x2 = OrderedTree([[],[]])
sage: x1 == x2
True
sage: tt1 = OrderedTree([x,x1,x2])
sage: tt2 = OrderedTree([[], [[], []], x2])
sage: tt1 == tt2
True

sage: OrderedTree([]) == OrderedTree()
True
sage.combinat.ordered_tree.OrderedTrees

Factory for ordered trees

INPUT:

  • size – (optional) an integer

OUTPUT:

  • the set of all ordered trees (of the given size if specified)

EXAMPLES:

sage: OrderedTrees()
Ordered trees

sage: OrderedTrees(2)
Ordered trees of size 2

Note

this is a factory class whose constructor returns instances of subclasses.

Note

the fact that OrderedTrees is a class instead of a simple callable is an implementation detail. It could be changed in the future and one should not rely on it.

sage.combinat.ordered_tree.OrderedTrees_all

The set of all ordered trees.

EXAMPLES:

sage: OT = OrderedTrees(); OT
Ordered trees
sage: OT.cardinality()
+Infinity
sage.combinat.ordered_tree.OrderedTrees_size

The enumerated sets of binary trees of a given size

EXAMPLES:

sage: S = OrderedTrees(3); S
Ordered trees of size 3
sage: S.cardinality()
2
sage: S.list()
[[[], []], [[[]]]]