Iterator - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Iterator : Trees : Iterator/Trees

Iterator

  

Trees

  

procedures for converting between tree representations

 

Description

Examples

References

Compatibility

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 : ek 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; lk (rk) is the left (right) child of node k. This is the format output by BinaryTrees.

• 

S : sk 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; ck is the level of the forest's kth node in preorder.

• 

D : run-length encoding.  A string of nested-parentheses is encoded as d1d2...dn, where the exponent dk produces dk nested parentheses.

• 

P : permutation encoding. The permutation p1,p2,...,pn represents a parenthesis string, where the kth right parenthesis matches the pkth left parenthesis.

• 

Z : zk is the location of the kth 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

Examples

withIterator:

withTrees

Conjugate,Convert,Random,Transpose

(1)

Binary Trees

• 

Construct an iterator that generates all binary trees with four internal nodes, in LR format.

BBinaryTrees4:

• 

Print the LR, C, E, and S representations of the binary trees.

printf L | R | C | E | S\n:forlrinBdocConvertlr,LR,C;sConvertc,C,S;eConverts,S,E;printf%{}d | %{}d | %{}d | %{}d | %{}d\n,lr,c,e,senddo:

   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.

ANestedParentheses4:

• 

Print the string of parentheses and its A, C, D, P, and Z representations.

printf | A | C | D | P | Z\n:forainAdozConverta,A,Z;cConvertz,Z,C;dConvertz,Z,D;pConvertc,C,P;printf%s | %{}d | %{}d | %{}d | %{}d | %{}d\n,StringA,a,c,d,p,zenddo:

         |        A        |    C    |    D    |    P    |    Z

Iterator:-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
Iterator:-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
Iterator:-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
Iterator:-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
Iterator:-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
Iterator:-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
Iterator:-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
Iterator:-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
Iterator:-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
Iterator:-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
Iterator:-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
Iterator:-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
Iterator:-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
Iterator:-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.

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

See Also

Iterator

Iterator[BinaryTrees]

Iterator[NestedParentheses]