Grammar-Oriented Enumeration of Arbitrary Trees and Arbitrary k-ary Trees

摘要

In literature, many methods have been pre- sented for enumerating binary trees (full binary trees) and regular k-ary trees, while no one for enumerating arbitrary trees or ar- bitrary k-ary trees. It is proposed in 1997 using a context-free grammar GBT (GFBT) to code binary trees (full binary trees) for enumerating them. In this paper, we use another grammar GT (GT_k) to code arbitrary trees (arbitrary k-ary trees) for enu- merating them. The properties of words of L_n(GT) (L_n (GT_k)) are discussed in depth, including necessary and sufficient condi- tions for a word, prefix and suffix of L_n(GT) (L_n(GT_k)), and efficient algorithms are given and analyzed for the enumeration of words of L_n (GT) (L_n (GT_k )).