Convert General Trees to Binary Trees

http://examradar.com/converting-m-ary-tree-general-tree-binary-tree/
https://studylib.net/doc/7707838/general-trees-and-conversion-to-binary-trees
Left-child right-sibling binary tree

a left-child, right-sibling binary tree is a binary tree representation of a k-ary tree.^[1] The process of converting from a k-ary tree to an LC-RS binary tree (sometimes called Knuth transform^[2]).

6-ary tree represented as a binary tree

To form a binary tree from an arbitrary k-ary tree by this method, the root of the original tree is made the root of the binary tree. Then, starting with the root, each node's leftmost child in the original tree is made its left child in the binary tree, and its nearest sibling to the right in the original tree is made its right child in the binary tree.^[3]

If the original tree was sorted, the new tree will be a binary search tree.

http://xlinux.nist.gov/dads//HTML/binaryTreeRepofTree.html

Let us see one example. Consider the following multiway tree

                  1           
                 /|\          
                / | \         
               /  |  \        
              2   3   4       
             / \      |       
            5   6     7       
                     / \      
                    8   9     
 

This tree can be represented in first child-next sibling manner as follows

                  1           
                 /            
                /             
               /              
              2---3---4       
             /       /        
            5---6   7         
                   /          
                  8---9       
 

Now, if we look at the first child-next sibling representation of the tree closely, we will see that it forms a binary tree. To see this better, we can rotate every next-sibling edge 45 degrees clockwise. After that we get the following binary tree:

                1             
               /              
              2               
             / \              
            5   3             
             \   \            
              6   4           
                 /            
                7             
               /              
              8               
               \              
                9             
 

This is binary tree representation of the given (multiway) tree.

General Trees and Conversion to Binary Trees

General trees can be represented as ADT's in whatever form they exist. However, there are some substantial problems. First, the number of references for each node must be equal to the maximum that will be used in the tree. Obviously, some real problems are presented when another subtree is added to a node which already has the maximum number attached to it. It is also obvious that most of the algorithms for searching, traversing, adding and deleting nodes become much more complex in that they must now cope with situations where there are not just two possibilities for any node but multiple possibilities. 

Fortunately, general trees can be converted to binary trees.  They don't often end up being well formed or full, but the advantages  accrue from being able to use the algorithms for processing that are used for binary trees with minor modifications.  Therefore, each node requires only two references but these are not designated as left or right. Instead they are

designated as the reference to the first child and the reference to next sibling.  Therefore the usual left pointer really points to the first child of the node and the usual right pointer points to the next sibling of the node.  One obvious saving in this structure is the number of fields which must be used for references.  In this way, moving right from a node accesses

the siblings of the node ( that is all of those nodes on the same level as the node in the general tree). Moving left and then right accesses all of the children of the node (that is the nodes on the next level of the general tree).