4
$\begingroup$

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!

  • 0
    @dtldarek: Indeed. Left-child right-sibling binary tree, in wikipedia terminology. Can you make that an answer, so we can +1 it?2012-12-04

2 Answers 2

4

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.

0

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