Mapping an n-ary tree representation to a logical binary tree structure

Andrew Smith, 2003

Preamble

Tabular representation

Node	Parent
Da	Da
Db	Da
Dc	Da
Dd	Db
De	Db
Df	Db
Dg	Dc
Dh	Dc
Di	Dc
Dj	Dc
Dk	Dd
Dm	Dh
Dn	Dh

N-ary Tree representation

                     D_a
                   /     \
                  /       \
                D_b       D_c ____________
              /  |  \      \    \    \    \
             /   |   \      \    \    \    \
           D_d  D_e  D_f    D_g  D_h  D_i  D_j
           /                    /   \ 
          /                    /     \
        D_k                  D_m     D_n

Binary Tree representation

                     D_a
                    / 
                   / 
                 D_b _________
                /             \
               /               \
             D_d               D_c
            /   \             /
           /     \           /
         D_k     D_e        D_g
                    \         \
                     \         \
                     D_f       D_h
                              /   \
                             /     \
                           D_m      D_i
                              \       \
                               \       \
                               D_n     D_j