Overview - Maple Help

Iterator

 Trees
 procedures for converting between tree representations

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 : ${e}_{k}$ is the number of children of node $k$ of the forest associated with the binary tree.
 • LR : two $n$-arrays, $l$ and $r$, specify the left and right children; ${l}_{k}$ (${r}_{k}$) is the left (right) child of node $k$. This is the format output by BinaryTrees.
 • S : ${s}_{k}$ is the number of descendants of node $k$ 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; ${c}_{k}$ is the level of the forest's $k$th node in preorder.
 • D : run-length encoding.  A string of nested-parentheses is encoded as ${\left(\right)}^{{d}_{1}}{\left(\right)}^{{d}_{2}}\mathrm{...}{\left(\right)}^{{d}_{n}}$, where the exponent ${d}_{k}$ produces ${d}_{k}$ nested parentheses.
 • P : permutation encoding. The permutation ${p}_{1},{p}_{2},\mathrm{...},{p}_{n}$ represents a parenthesis string, where the $k$th right parenthesis matches the ${p}_{k}$th left parenthesis.
 • Z : ${z}_{k}$ is the location of the $k$th left parenthesis.

Exports

 compute the conjugate of a tree convert between tree formats generate a random tree compute the transpose of a tree

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$
 > $\mathrm{with}\left(\mathrm{Trees}\right)$
 $\left[{\mathrm{Conjugate}}{,}{\mathrm{Convert}}{,}{\mathrm{Random}}{,}{\mathrm{Transpose}}\right]$ (1)

Binary Trees

 • Construct an iterator that generates all binary trees with four internal nodes, in LR format.
 > $B≔\mathrm{BinaryTrees}\left(4\right):$
 • Print the LR, C, E, and S representations of the binary trees.
 > $\mathrm{printf}\left("L | R | C | E | S\n"\right):$$\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{lr}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}B\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}c≔\mathrm{Convert}\left(\mathrm{lr},'\mathrm{LR}','C'\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}s≔\mathrm{Convert}\left(c,'C','S'\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}e≔\mathrm{Convert}\left(s,'S','E'\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%\left\{\right\}d | %\left\{\right\}d | %\left\{\right\}d | %\left\{\right\}d | %\left\{\right\}d\n",\mathrm{lr},c,e,s\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 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.
 > $A≔\mathrm{NestedParentheses}\left(4\right):$
 • Print the string of parentheses and its A, C, D, P, and Z representations.
 > $\mathrm{printf}\left("| A | C | D | P | Z\n"\right):$$\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}a\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}A\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}z≔\mathrm{Convert}\left(a,'A','Z'\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}c≔\mathrm{Convert}\left(z,'Z','C'\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}d≔\mathrm{Convert}\left(z,'Z','\mathrm{D}'\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}p≔\mathrm{Convert}\left(c,'C','P'\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%s | %\left\{\right\}d | %\left\{\right\}d | %\left\{\right\}d | %\left\{\right\}d | %\left\{\right\}d\n",\mathrm{String}\left(A\right),a,c,d,p,z\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 |        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

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.