Overview of the Iterator:-Trees Subpackage
Description
Examples
References
Compatibility
The Iterator:-Trees subpackage exports procedures that convert between representations of tree structures.
Binary Tree Formats
Binary trees are represented in preorder. A binary tree is associated with a forest by the natural correspondence [1]. The following paragraphs describe the E, LR, and S binary tree formats.
E : is the number of children of node of the forest associated with the binary tree.
LR : two -arrays, and , specify the left and right children; () is the left (right) child of node . This is the format output by BinaryTrees.
S : is the number of descendants of node of the forest associated with the binary tree.
Nested Parentheses Formats
The following paragraphs describe the A, C, D, P, and Z nested parentheses formats
A : binary representation of n pairs of nested parentheses. The array is indexed from 1 to 2n. A zero (one) at index k corresponds to a left (right) parenthesis. This is the format output by NestedParentheses.
C : inversion table encoding of the permutation representation (P). This also corresponds to a level encoding of the corresponding forest; is the level of the forest's th node in preorder.
D : run-length encoding. A string of nested-parentheses is encoded as , where the exponent produces nested parentheses.
P : permutation encoding. The permutation represents a parenthesis string, where the th right parenthesis matches the th left parenthesis.
Z : is the location of the th left parenthesis.
Exports
Conjugate
compute the conjugate of a tree
Convert
convert between tree formats
Random
generate a random tree
Transpose
compute the transpose of a tree
Binary Trees
Construct an iterator that generates all binary trees with four internal nodes, in LR format.
Print the LR, C, E, and S representations of the binary trees.
L | R | C | E | S
2 3 4 0 | 0 0 0 0 | 0 1 2 3 | 1 1 1 0 | 3 2 1 0 0 3 4 0 | 2 0 0 0 | 0 0 1 2 | 0 1 1 0 | 0 2 1 0 2 0 4 0 | 0 3 0 0 | 0 1 1 2 | 2 0 1 0 | 3 0 1 0 2 0 4 0 | 3 0 0 0 | 0 1 0 1 | 1 0 1 0 | 1 0 1 0 0 0 4 0 | 2 3 0 0 | 0 0 0 1 | 0 0 1 0 | 0 0 1 0 2 3 0 0 | 0 0 4 0 | 0 1 2 2 | 1 2 0 0 | 3 2 0 0 0 3 0 0 | 2 0 4 0 | 0 0 1 1 | 0 2 0 0 | 0 2 0 0 2 3 0 0 | 0 4 0 0 | 0 1 2 1 | 2 1 0 0 | 3 1 0 0 2 3 0 0 | 4 0 0 0 | 0 1 2 0 | 1 1 0 0 | 2 1 0 0 0 3 0 0 | 2 4 0 0 | 0 0 1 0 | 0 1 0 0 | 0 1 0 0 2 0 0 0 | 0 3 4 0 | 0 1 1 1 | 3 0 0 0 | 3 0 0 0 2 0 0 0 | 4 3 0 0 | 0 1 1 0 | 2 0 0 0 | 2 0 0 0 2 0 0 0 | 3 0 4 0 | 0 1 0 0 | 1 0 0 0 | 1 0 0 0 0 0 0 0 | 2 3 4 0 | 0 0 0 0 | 0 0 0 0 | 0 0 0 0
Nested Parentheses
Construct an iterator that generates all nested pairs of four parentheses.
Print the string of parentheses and its A, C, D, P, and Z representations.
| A | C | D | P | Z
NestedParentheses(4) | 0 1 0 1 0 1 0 1 | 0 0 0 0 | 1 1 1 1 | 1 2 3 4 | 1 3 5 7 NestedParentheses(4) | 0 1 0 1 0 0 1 1 | 0 0 0 1 | 1 1 0 2 | 1 2 4 3 | 1 3 5 6 NestedParentheses(4) | 0 1 0 0 1 1 0 1 | 0 0 1 0 | 1 0 2 1 | 1 3 2 4 | 1 3 4 7 NestedParentheses(4) | 0 1 0 0 1 0 1 1 | 0 0 1 1 | 1 0 1 2 | 1 3 4 2 | 1 3 4 6 NestedParentheses(4) | 0 1 0 0 0 1 1 1 | 0 0 1 2 | 1 0 0 3 | 1 4 3 2 | 1 3 4 5 NestedParentheses(4) | 0 0 1 1 0 1 0 1 | 0 1 0 0 | 0 2 1 1 | 2 1 3 4 | 1 2 5 7 NestedParentheses(4) | 0 0 1 1 0 0 1 1 | 0 1 0 1 | 0 2 0 2 | 2 1 4 3 | 1 2 5 6 NestedParentheses(4) | 0 0 1 0 1 1 0 1 | 0 1 1 0 | 0 1 2 1 | 2 3 1 4 | 1 2 4 7 NestedParentheses(4) | 0 0 1 0 1 0 1 1 | 0 1 1 1 | 0 1 1 2 | 2 3 4 1 | 1 2 4 6 NestedParentheses(4) | 0 0 1 0 0 1 1 1 | 0 1 1 2 | 0 1 0 3 | 2 4 3 1 | 1 2 4 5 NestedParentheses(4) | 0 0 0 1 1 1 0 1 | 0 1 2 0 | 0 0 3 1 | 3 2 1 4 | 1 2 3 7 NestedParentheses(4) | 0 0 0 1 1 0 1 1 | 0 1 2 1 | 0 0 2 2 | 3 2 4 1 | 1 2 3 6 NestedParentheses(4) | 0 0 0 1 0 1 1 1 | 0 1 2 2 | 0 0 1 3 | 3 4 2 1 | 1 2 3 5 NestedParentheses(4) | 0 0 0 0 1 1 1 1 | 0 1 2 3 | 0 0 0 4 | 4 3 2 1 | 1 2 3 4
Knuth, Donald Ervin. The Art of Computer Programming, volume 1, 3rd ed. fundamental algorithms, sec. 2.3.2, binary tree representation of trees, pp. 334-335.
The Iterator:-Trees package was introduced in Maple 2016.
For more information on Maple 2016 changes, see Updates in Maple 2016.
See Also
Iterator
Iterator[BinaryTrees]
Iterator[NestedParentheses]
Download Help Document