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 treeslabel
– 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() [[[], []], [[[]]]]