Enumerating, Ranking and Unranking Binary Trees

Abstract

We introduce weight sequences, which are sequences of positive integers characterising binary trees, in order to generate lexicographically binary trees as a list. Algorithms are developed to determine the position of a given weight sequence, and to generate the weight sequence of a given position. We also use weight sequences in order to study a transformation on binary trees. Furthermore, we make a link with term rewriting systems.