A linear Time Algorithm for the Generation of Trees
Résumé
We present a linear algorithm which generates randomly and with uniform probability many kinds of trees: binary trees, ternary trees, arbitrary trees, forests of $p$ $k$-ary trees, $\ldots$. The algorithm is based on the definition of generic trees which can be coded as words. These words, in turn, are generated in linear time.