“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 33 |
|
||||
| Abstract: | |||||
|
An efficient recursive a algorithm for the generating all shapes
of binary trees with n-nodes is presented. A binary tree with
n-nodes is represented by 2(n−1) zeros and ones in a certain
predetermined order. This scheme encodes the non-null links of a
binary tree by 1's and the null links by 0's in a pre-order
traversal. The algorithm generates Cn 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 |
|||||
| back to top | |||||
