Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
There is a way of encoding n-ary trees into binary: the left is a son and the right is a brother. Are you looking along those lines, could you provide some context? –  dtldarek Dec 4 '12 at 18:41
    
@dtldarek: Indeed. Left-child right-sibling binary tree, in wikipedia terminology. Can you make that an answer, so we can +1 it? –  Hendrik Jan Dec 4 '12 at 21:37

2 Answers 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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.