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!
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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