PQ Tree - Examples and Notation

Examples and Notation

If all the leaves of a PQ tree are connected directly to a root P node then all possible orderings are allowed. If all the leaves are connected directly to a root Q node then only one order (and its reverse) is allowed. If nodes a,b,c connect to a P node, which connects to a root P node, with all other leaf nodes connected directly to the root, then any ordering where a,b,c are contiguous is allowed.

Where graphical presentation is unavailable PQ trees are often noted using nested parenthesized lists. Square parentheses represents a Q node and regular ones represents P nodes. Leaves are non-parentheses elements of the lists. The image on the left is represented in this notation by . This PQ tree represents the following twelve permutations on the set {1, 2, 3, 4, 5}:

12345, 12435, 13245, 13425, 14235, 14325, 52341, 52431, 53241, 53421, 54231, 54321.