Generating Binary Trees by Transpositions. Ruskey, F. & Proskurowski, A. Journal of Algorithms, 11(1):68--84, March, 1990.
Generating Binary Trees by Transpositions [link]Paper  doi  abstract   bibtex   
Let T(n) denote the set of all bitstrings with n 1's and n 0's that satisfy the property that in every prefix the number of 0's does not exceed the number of 1's. This is a well known representation of binary trees. We consider algorithms for generating the elements of T(n) that satisfy one of the following constraints: (a) successive bitstrings differ by the transposition of two bits or (b) successive bitstrings differ by the transposition of two adjacent bits. In case (a) a constant average time generation algorithm is presented. In case (b) we show that such generation is possible if and only if n is even or n < 5. A constant average time algorithm is presented in this case as well.
@article{ Ruskey1990,
  abstract = {Let T(n) denote the set of all bitstrings with n 1's and n 0's that satisfy the property that in every prefix the number of 0's does not exceed the number of 1's. This is a well known representation of binary trees. We consider algorithms for generating the elements of T(n) that satisfy one of the following constraints: (a) successive bitstrings differ by the transposition of two bits or (b) successive bitstrings differ by the transposition of two adjacent bits. In case (a) a constant average time generation algorithm is presented. In case (b) we show that such generation is possible if and only if n is even or n < 5. A constant average time algorithm is presented in this case as well.},
  author = {Ruskey, Frank and Proskurowski, Andrzej},
  doi = {10.1016/0196-6774(90)90030-I},
  file = {:Users/KunihiroWASA/Dropbox/paper/1990/Ruskey, Proskurowski, Generating Binary Trees by Transpositions, 1990.pdf:pdf},
  issn = {01966774},
  journal = {Journal of Algorithms},
  month = {March},
  number = {1},
  pages = {68--84},
  title = {{Generating Binary Trees by Transpositions}},
  url = {http://www.sciencedirect.com/science/article/pii/019667749090030I http://linkinghub.elsevier.com/retrieve/pii/019667749090030I},
  volume = {11},
  year = {1990}
}

Downloads: 0