• 1
  • 2
  • 3
  • 4
IPM
30
YEARS OLD

“School of Mathematics”

Paper   IPM / M / 33
   School of Mathematics
  Title: On the generation of binary trees from (0-1) codes
  Author(s):
1 . A. Nowzari-Dalini
2 . H. Ahrabian
  Status: Published
  Journal: Int. J. Comput. Math.
  Vol.: 69
  Year: 1998
  Pages: 243-251
  Supported by: IPM
  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
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right