Proskurowski, Andrzej; Ruskey, Frank Generating binary trees by transpositions. (English) Zbl 0651.68081 Algorithm theory, Proc. 1st Scand. Workshop, Halmstad/Sweden 1988, Lect. Notes Comput. Sci. 318, 199-207 (1988). Summary: [For the entire collection see Zbl 0639.00043.] Let T(n) denote the set of all bitstrings with n 1’s and n 0’s such 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 that generate the elements of T(n) in such a way that successive bitstrings differ by the transposition of two bits. The presented algorithms have a constant average time per generated tree. Cited in 2 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity 94B25 Combinatorial codes Keywords:Gray code; binary trees; bitstrings; transposition; constant average time Citations:Zbl 0639.00043 PDFBibTeX XML