Grammar-Oriented Enumeration of Binary Trees
Liming Xiang · The Computer Journal · 1997
In contrast to traditional integer sequences for the representation of binary trees, a kind of character sequence (words) is presented for binary trees based on a grammar GBT and for full binary trees based on a grammar GFBT. The properties of words derived from GBT (GFBT) are discussed in depth, including necessary and sufficient conditions for a word, prefix and suffix of Ł(GBT) (Ł(GFBT)) and algorithms are given and analysed for the enumeration of words of Ł(GBT) (Ł(GFBT)) lexicographically and in other ways. By modifying an algorithm for the enumeration of words in Ł(GBT), an algorithm is obtained to enumerate binary trees with a computer representation in an average time of O(1) per tree. The problem with non-isomorphic series of binary trees is also discussed within the category of a grammar.