Tree datastructures: Difference between revisions
(New draft task with python example.) |
m (sp.) |
||
Line 9: | Line 9: | ||
golfing</pre> |
golfing</pre> |
||
A common datastructure for trees is to define node structures having a name and a, (possibly empty), list of child nodes. |
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 |
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'''. |
||
;Task: |
;Task: |
||
Line 19: | Line 19: | ||
## Change from a nest tree datastructure to an indent one. |
## Change from a nest tree datastructure to an indent one. |
||
## Change from an indent tree datastructure to a nest one |
## Change from an indent tree datastructure to a nest one |
||
# Use the above to encode the example |
# Use the above to encode the example at the start into the nest format, and show it. |
||
# transform the initial nest format to indent format and show it. |
# transform the initial nest format to indent format and show it. |
||
# transform the indent format to final nest format and show it. |
# transform the indent format to final nest format and show it. |
Revision as of 22:27, 15 October 2019
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.
- Task
- Create/use a nest datastructure format and textual representation for arbitrary trees.
- Create/use an indent datastructure format and textual representation for arbitrary trees.
- Create methods/classes/proceedures/routines etc to:
- Change from a nest tree datastructure to an indent one.
- Change from an indent tree datastructure to a nest one
- Use the above to encode the example at the start into the nest format, and show it.
- transform the initial nest format to indent format and show it.
- transform the indent format to final nest format and show it.
- 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_list(node, depth=0, flat=None):
if flat is None: flat = [] if node: flat.append((depth, node[0])) for child in node[1]: to_list(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 List format:') as_list = to_list(nest) pp(as_list, width=25)
print('\n... To Nest format:') as_nest = to_nest(as_list[:]) 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 List 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', [])])])