1-1hit |
In literature, many methods have been presented for enumerating binary trees (full binary trees) and regular k-ary trees, while no one for enumerating arbitrary trees or arbitrary 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 (GTk) to code arbitrary trees (arbitrary k-ary trees) for enumerating them. The properties of words of Ln(GT) (Ln(GTk)) are discussed in depth, including necessary and sufficient conditions for a word, prefix and suffix of Ln(GT) (Ln(GTk)), and efficient algorithms are given and analyzed for the enumeration of words of Ln(GT) (Ln(GTk)).