Bijection between binary trees and plane trees?

Question

I would like to describe a bijection between binary trees and plane trees. A binary tree has a root node and each node of the tree has at most 2 children (left and right). A plane tree has a root node and the children of each node are ordered from left to right. Can someone enlighten me on this? Thanks!

Answer 1

The tree is a totally repeating structure, so we need to try for a bijection between a plain tree with one root node plus whatever number of children and a particular binary tree.

I think the following algorithm will work: Lets suppose the Root node of a plain tree has n children, then we count $min (k): 2^k <= n $ Next we build the 3-level binary tree with Root node = Root node of the plain tree and intermediate nodes also = Root node of the plain tree.

The binary tree itself is a subclass of a plain tree

Answer 2

There is a way of encoding n-ary trees into binary: the left is a son and the right is a brother; here is the Wikipedia's entry.

P.S. This was a comment, made an answer on request.