All Possible Combination of a Tree
If you are interested in the number of binary trees with a given number of nodes, see here: http://en.wikipedia.org/wiki/Catalan_number
Author
Oh I see. Thanks. I need the actual combination, not the number. Alvaro, I will give your algorithm a shot. Have you done this before with that algorithm?
Author
[quote name='D.Chhetri' timestamp='1297878270' post='4775032']
Does anyone now how many combinations there should be? Maybe something like 2^n - n, where n is number of children.
Oh, it's worse than that. For binary trees of depth exactly n, the recurrence is f(n)=f(n-1)^2+2f(n-1), n(1)=1. That comes out to 2+(2^(n-1))-1. That's, for instance, 65 thousand trees for depth 5.
[/quote]
Maybe I'm missing something how is plugging 5 for n into the formula 2^(n-1) + 1 equals 65k?
[quote name='Sneftel' timestamp='1297886897' post='4775094']
[quote name='D.Chhetri' timestamp='1297878270' post='4775032']
Does anyone now how many combinations there should be? Maybe something like 2^n - n, where n is number of children.
Oh, it's worse than that. For binary trees of depth exactly n, the recurrence is f(n)=f(n-1)^2+2f(n-1), n(1)=1. That comes out to 2+(2^(n-1))-1. That's, for instance, 65 thousand trees for depth 5.
[/quote]
Maybe I'm missing something how is plugging 5 for n into the formula 2^(n-1) + 1 equals 65k?
[/quote]
Whoops, typo. The equation is 2^(2^(n-1))-1. Double exponentiation.
Oh I see. Thanks. I need the actual combination, not the number. Alvaro, I will give your algorithm a shot. Have you done this before with that algorithm?
No, but I am good at this type of thing.
Author
Hey alvaro, just a quick question on your algorithm. Is this what you mean :
[color="#666600"]I just want to be sure.
ContainerOfTrees generate_all_binary_trees(root) {
if (root.isLeaf())
return contrainer_of_trees_with_only_an_empty_tree;
ContainerOfTrees result;
size_t size = root.childrenCount();
for (int i=0; i< size; ++i) {
ContainerOfTrees left_trees = generate_all_binary_trees(root.childrenAt(i));
ContainerOfTrees right_trees = generate_all_binary_trees(root.childrenAt(size - i - 1));
for (Tree left in left_trees) {
for (Tree right in right_trees) {
result.push(build_tree(left, right));
}
}
}
return result;
}
[font="'Courier New"][color="#666600"]
[/font]
[color="#666600"]I just want to be sure.
Author
[quote name='D.Chhetri' timestamp='1297900220' post='4775170']
[quote name='Sneftel' timestamp='1297886897' post='4775094']
[quote name='D.Chhetri' timestamp='1297878270' post='4775032']
Does anyone now how many combinations there should be? Maybe something like 2^n - n, where n is number of children.
Oh, it's worse than that. For binary trees of depth exactly n, the recurrence is f(n)=f(n-1)^2+2f(n-1), n(1)=1. That comes out to 2+(2^(n-1))-1. That's, for instance, 65 thousand trees for depth 5.
[/quote]
Maybe I'm missing something how is plugging 5 for n into the formula 2^(n-1) + 1 equals 65k?
[/quote]
Whoops, typo. The equation is 2^(2^(n-1))-1. Double exponentiation.
[/quote]
Hey, do you have a link to the proof of this? Or some sort of reference?
Hey alvaro, just a quick question on your algorithm. Is this what you mean :
ContainerOfTrees generate_all_binary_trees(root) {
if (root.isLeaf())
return contrainer_of_trees_with_only_an_empty_tree;
ContainerOfTrees result;
size_t size = root.childrenCount();
for (int i=0; i< size; ++i) {
ContainerOfTrees left_trees = generate_all_binary_trees(root.childrenAt(i));
ContainerOfTrees right_trees = generate_all_binary_trees(root.childrenAt(size - i - 1));
for (Tree left in left_trees) {
for (Tree right in right_trees) {
result.push(build_tree(left, right));
}
}
}
return result;
}
[font="'Courier New"][color="#666600"]
[/font]
[color="#666600"]I just want to be sure.
I think the pseudo-code I posted was correct. Here it is in working C++ (using boost::shared_ptr):
#include <iostream>
#include <boost/smart_ptr.hpp>
#include <vector>
struct Node {
boost::shared_ptr<Node> left, right;
Node(boost::shared_ptr<Node> left, boost::shared_ptr<Node> right)
: left(left), right(right) {
}
};
typedef boost::shared_ptr<Node> Tree;
Tree make_tree(Tree left, Tree right) {
return Tree(new Node(left, right));
}
typedef std::vector<Tree> TreeVector;
std::ostream &operator<<(std::ostream &os, Tree n) {
if (n != Tree()) {
os << '(' << n->left << ')' << n->right;
}
return os;
}
TreeVector generate_trees(int nodes) {
if (nodes == 0)
return TreeVector(1);
TreeVector result;
for (int i=0; i<nodes; ++i) {
TreeVector left_trees = generate_trees(i);
TreeVector right_trees = generate_trees(nodes-i-1);
for (TreeVector::iterator i = left_trees.begin(),
end_i = left_trees.end(); i != end_i; ++i) {
for (TreeVector::iterator j = right_trees.begin(),
end_j = right_trees.end(); j != end_j; ++j) {
result.push_back(make_tree(*i, *j));
}
}
}
return result;
}
int main() {
TreeVector trees = generate_trees(10);
for (TreeVector::const_iterator i = trees.begin(),
end_i = trees.end(); i != end_i; ++i) {
std::cout << *i << '\n';
}
}
[quote name='Sneftel' timestamp='1297903888' post='4775196']
Whoops, typo. The equation is 2^(2^(n-1))-1. Double exponentiation.
Hey, do you have a link to the proof of this? Or some sort of reference?
[/quote]
A vanilla application of mathematical induction will tell you that the formula is correct.
Author
Oh I see. I think I might have been mistaken in my words. I was not trying to generate all possible binary tree given of N nodes size. What I was trying to do was given a general tree, make all possible binary combination of that general tree,. Which is why I posted the above modification on your algorithm. I think its the same process as your algorithm. Unless, I'm being confused somewhere.
EDIT: and sorry, I was referring more to the reoccurrence relation.
EDIT: and sorry, I was referring more to the reoccurrence relation.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
