In this paper an efficient algorithm for generating k-ary trees in Gray code order is presented. This algorithm is an extended form of the constant time algorithm developed by Vajnovszki to enumerate Gray codes for binary trees. In our algorithm the k-ary trees are represented by bitstring sequences. The generation algorithm is based on moving in a Hamiltonian path of a graph, which each vertex of it is labeled with a bitstring corresponding to a k-ary tree. Clearly, the Gray code property of the vertices construct the edges of this graph. The algorithm generates two successor codes in constant delay time.
k-ary tree, Gray codes, Constant time generation algorithm.
All articles published by Studies in Informatics and Control (SIC) are published in accordance with the terms and conditions of the Creative Commons Attribution License (CC BY-NC-SA 4.0).