在python中将平面嵌套数据转换为层次数据的最佳方法

Question

我以扁平的方式表示类别层次。
类别层次结构是

category1  
    category4
        category6  
    category5  
        category7
category2
category3

我用字典把这个作为列表储存起来

^{pr2}$

将这个类别列表转换为层次列表的最佳方法是什么

[{'name': 'category1',
  'subcategory': [{'name': 'category4',
                   'subcategory': [{'name': 'category6', 'subcategory': []}]},
                  {'name': 'category5',
                   'subcategory': [{'name': 'category7', 'subcategory': []}]}]},
 {'name': 'category2', 'subcategory': []},
 {'name': 'category3', 'subcategory': []}]

Answer 1

def flat_to_hierarchical(d, category_id=None):
    out = list()
    for item in filter(lambda item: item['parent_category_id']==category_id, d):
        out.append(dict(
            name = item['name'],
            subcategories = flat_to_hierarchical(d, item['id'])
        ))
    return out


print(flat_to_hierarchical(d))

Answer 2

你的问题和我在Calculating the Path from Parent Child Relationships 回答的问题非常相似

我注意到您的数据结构中似乎有很多多余的字段。基本上，您可以通过以下方式表示帖子中的信息：

d = {1: {4: {6: None}, 5: {7: None}}, 2: None, 3: None}

为你重新编写代码。在

^{pr2}$

输出：

3
2
1 5 7
1 4 6

为了把它变成一个嵌套字典，我建议您参考What is the best way to implement nested dictionaries?

Answer 3

我们从给定index和root节点标识的make_tree开始

def make_tree (index, root):
  if not root in index:
    return []
  else:
    return [ make_node (index, child) for child in index[root] ]

现在我们需要一种方法make_node-这是我们将输入数据中的元素转换为输出树的元素的地方

^{pr2}$

当然，现在我们需要一种基于输入数据的make_index的方法。我们使用itertools^{}，这样我们就可以高效地查找所有子节点

from itertools import groupby

def make_index (nodes):
  return \
    { k: list (v)
        for (k,v) in
          groupby (nodes, lambda n: n['parent_category_id']) }

最后，我们编写main来将它们绑定在一起。注意数据不会为每次迭代重新编制索引或过滤

def main (nodes, root = None):
  return make_tree (make_index (nodes), root)

全程序演示

from itertools import groupby

def make_tree (index, root):
  if not root in index:
    return []
  else:
    return [ make_node (index, child) for child in index[root] ]

def make_node (index, child):
  return \
    { 'name': child['name']
    , 'children': make_tree (index, child['id'])
    }

def make_index (nodes):
  return \
    { k: list (v)
        for (k,v) in
          groupby (nodes, lambda n: n['parent_category_id']) }

def main (nodes, root = None):
  return make_tree (make_index (nodes), root)

d = \
  [ {'id': 1, 'name': 'category1', 'parent_category_id': None, 'level': 1}
  , {'id': 2, 'name': 'category2', 'parent_category_id': None, 'level': 1}
  , {'id': 3, 'name': 'category3', 'parent_category_id': None, 'level': 1}
  , {'id': 4, 'name': 'category4', 'parent_category_id': 1, 'level': 2}
  , {'id': 5, 'name': 'category5', 'parent_category_id': 1, 'level': 2}
  , {'id': 7, 'name': 'category6', 'parent_category_id': 4, 'level': 3}
  , {'id': 7, 'name': 'category7', 'parent_category_id': 5, 'level': 3}
  ]

# get sub-tree of [None] from dataset [d]
print (main (d, None))

程序输出

[ { 'name': 'category1'
  , 'children': [ { 'name': 'category4'
                  , 'children': [  { 'name': 'category6'
                                  , 'children': []
                                  }
                                ]
                  }
                  , { 'name': 'category5'
                    , 'children': [ { 'name': 'category7'
                                    , 'children': []
                                    }
                                  ]
                    }
                ]
  }
  , { 'name': 'category2', 'children': [] } 
  , { 'name': 'category3', 'children': [] }
]