A Loopless Gray-Code Algorithm for Listing k-ary Trees
✍ Scribed by Dominique Roelants van Baronaigien
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 91 KB
- Volume
- 35
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
The bit sequence representation for k-ary trees is a sequence b , b , . . . , b
of bits that is formed by doing a preorder traversal of the k-ary tree and writing a 1 when the visited subtree is not empty and a zero when the visited subtree is empty.
The representation is well known and in the case of binary trees, the bit sequence representation also represents well-formed parenthesis strings. This paper presents the first loopless algorithm for listing the bit sequence representations of k-ary trees in a Gray-code order. The algorithm is simpler than existing loop free algorithms for both binary and k-ary trees. The algorithm is also the only known algorithm that generates the bit sequences by homogeneous transpositions.