The purpose of this class is to help implement trees with a specific structure on the children of each node. For instance, one could want to define a tree in which each node sees its children as linearly (see the Ordered Trees module) or cyclically ordered.
Tree structures
Conceptually, one can define a tree structure from any object that can contain others. Indeed, a list can contain lists which contain lists which contain lists, and thus define a tree ... The same can be done with sets, or any kind of iterable objects.
While any iterable is sufficient to encode trees, it can prove useful to have other methods available like isomorphism tests (see next section), conversions to DiGraphs objects (see as_digraph()) or computation of the number of automorphisms constrained by the structure on children. Providing such methods is the whole purpose of the AbstractTree class.
As a result, the AbstractTree class is not meant to be instantiated, but extended. It is expected that classes extending this one may also inherit from classes representing iterables, for instance ClonableArray or ClonableList
Constrained Trees
The tree built from a specific container will reflect the properties of the container. Indeed, if A is an iterable class whose elements are linearly ordered, a class B extending both of AbstractTree and A will be such that the children of a node will be linearly ordered. If A behaves like a set (i.e. if there is no order on the elements it contains), then two trees will be considered as equal if one can be obtained from the other through permutations between the children of a same node (see next section).
Paths and ID
It is expected that each element of a set of children should be identified by its index in the container. This way, any node of the tree can be identified by a word describing a path from the root node.
Canonical labellings
Equality between instances of classes extending both AbstractTree and A is entirely defined by the equality defined on the elements of A. A canonical labelling of such a tree, however, should be such that two trees a and b satisfying a == b have the same canonical labellings. On the other hand, the canonical labellings of trees a and b satisfying a != b are expected to be different.
For this reason, the values returned by the canonical_labelling method heavily depend on the data structure used for a node’s children and should be overridden by most of the classes extending AbstractTree if it is incoherent with the data structure.
Authors
Bases: sage.combinat.abstract_tree.AbstractTree
Abstract Clonable Tree.
An abstract class for trees with clone protocol (see list_clone). It is expected that classes extending this one may also inherit from classes like ClonableArray or ClonableList depending whether one wants to build trees where adding a child is allowed.
Note
Due to the limitation of Cython inheritance, one cannot inherit here from ClonableElement, because it would prevent us from later inheriting from ClonableArray or ClonableList.
How should this class be extended ?
A class extending AbstractClonableTree should satisfy the following assumptions:
See also the assumptions in AbstractTree.
Check that self is a correct tree.
This method does nothing. It is implemented here because many extensions of AbstractClonableTree also extend sage.structure.list_clone.ClonableElement, which requires it.
It should be overridden in subclasses in order to check that the characterizing property of the respective kind of tree holds (eg: two children for binary trees).
EXAMPLES:
sage: OrderedTree([[],[[]]]).check()
sage: BinaryTree([[],[[],[]]]).check()
Bases: sage.combinat.abstract_tree.AbstractLabelledTree, sage.combinat.abstract_tree.AbstractClonableTree
Abstract Labelled Clonable Tree
This class takes care of modification for the label by the clone protocol.
Note
Due to the limitation of Cython inheritance, one cannot inherit here from ClonableArray, because it would prevent us to inherit later from ClonableList.
Applies the function \(f\) to the labels of self
This method returns a copy of self on which the function \(f\) has been applied on all labels (a label \(x\) is replaced by \(f(x)\)).
EXAMPLES:
sage: LT = LabelledOrderedTree
sage: t = LT([LT([],label=1),LT([],label=7)],label=3); t
3[1[], 7[]]
sage: t.map_labels(lambda z:z+1)
4[2[], 8[]]
sage: LBT = LabelledBinaryTree
sage: bt = LBT([LBT([],label=1),LBT([],label=4)],label=2); bt
2[1[., .], 4[., .]]
sage: bt.map_labels(lambda z:z+1)
3[2[., .], 5[., .]]
Changes the label of subtree indexed by path to label
INPUT:
index in the tree)
label – any sage object
OUPUT: Nothing, self is modified in place
Note
self must be in a mutable state. See sage.structure.list_clone for more details about mutability.
EXAMPLES:
sage: t = LabelledOrderedTree([[],[[],[]]])
sage: t.set_label((0,), 4)
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
sage: with t.clone() as t:
....: t.set_label((0,), 4)
sage: t
None[4[], None[None[], None[]]]
sage: with t.clone() as t:
....: t.set_label((1,0), label = 42)
sage: t
None[4[], None[42[], None[]]]
Todo
Do we want to implement the following syntactic sugar:
with t.clone() as tt:
tt.labels[1,2] = 3 ?
Sets the label of the root of self
INPUT: label – any Sage object
OUPUT: None, self is modified in place
Note
self must be in a mutable state. See sage.structure.list_clone for more details about mutability.
EXAMPLES:
sage: t = LabelledOrderedTree([[],[[],[]]])
sage: t.set_root_label(3)
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
sage: with t.clone() as t:
....: t.set_root_label(3)
sage: t.label()
3
sage: t
3[None[], None[None[], None[]]]
This also works for binary trees:
sage: bt = LabelledBinaryTree([[],[]])
sage: bt.set_root_label(3)
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
sage: with bt.clone() as bt:
....: bt.set_root_label(3)
sage: bt.label()
3
sage: bt
3[None[., .], None[., .]]
TESTS:
sage: with t.clone() as t:
....: t[0] = LabelledOrderedTree(t[0], label = 4)
sage: t
3[4[], None[None[], None[]]]
sage: with t.clone() as t:
....: t[1,0] = LabelledOrderedTree(t[1,0], label = 42)
sage: t
3[4[], None[42[], None[]]]
Bases: sage.combinat.abstract_tree.AbstractTree
Abstract Labelled Tree.
Typically a class for labelled trees is contructed by inheriting from a class for unlabelled trees and AbstractLabelledTree.
How should this class be extended ?
A class extending AbstractLabelledTree should respect the following assumptions:
See also the assumptions in AbstractTree.
See also
Returns a directed graph version of self.
Warning
At this time, the output makes sense only if self is a labelled binary tree with no repeated labels and no None labels.
EXAMPLES:
sage: LT = LabelledOrderedTrees()
sage: t1 = LT([LT([],label=6),LT([],label=1)],label=9)
sage: t1.as_digraph()
Digraph on 3 vertices
sage: t = BinaryTree([[None, None],[[],None]]);
sage: lt = t.canonical_labelling()
sage: lt.as_digraph()
Digraph on 4 vertices
Return the label of self.
INPUT:
in the tree)
OUTPUT: the label of the subtree indexed by path
EXAMPLES:
sage: t = LabelledOrderedTree([[],[]], label = 3)
sage: t.label()
3
sage: t[0].label()
sage: t = LabelledOrderedTree([LabelledOrderedTree([], 5),[]], label = 3)
sage: t.label()
3
sage: t[0].label()
5
sage: t[1].label()
sage: t.label([0])
5
Return the list of labels of self.
EXAMPLES:
sage: LT = LabelledOrderedTree
sage: t = LT([LT([],label='b'),LT([],label='c')],label='a')
sage: t.labels()
['a', 'b', 'c']
sage: LBT = LabelledBinaryTree
sage: LBT([LBT([],label=1),LBT([],label=4)],label=2).labels()
[2, 1, 4]
Return the list of labels of the leaves of self.
In case of a labelled binary tree, these “leaves” are not actually the leaves of the binary trees, but the nodes whose both children are leaves!
EXAMPLES:
sage: LT = LabelledOrderedTree
sage: t = LT([LT([],label='b'),LT([],label='c')],label='a')
sage: t.leaf_labels()
['b', 'c']
sage: LBT = LabelledBinaryTree
sage: bt = LBT([LBT([],label='b'),LBT([],label='c')],label='a')
sage: bt.leaf_labels()
['b', 'c']
sage: LBT([], label='1').leaf_labels()
['1']
sage: LBT(None).leaf_labels()
[]
Returns the unlabelled tree associated to self
EXAMPLES:
sage: t = LabelledOrderedTree([[],[[]]], label = 25).shape(); t
[[], [[]]]
sage: LabelledBinaryTree([[],[[],[]]], label = 25).shape()
[[., .], [[., .], [., .]]]
TESTS:
sage: t.parent()
Ordered trees
sage: type(t)
<class 'sage.combinat.ordered_tree.OrderedTrees_all_with_category.element_class'>
Bases: object
Abstract Tree.
There is no data structure defined here, as this class is meant to be extended, not instantiated.
How should this class be extended?
A class extending AbstractTree should respect several assumptions:
TESTS:
sage: TestSuite(OrderedTree()).run()
sage: TestSuite(BinaryTree()).run()
Run the breadth-first post-order traversal algorithm and subject every node encountered to some procedure action. The algorithm is:
queue <- [ root ];
while the queue is not empty:
node <- pop( queue );
manipulate the node;
prepend to the queue the list of all subtrees of
the node (from the rightmost to the leftmost).
INPUT:
OUTPUT:
None. (This is not an iterator.)
EXAMPLES:
For example, on the following binary tree \(b\):
| ___3____ |
| / \ |
| 1 _7_ |
| \ / \ |
| 2 5 8 |
| / \ |
| 4 6 |
the breadth-first order traversal algorithm explores \(b\) in the following order of nodes: \(3,1,7,2,5,8,4,6\).
TESTS:
sage: b = BinaryTree([[None,[]],[[[],[]],[]]]).canonical_labelling()
sage: l = []
sage: b.breadth_first_order_traversal(lambda node: l.append(node.label()))
sage: l
[3, 1, 7, 2, 5, 8, 4, 6]
sage: t = OrderedTree([[[[],[]]],[[]],[[],[]]]).canonical_labelling()
sage: t
1[2[3[4[], 5[]]], 6[7[]], 8[9[], 10[]]]
sage: l = []
sage: t.breadth_first_order_traversal(lambda node: l.append(node.label()))
sage: l
[1, 2, 6, 8, 3, 7, 9, 10, 4, 5]
sage: l = []
sage: BinaryTree().canonical_labelling().\
....: breadth_first_order_traversal(
....: lambda node: l.append(node.label()))
sage: l
[]
sage: OrderedTree([]).canonical_labelling().\
....: breadth_first_order_traversal(
....: lambda node: l.append(node.label()))
sage: l
[1]
Returns a labelled version of self.
The actual canonical labelling is currently unspecified. However, it is guaranteed to have labels in \(1...n\) where \(n\) is the number of nodes of the tree. Moreover, two (unlabelled) trees compare as equal if and only if their canonical labelled trees compare as equal.
EXAMPLES:
sage: t = OrderedTree([[], [[], [[], []], [[], []]], [[], []]])
sage: t.canonical_labelling()
1[2[], 3[4[], 5[6[], 7[]], 8[9[], 10[]]], 11[12[], 13[]]]
sage: BinaryTree([]).canonical_labelling()
1[., .]
sage: BinaryTree([[],[[],[]]]).canonical_labelling()
2[1[., .], 4[3[., .], 5[., .]]]
TESTS:
sage: BinaryTree().canonical_labelling()
.
The depth of self.
EXAMPLES:
sage: OrderedTree().depth()
1
sage: OrderedTree([]).depth()
1
sage: OrderedTree([[],[]]).depth()
2
sage: OrderedTree([[],[[]]]).depth()
3
sage: OrderedTree([[], [[], [[], []], [[], []]], [[], []]]).depth()
4
sage: BinaryTree().depth()
0
sage: BinaryTree([[],[[],[]]]).depth()
3
Run the depth-first post-order traversal algorithm (iterative implementation) and subject every node encountered to some procedure action. The algorithm is:
explore each subtree (by the algorithm) from the
leftmost one to the rightmost one;
then manipulate the root with function `action` (in the
case of a binary tree, only if the root is not a leaf).
INPUT:
OUTPUT:
None. (This is not an iterator.)
See also
TESTS:
sage: l = []
sage: b = BinaryTree([[None,[]],[[[],[]],[]]]).canonical_labelling()
sage: b
3[1[., 2[., .]], 7[5[4[., .], 6[., .]], 8[., .]]]
sage: b.iterative_post_order_traversal(lambda node: l.append(node.label()))
sage: l
[2, 1, 4, 6, 5, 8, 7, 3]
sage: t = OrderedTree([[[[],[]]],[[]],[[],[]]]).canonical_labelling()
sage: t
1[2[3[4[], 5[]]], 6[7[]], 8[9[], 10[]]]
sage: l = []
sage: t.iterative_post_order_traversal(lambda node: l.append(node.label()))
sage: l
[4, 5, 3, 2, 7, 6, 9, 10, 8, 1]
sage: l = []
sage: BinaryTree().canonical_labelling().\
....: iterative_post_order_traversal(
....: lambda node: l.append(node.label()))
sage: l
[]
sage: OrderedTree([]).canonical_labelling().\
....: iterative_post_order_traversal(
....: lambda node: l.append(node.label()))
sage: l
[1]
The following test checks that things do not go wrong if some among the descendants of the tree are equal or even identical:
sage: u = BinaryTree(None)
sage: v = BinaryTree([u, u])
sage: w = BinaryTree([v, v])
sage: t = BinaryTree([w, w])
sage: t.node_number()
7
sage: l = []
sage: t.iterative_post_order_traversal(lambda node: l.append(1))
sage: len(l)
7
Run the depth-first pre-order traversal algorithm (iterative implementation) and subject every node encountered to some procedure action. The algorithm is:
manipulate the root with function `action` (in the case
of a binary tree, only if the root is not a leaf);
then explore each subtree (by the algorithm) from the
leftmost one to the rightmost one.
INPUT:
OUTPUT:
None. (This is not an iterator.)
TESTS:
sage: l = []
sage: b = BinaryTree([[None,[]],[[[],[]],[]]]).canonical_labelling()
sage: b
3[1[., 2[., .]], 7[5[4[., .], 6[., .]], 8[., .]]]
sage: b.iterative_pre_order_traversal(lambda node: l.append(node.label()))
sage: l
[3, 1, 2, 7, 5, 4, 6, 8]
sage: t = OrderedTree([[[[],[]]],[[]],[[],[]]]).canonical_labelling()
sage: t
1[2[3[4[], 5[]]], 6[7[]], 8[9[], 10[]]]
sage: l = []
sage: t.iterative_pre_order_traversal(lambda node: l.append(node.label()))
sage: l
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
sage: l = []
sage: BinaryTree().canonical_labelling().\
....: pre_order_traversal(lambda node: l.append(node.label()))
sage: l
[]
sage: OrderedTree([]).canonical_labelling().\
....: iterative_pre_order_traversal(lambda node: l.append(node.label()))
sage: l
[1]
The following test checks that things do not go wrong if some among the descendants of the tree are equal or even identical:
sage: u = BinaryTree(None)
sage: v = BinaryTree([u, u])
sage: w = BinaryTree([v, v])
sage: t = BinaryTree([w, w])
sage: t.node_number()
7
sage: l = []
sage: t.iterative_pre_order_traversal(lambda node: l.append(1))
sage: len(l)
7
The number of nodes of self.
EXAMPLES:
sage: OrderedTree().node_number()
1
sage: OrderedTree([]).node_number()
1
sage: OrderedTree([[],[]]).node_number()
3
sage: OrderedTree([[],[[]]]).node_number()
4
sage: OrderedTree([[], [[], [[], []], [[], []]], [[], []]]).node_number()
13
EXAMPLES:
sage: BinaryTree(None).node_number()
0
sage: BinaryTree([]).node_number()
1
sage: BinaryTree([[], None]).node_number()
2
sage: BinaryTree([[None, [[], []]], None]).node_number()
5
Return a generator for all paths to nodes of self.
OUTPUT:
This method returns a list of sequences of integers. Each of these sequences represents a path from the root node to some node. For instance, \((1, 3, 2, 5, 0, 3)\) represents the node obtained by choosing the 1st child of the root node (in the ordering returned by iter), then the 3rd child of its child, then the 2nd child of the latter, etc. (where the labelling of the children is zero-based).
The root element is represented by the empty tuple ().
EXAMPLES:
sage: list(OrderedTree([]).paths())
[()]
sage: list(OrderedTree([[],[[]]]).paths())
[(), (0,), (1,), (1, 0)]
sage: list(BinaryTree([[],[[],[]]]).paths())
[(), (0,), (1,), (1, 0), (1, 1)]
TESTS:
sage: t = OrderedTree([[], [[], [[], []], [[], []]], [[], []]])
sage: t.node_number() == len(list(t.paths()))
True
sage: list(BinaryTree().paths())
[]
sage: bt = BinaryTree([[],[[],[]]])
sage: bt.node_number() == len(list(bt.paths()))
True
Run the depth-first post-order traversal algorithm (recursive implementation) and subject every node encountered to some procedure action. The algorithm is:
explore each subtree (by the algorithm) from the
leftmost one to the rightmost one;
then manipulate the root with function `action` (in the
case of a binary tree, only if the root is not a leaf).
INPUT:
OUTPUT:
None. (This is not an iterator.)
TESTS:
sage: l = []
sage: b = BinaryTree([[None,[]],[[[],[]],[]]]).canonical_labelling()
sage: b
3[1[., 2[., .]], 7[5[4[., .], 6[., .]], 8[., .]]]
sage: b.post_order_traversal(lambda node: l.append(node.label()))
sage: l
[2, 1, 4, 6, 5, 8, 7, 3]
sage: t = OrderedTree([[[[],[]]],[[]],[[],[]]]).\
....: canonical_labelling(); t
1[2[3[4[], 5[]]], 6[7[]], 8[9[], 10[]]]
sage: l = []
sage: t.post_order_traversal(lambda node: l.append(node.label()))
sage: l
[4, 5, 3, 2, 7, 6, 9, 10, 8, 1]
sage: l = []
sage: BinaryTree().canonical_labelling().\
....: post_order_traversal(lambda node: l.append(node.label()))
sage: l
[]
sage: OrderedTree([]).canonical_labelling().\
....: post_order_traversal(lambda node: l.append(node.label()))
sage: l
[1]
The following test checks that things do not go wrong if some among the descendants of the tree are equal or even identical:
sage: u = BinaryTree(None)
sage: v = BinaryTree([u, u])
sage: w = BinaryTree([v, v])
sage: t = BinaryTree([w, w])
sage: t.node_number()
7
sage: l = []
sage: t.post_order_traversal(lambda node: l.append(1))
sage: len(l)
7
The depth-first post-order traversal iterator.
This method iters each node following the depth-first post-order traversal algorithm (recursive implementation). The algorithm is:
explore each subtree (by the algorithm) from the
leftmost one to the rightmost one;
then yield the root (in the case of binary trees, only if
it is not a leaf).
EXAMPLES:
For example on the following binary tree \(b\):
| ___3____ |
| / \ |
| 1 _7_ |
| \ / \ |
| 2 5 8 |
| / \ |
| 4 6 |
(only the nodes are shown), the depth-first post-order traversal algorithm explores \(b\) in the following order of nodes: \(2,1,4,6,5,8,7,3\).
For another example, consider the labelled tree:
| __1____ |
| / / / |
| 2 6 8_ |
| | | / / |
| 3_ 7 9 10 |
| / / |
| 4 5 |
The algorithm explores this tree in the following order: \(4,5,3,2,7,6,9,10,8,1\).
TESTS:
sage: b = BinaryTree([[None,[]],[[[],[]],[]]]).canonical_labelling()
sage: ascii_art([b])
[ ___3____ ]
[ / \ ]
[ 1 _7_ ]
[ \ / \ ]
[ 2 5 8 ]
[ / \ ]
[ 4 6 ]
sage: [node.label() for node in b.post_order_traversal_iter()]
[2, 1, 4, 6, 5, 8, 7, 3]
sage: t = OrderedTree([[[[],[]]],[[]],[[],[]]]).canonical_labelling()
sage: ascii_art([t])
[ __1____ ]
[ / / / ]
[ 2 6 8_ ]
[ | | / / ]
[ 3_ 7 9 10 ]
[ / / ]
[ 4 5 ]
sage: [node.label() for node in t.post_order_traversal_iter()]
[4, 5, 3, 2, 7, 6, 9, 10, 8, 1]
sage: [node.label() for node in BinaryTree().canonical_labelling().\
....: post_order_traversal_iter()]
[]
sage: [node.label() for node in OrderedTree([]).\
....: canonical_labelling().post_order_traversal_iter()]
[1]
The following test checks that things do not go wrong if some among the descendants of the tree are equal or even identical:
sage: u = BinaryTree(None)
sage: v = BinaryTree([u, u])
sage: w = BinaryTree([v, v])
sage: t = BinaryTree([w, w])
sage: t.node_number()
7
sage: l = [1 for i in t.post_order_traversal_iter()]
sage: len(l)
7
Run the depth-first pre-order traversal algorithm (recursive implementation) and subject every node encountered to some procedure action. The algorithm is:
manipulate the root with function `action` (in the case
of a binary tree, only if the root is not a leaf);
then explore each subtree (by the algorithm) from the
leftmost one to the rightmost one.
INPUT:
OUTPUT:
None. (This is not an iterator.)
EXAMPLES:
For example, on the following binary tree \(b\):
| ___3____ |
| / \ |
| 1 _7_ |
| \ / \ |
| 2 5 8 |
| / \ |
| 4 6 |
the depth-first pre-order traversal algorithm explores \(b\) in the following order of nodes: \(3,1,2,7,5,4,6,8\).
Another example:
| __1____ |
| / / / |
| 2 6 8_ |
| | | / / |
| 3_ 7 9 10 |
| / / |
| 4 5 |
The algorithm explores this tree in the following order: \(1,2,3,4,5,6,7,8,9,10\).
TESTS:
sage: l = []
sage: b = BinaryTree([[None,[]],[[[],[]],[]]]).canonical_labelling()
sage: b
3[1[., 2[., .]], 7[5[4[., .], 6[., .]], 8[., .]]]
sage: b.pre_order_traversal(lambda node: l.append(node.label()))
sage: l
[3, 1, 2, 7, 5, 4, 6, 8]
sage: li = []
sage: b.iterative_pre_order_traversal(lambda node: li.append(node.label()))
sage: l == li
True
sage: t = OrderedTree([[[[],[]]],[[]],[[],[]]]).canonical_labelling()
sage: t
1[2[3[4[], 5[]]], 6[7[]], 8[9[], 10[]]]
sage: l = []
sage: t.pre_order_traversal(lambda node: l.append(node.label()))
sage: l
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
sage: li = []
sage: t.iterative_pre_order_traversal(lambda node: li.append(node.label()))
sage: l == li
True
sage: l = []
sage: BinaryTree().canonical_labelling().\
....: pre_order_traversal(lambda node: l.append(node.label()))
sage: l
[]
sage: OrderedTree([]).canonical_labelling().\
....: pre_order_traversal(lambda node: l.append(node.label()))
sage: l
[1]
The following test checks that things do not go wrong if some among the descendants of the tree are equal or even identical:
sage: u = BinaryTree(None)
sage: v = BinaryTree([u, u])
sage: w = BinaryTree([v, v])
sage: t = BinaryTree([w, w])
sage: t.node_number()
7
sage: l = []
sage: t.pre_order_traversal(lambda node: l.append(1))
sage: len(l)
7
The depth-first pre-order traversal iterator.
This method iters each node following the depth-first pre-order traversal algorithm (recursive implementation). The algorithm is:
yield the root (in the case of binary trees, if it is not
a leaf);
then explore each subtree (by the algorithm) from the
leftmost one to the rightmost one.
EXAMPLES:
For example, on the following binary tree \(b\):
| ___3____ |
| / \ |
| 1 _7_ |
| \ / \ |
| 2 5 8 |
| / \ |
| 4 6 |
(only the nodes shown), the depth-first pre-order traversal algorithm explores \(b\) in the following order of nodes: \(3,1,2,7,5,4,6,8\).
Another example:
| __1____ |
| / / / |
| 2 6 8_ |
| | | / / |
| 3_ 7 9 10 |
| / / |
| 4 5 |
The algorithm explores this labelled tree in the following order: \(1,2,3,4,5,6,7,8,9,10\).
TESTS:
sage: b = BinaryTree([[None,[]],[[[],[]],[]]]).canonical_labelling()
sage: ascii_art([b])
[ ___3____ ]
[ / \ ]
[ 1 _7_ ]
[ \ / \ ]
[ 2 5 8 ]
[ / \ ]
[ 4 6 ]
sage: [n.label() for n in b.pre_order_traversal_iter()]
[3, 1, 2, 7, 5, 4, 6, 8]
sage: t = OrderedTree([[[[],[]]],[[]],[[],[]]]).canonical_labelling()
sage: ascii_art([t])
[ __1____ ]
[ / / / ]
[ 2 6 8_ ]
[ | | / / ]
[ 3_ 7 9 10 ]
[ / / ]
[ 4 5 ]
sage: [n.label() for n in t.pre_order_traversal_iter()]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
sage: [n for n in BinaryTree(None).pre_order_traversal_iter()]
[]
The following test checks that things do not go wrong if some among the descendants of the tree are equal or even identical:
sage: u = BinaryTree(None)
sage: v = BinaryTree([u, u])
sage: w = BinaryTree([v, v])
sage: t = BinaryTree([w, w])
sage: t.node_number()
7
sage: l = [1 for i in t.pre_order_traversal_iter()]
sage: len(l)
7
Return a generator for all nonempty subtrees of self.
The number of nonempty subtrees of a tree is its number of nodes. (The word “nonempty” makes a difference only in the case of binary trees. For ordered trees, for example, all trees are nonempty.)
EXAMPLES:
sage: list(OrderedTree([]).subtrees())
[[]]
sage: list(OrderedTree([[],[[]]]).subtrees())
[[[], [[]]], [], [[]], []]
sage: list(OrderedTree([[],[[]]]).canonical_labelling().subtrees())
[1[2[], 3[4[]]], 2[], 3[4[]], 4[]]
sage: list(BinaryTree([[],[[],[]]]).subtrees())
[[[., .], [[., .], [., .]]], [., .], [[., .], [., .]], [., .], [., .]]
sage: v = BinaryTree([[],[]])
sage: list(v.canonical_labelling().subtrees())
[2[1[., .], 3[., .]], 1[., .], 3[., .]]
TESTS:
sage: t = OrderedTree([[], [[], [[], []], [[], []]], [[], []]])
sage: t.node_number() == len(list(t.subtrees()))
True
sage: list(BinaryTree().subtrees())
[]
sage: bt = BinaryTree([[],[[],[]]])
sage: bt.node_number() == len(list(bt.subtrees()))
True
Transform a tree into an hexadecimal string.
The definition of the hexacode is recursive. The first letter is the valence of the root as an hexadecimal (up to 15), followed by the concatenation of the hexacodes of the subtrees.
This method only works for trees where every vertex has valency at most 15.
See from_hexacode() for the reverse transformation.
EXAMPLES:
sage: from sage.combinat.abstract_tree import from_hexacode
sage: LT = LabelledOrderedTrees()
sage: from_hexacode('2010', LT).to_hexacode()
'2010'
sage: LT.an_element().to_hexacode()
'3020010'
sage: t = from_hexacode('a0000000000000000', LT)
sage: t.to_hexacode()
'a0000000000'
sage: OrderedTrees(6).an_element().to_hexacode()
'500000'
TESTS:
sage: one = LT([], label='@')
sage: LT([one for _ in range(15)], label='@').to_hexacode()
'f000000000000000'
sage: LT([one for _ in range(16)], label='@').to_hexacode()
Traceback (most recent call last):
...
ValueError: the width of the tree is too large
Return the tree-factorial of self.
Definition:
The tree-factorial \(T!\) of a tree \(T\) is the product \(\prod_{v\in T}\#\mbox{children}(v)\).
EXAMPLES:
sage: LT = LabelledOrderedTrees()
sage: t = LT([LT([],label=6),LT([],label=1)],label=9)
sage: t.tree_factorial()
3
sage: BinaryTree([[],[[],[]]]).tree_factorial()
15
TESTS:
sage: BinaryTree().tree_factorial()
1
Transform an hexadecimal string into a tree.
INPUT:
See AbstractTree.to_hexacode() for the description of the encoding
See _from_hexacode_aux() for the actual code
EXAMPLES:
sage: from sage.combinat.abstract_tree import from_hexacode
sage: from_hexacode('12000', LabelledOrderedTrees())
@[@[@[], @[]]]
sage: from_hexacode('1200', LabelledOrderedTrees())
@[@[@[], @[]]]
It can happen that only a prefix of the word is used:
sage: from_hexacode('a'+14*'0', LabelledOrderedTrees())
@[@[], @[], @[], @[], @[], @[], @[], @[], @[], @[]]
One can choose the label:
sage: from_hexacode('1200', LabelledOrderedTrees(), label='o')
o[o[o[], o[]]]
One can also create other kinds of trees:
sage: from_hexacode('1200', OrderedTrees())
[[[], []]]