GRAMMAR-ORIENTED ENUMERATION OF BINARY-TREES

In contrast to traditional integer sequences for the representation of binary trees, a kind of character sequence (words) is presented for b inary trees based on a grammar GBT and for full binary trees based on a grammar GFBT. The properties of wards derived from GBT (GFBT) are di scussed in depth, including necessary and sufficient conditions for a word, prefix and suffix of (L) over bar(GBT) ((L) over bar(GFBT)) and algorithms are given and analysed for the enumeration of words of (L) over bar(GBT) ((L) over bar(GFBT)) lexicographically and in other ways , By modifying an algorithm for the enumeration of words in (L) over b ar(GBT), an algorithm is obtained to enumerate binary trees with a com puter representation in an average time of O(1) per tree. The problem with nom-isomorphic series of binary trees is also discussed within th e category of a grammar.