Tree datastructures

Tree datastructures is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The following shows a tree of data with nesting denoted by visual levels of indentation:

RosettaCode
    rocks
        code
        comparison
        wiki
    mocks
        golfing

A common datastructure for trees is to define node structures having a name and a, (possibly empty), list of child nodes. The nesting of nodes captures the indentation of the tree. Lets call this the nest form.

Another datastructure for trees is to construct from the root an ordered list of the nodes level of indentation and the name of that node. The indentation for the root node is zero; node 'rocks is indented by one level from the left, and so on. Lets call this the indent form.

0 RosettaCode
1 rocks
2 code
...

Task

1. Create/use a nest datastructure format and textual representation for arbitrary trees.
2. Create/use an indent datastructure format and textual representation for arbitrary trees.
3. Create methods/classes/proceedures/routines etc to:
   1. Change from a nest tree datastructure to an indent one.
   2. Change from an indent tree datastructure to a nest one
4. Use the above to encode the example at the start into the nest format, and show it.
5. transform the initial nest format to indent format and show it.
6. transform the indent format to final nest format and show it.
7. Compare initial and final nest formats which should be the same.

Show all output on this page.

Python

Just arranges the standard lists and tuples for the datastructures allowing pprint to show the different arrangement of storage.

<lang python>from pprint import pprint as pp from collections import namedtuple

def to_indent(node, depth=0, flat=None):

   if flat is None:
       flat = []
   if node:
       flat.append((depth, node[0]))
   for child in node[1]:
       to_indent(child, depth + 1, flat)
   return flat

def to_nest(lst, depth=0, level=None):

   if level is None:
       level = []
   while lst:
       d, name = lst[0]
       if d == depth:
           children = []
           level.append((name, children))
           lst.pop(0)
       elif d > depth:  # down
           to_nest(lst, d, children)
       elif d < depth:  # up
           return
   return level[0] if level else None
                   

if __name__ == '__main__':

   print('Start Nest format:')
   nest = ('RosettaCode', [('rocks', [('code', []), ('comparison', []), ('wiki', [])]), 
                           ('mocks', [('golfing', [])])])
   pp(nest, width=25)

   print('\n... To Indent format:')
   as_ind = to_indent(nest)
   pp(as_ind, width=25)

   print('\n... To Nest format:')
   as_nest = to_nest(as_ind)
   pp(as_nest, width=25)

   if nest != as_nest:
       print("Whoops round-trip issues")</lang>

Output:

Start Nest format:
('RosettaCode',
 [('rocks',
   [('code', []),
    ('comparison', []),
    ('wiki', [])]),
  ('mocks',
   [('golfing', [])])])

... To Indent format:
[(0, 'RosettaCode'),
 (1, 'rocks'),
 (2, 'code'),
 (2, 'comparison'),
 (2, 'wiki'),
 (1, 'mocks'),
 (2, 'golfing')]

... To Nest format:
('RosettaCode',
 [('rocks',
   [('code', []),
    ('comparison', []),
    ('wiki', [])]),
  ('mocks',
   [('golfing', [])])])