Building a linear tree hierarchy using Python

Question

Enter the following json:

{
    'a': {
        'children': [],
        'name': 'a'
    },
    'b': {
        'children': [{
                'x': {
                    'children': [],
                    'name': 'x'
                }
            }, {
                'y': {
                    'children': [{
                        'z': {
                            'children': [],
                            'name': 'z'
                        }
                    }]
                }]
        }
    }

The final result should be:

a 
b -> x
b -> y -> z

I am having trouble transferring the mind around a recursive function that I need to solve. Are lists associated with this solution? There is an unknown recursion level in my data, so the function should just keep returning any child nodes. I have no problem listing all nodes recursively, however tracking them is my problem.

def print_tree(tree, prev=None, child=False):
    for node in tree:
        print(node['name'])
        if len(node['children']):          
            print_tree(node['children'])




print_tree(tree_data)

What logic am I missing to track this?

Answer 1

You have problems with your code.

• JSON is invalid, there is no close }to the last]

• Have your units band ydo not have a setname

• : node, children node, node. , { 'a': ..., 'b': ... }, [ { 'a': ... }, { 'b': ... } ].

• . .., { 'x': nodeX }, 'x' - , nodeX

1 2

data = \
  { 'a': { 'children': []
         , 'name': 'a'
         }
  , 'b': { 'children': [ { 'x': { 'children': []
                                , 'name': 'x'
                                }
                         }
                       , { 'y': { 'children': [ { 'z': { 'children': []
                                                       , 'name': 'z'
                                                       }
                                                }
                                              ]
                                , 'name': 'y' # you missed this
                                }
                         } # you missed this
                       ]
          , 'name': 'b'  # you missed this
          }
  }

3, root node

root = \
  { 'root': { 'children': [ {k:v} for (k,v) in data.items() ]
            , 'name': 'root'
            }
  }

4 unwrap_node

def unwrap_node (wrapped_node):
  node, *_ = wrapped_node.values()
  if 'children' in node and len (node['children']) > 0:
    return { 'name': node['name']
           , 'children': [ unwrap_node(n) for n in node['children'] ]
           }
  else:
    return node 

. traverse, () node

def traverse (node, path = []):
  if 'children' in node and len (node['children']) > 0:
    for n in node['children']:
      yield from traverse (n, path + [ node ])
  else:
    yield path + [ node ]

, node name "->"

for path in traverse (unwrap_node (root)):
  print (" -> ".join (node['name'] for node in path))

# root -> a
# root -> b -> x
# root -> b -> y -> z

, print_tree, . root -> ...

def print_tree (node):    
  for path in traverse (unwrap_node (node)):
    print (" -> ".join (n['name'] for n in path if n['name'] is not 'root'))

print_tree (root)
# a
# b -> x
# b -> y -> z

JSON,

Answer 2

, , . , , (, , ..) .

, , , , / . - :

# this function collects the paths as lists (e.g. ['b', 'y', 'z']) and returns a list of those paths
def get_paths(tree):
  paths = []
  for branch in tree:
    name = tree[branch]['name']
    children = tree[branch]['children']
    if len(children):
      # this mostly accounts for the fact that the children are a dictionary in a list
      for node in children:
        # get the paths from the children
        sub_paths = get_paths(node)
        # add this element to the beginning of those paths
        for path in sub_paths:
          path.insert(0, name)
        # transfer modified sub-paths to list of paths
        paths.extend(sub_paths)
    else:
      # leaf node, add as a path with one element
      paths.append([name])
  return paths

# this function uses the above function to get the paths and then prints the results as desired
def print_tree(tree):
  paths = get_paths(tree)
  print(paths)
  # do whatever you want with the paths
  for path in paths:
    print(' -> '.join(path))

( "y" "b" ), :

a
b -> x
b -> y -> z