A Ranking Algorithm of Non-Regular Trees in Gray-Code Order
Ro–Yu Wu, Jou–Ming Chang, An–Hang Chen · International Journal of Machine Learning and Computing · 2012
A non-regular tree T with a prescribed branching sequence is an ordered tree whose internal nodes are numbered from 1 to n in preorder such that every node in T has a prescribed number of children.Recently, Wu et al. (2010) introduced a concise representation called RD-sequences to represent all non-regular trees and proposed a loopless algorithm for generating all non-regular trees in a Gray-code order.In this paper, based on such a Gray-code order, we show that a ranking algorithm can be done in quadratic time provided a preprocessing in advance.