EDIT: Actually, in retrospect, this is not quite right. It maps every tree to a natural number, but not every natural number to a tree. Regardless, it can be handy in certain circumstances.
Another simpler way of doing this is to encode a tree with n levels as 2^n - 1 bits. The first bit is 1 if and only if this tree has a root. The next 2^(n-1) - 1 bits represent the left tree. The following 2^(n-1) - 1 bits represent the right tree. Recurse as needed until you get to a tree with only one level (which is either a single node when the bit is 1, or is nothing when the bit is 0).
I'm fairly sure this is not optimal, but it is much simpler.
Another simpler way of doing this is to encode a tree with n levels as 2^n - 1 bits. The first bit is 1 if and only if this tree has a root. The next 2^(n-1) - 1 bits represent the left tree. The following 2^(n-1) - 1 bits represent the right tree. Recurse as needed until you get to a tree with only one level (which is either a single node when the bit is 1, or is nothing when the bit is 0).
I'm fairly sure this is not optimal, but it is much simpler.