Python：树形实现字典数据结构

Question

Python：树形实现字典数据结构

6

我有一个类似于这样的字典对象：

topo = {
'name' : 'm0',
'children' : [{
    'name' : 'm1',
    'children' : []
 }, {
    'name' : 'm2',
    'children' : []
 }, {
    'name' : 'm3',
    'children' : []
 }]
}

现在，我想插入一个字典对象，例如，

{
'name' : 'ABC',
'children' : []
}

作为名为"m2"的字典内子项，需要在m2的子项数组中实现。请问我该如何处理？

我应该选择单独的数据结构实现吗？

- Aashish P

1

如果您想通过名称而不是索引来访问项目，请使用字典或有序字典（OrderedDict）代替列表（list）作为子元素。 - oleg

5个回答

3

你的问题是一个常见的树形结构，你可以考虑使用http://pythonhosted.org/ete2/tutorial/tutorial_trees.html，并将每个节点填充为你的字典值（不要重复造轮子）。

- Ali SAID OMAR

您可以使用http://pythonhosted.org/ete2/tutorial/tutorial_trees.html#creating-trees-from-scratch来构建您的树形结构，并使用字典将名称与其值进行映射。 - Ali SAID OMAR

1

将其像平常一样加入字典中，使用.append()方法：

topo['children'][1]['children'].append({'name' : 'ABC', 'children' : []})

topo现在是：

{
  "name": "m0", 
  "children": [
    {
      "name": "m1", 
      "children": []
    }, 
    {
      "name": "m2", 
      "children": [
        {
          "name": "ABC", 
          "children": []
        }
      ]
    }, 
    {
      "name": "m3", 
      "children": []
    }
  ]
}

- TerryA

1

topo['children'][1]['children'].append({'name': 'ABC', 'children': []})

这将在topo的第二个子节点的子节点下添加新字典：

{'children': [{'children': [], 'name': 'm1'},
              {'children': [{'children': [], 'name': 'ABC'}], 'name': 'm2'},
              {'children': [], 'name': 'm2'}],
 'name': 'm0'}

但是我不会使用字典和列表内置对象来完成这样的任务 - 我更愿意创建自己的对象。

- mawimawi

0

topo['children'].append({'name' : 'ABC',
                      'children' : []
                     })

- Ivan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- morningstar · Accepted Answer

我建议您先将其转换为以下数据结构：

我建议您首先将其转换为类似这样的数据结构：

topo = {
  'm0' : {
    'm1' : {},
    'm2' : {},
    'm3' : {},
  },
}

也就是说，您已经将“name”键的每个值都作为字典中的一个键，并且“children”键的每个值都成为该键的值，并将它从列表更改为字典。

现在，您不需要预先假设m2所在的索引位置。您确实需要知道m2在m0内部，但然后您可以简单地说：

topo['m0']['m2']['ABC'] = {}

您可以使用以下代码在不同格式之间进行转换：

def verbose_to_compact(verbose):
    return { item['name']: verbose_to_compact(item['children']) for item in verbose }

def compact_to_verbose(compact):
    return [{'name':key, 'children':compact_to_verbose(value)} for key, value in compact]

按照以下方式进行调用

compact_topo = verbose_to_compact([topo]) # function expects list; make one-item list
verbose_topo = compact_to_verbose(compact_topo)[0] # function returns list; extract the single item

我假设你现有的格式是某个文件格式的直接解释。你可以按照这种方式读取它，转换它，在紧凑格式下处理它，然后在需要再次写入文件时将其转换回来。