An efficient recursive a algorithm for the generating all shapes
of binary trees with nnodes is presented. A binary tree with
nnodes is represented by 2(n−1) zeros and ones in a certain
predetermined order. This scheme encodes the nonnull links of a
binary tree by 1's and the null links by 0's in a preorder
traversal. The algorithm generates C_{n} numbers of such codes.
The algorithm is based on the idea of shifting `1' bits one space
to the right. It is shown that the generation time per tree is
constant O(1). The ranking and unranking algorithms are
discussed. Also, an alternate way to obtain the Catalan numbers is
given.
Download TeX format
