
Re: Generation of random binary trees
Posted:
Mar 2, 2014 4:09 AM


Am 02.03.2014 00:54, schrieb Joe keane: > In article <lelj4l$2s7$1@news.albasani.net>, > MokKong Shen <mokkong.shen@tonline.de> wrote: >> Given n, I want to randomly generate a binary tree (unlabelled) that >> has n end nodes. Could someone kindly provide a reference containing >> an algorithm for doing that? > > They are counted by Catalan numbers. > > At worst you can generate some random strings like "()(())" and throw > out the ones that are illegal. > > There's probably a better way.
Isn't it that the Catalan number gives only the total count. Given a number less the total count, how could one determine the corresponding tree algorithmically?
M. K. Shen

