Author |
Topic: Generating Binary Trees (Read 1590 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Generating Binary Trees
« on: May 11th, 2004, 6:29am » |
 Quote  Modify
|
Devise an algorithm that generates all binary trees with n internal nodes.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Generating Binary Trees
« Reply #2 on: May 11th, 2004, 8:55am » |
Quote Modify
|
::any permutation of 1..n can be seen as the infix notation of a tree with n nodes numbered breadth first 1 to n
So simply generate all permutations of 1..n::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Generating Binary Trees
« Reply #3 on: May 11th, 2004, 10:46am » |
Quote Modify
|
on May 11th, 2004, 8:31am, towr wrote:| I suppose you'd rather not have duplicates? |
|
Correct.
As for your proposed solution: do you mean that there is a 1-1 correspondence between permutations of n elements and binary trees with n internal nodes? If yes, then I don't agree with you.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Generating Binary Trees
« Reply #4 on: May 11th, 2004, 1:00pm » |
Quote Modify
|
Only with that one extra condition that I mentioned. That excludes a few permutations from giving a valid tree.
You can look at it in another way, ::repeatedly splitting the number of nodes
i.e
given n=a+1+b nodes, a >=0 nodes go to the left subtree, b>=0 to the right
rince and repeat
::
|
| « Last Edit: May 11th, 2004, 1:06pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Generating Binary Trees
« Reply #5 on: May 12th, 2004, 4:13am » |
Quote Modify
|
on May 11th, 2004, 1:00pm, towr wrote:| Only with that one extra condition that I mentioned. That excludes a few permutations from giving a valid tree. |
|
How would you say which permutation represents a valid tree, and which one?
Quote:| You can look at it in another way, :: … :: |
|
Could you write a program that implements this approach? How much space it will take?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Generating Binary Trees
« Reply #6 on: May 12th, 2004, 4:40am » |
Quote Modify
|
on May 12th, 2004, 4:13am, Barukh wrote:
How would you say which permutation represents a valid tree, and which one? |
|
Well, there's only one way to make a binary tree from a given permutation, and once you've done so you can check wether the nodes are numbered correctly (and thus constitutes a unique binary tree)
You can check it in O(n), I'm not quite sure how many you'd have to discard though, so it may not be that efficient overall.
Quote:| Could you write a program that implements this approach? How much space it will take? |
|
Yes I probably could, and maybe I will 
I could probably do it serially in memory, with recursion that would probably make it about O(n2). Parallel would be easier though, in which case you get something like O(n!) (which seems the right ballpark for how many trees you get)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Generating Binary Trees
« Reply #7 on: May 12th, 2004, 6:28am » |
Quote Modify
|
Code:#include <iostream>
#include <vector>
int x=0; /* counter */
class Node
{
public:
int d_N_children,
d_left,
d_right;
};
void process(std::vector<Node> &nodes, int l, int r)
{
if (l==r)
x++; /* alternatively do something with (a copy of) the binary tree*/
else
if (nodes[l].d_N_children == 0) /* leaf */
{
nodes[l].d_left=-1;
nodes[l].d_right=-1;
process(nodes, l+1, r);
}
else
{
int m = nodes[l].d_N_children;
nodes[l].d_left=-1;
nodes[l].d_right=r;
nodes[r].d_N_children = m-1;
process(nodes, l+1, r+1);
nodes[l].d_left=r;
nodes[l].d_right=-1;
process(nodes, l+1, r+1);
nodes[l].d_right=r+1;
for(int i=1; i < m; i++)
{
nodes[r].d_N_children = i-1;
nodes[r+1].d_N_children = m-i-1;
process(nodes, l+1, r+2);
}
}
}
int main(int argc, char ** argv)
{
int n=argc > 1 ? atoi(argv[1]) : 5;
std::vector<Node> nodes(n);
nodes[0].d_N_children=n-1;
process(nodes, 0, 1);
std::cout << x << std::endl;
}
|
|
I wasn't sure what to do with the trees, so I just counted them, and got A000108 (binomial(2n,n)/(n+1)) which is what one might expect..
Also, it's O(n) in space, which is better than I had expected.
|
| « Last Edit: May 12th, 2004, 6:34am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print