|
Description
|
|
•
|
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
|
|
|
|
|
Examples
|
|
| (1) |
|
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.
|
>
|
|
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.
|
>
|
|
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
| |
|
|
|
References
|
|
|
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.
|
|
|
Compatibility
|
|
•
|
The Iterator:-Trees package was introduced in Maple 2016.
|
|
|
|