python - 从列表类别创建递归列表

Question

我正在编写一段代码，其中有一些这种格式的输入数据:

_input = [
        ('Cat 1', 'Sub Cat 1', 'lvl_3_cat-1'),
        ('Cat 1', 'Sub Cat 2', 'lvl_3_cat-2'),
        ('Cat 2', 'Sub Cat 3', 'lvl_3_cat-3')
    ]

我需要将以下类别列表转换为父子嵌套列表，可以迭代该列表以获取嵌套关系列表。

预期输出

expected output = [{
    "name": 'Cat 1',
    "children": [{
        "name": 'Sub Cat 1',
        "children": [{
            "name": 'lvl_3_cat-1',
            "children": []
        }]
    },{
        "name": 'Sub Cat 2',
        "children": [{
            "name": 'lvl_3_cat-2',
            "children": []
        }]
    }]
},{
    "name": 'Cat 2',
    "children": [{
        "name": 'Sub Cat',
        "children": [{
            "name": 'lvl_3_cat-3',
            "children": []
        }]
    }]
}]

此示例中的输入具有 3 级嵌套，但这可以是动态的，即最多 n 个。

我当前的代码

    def dsearch(lod, name):
        for e in lod:
            if e["name"] == name:
                return e
            else:
                return dsearch(e["children"], name)
        return {
            'name': name,
            'children': []
        }


    data = []
    lvl_products = [
        ('Cat 1', 'Sub Cat 1', 'lvl_3_cat-1'),
        ('Cat 1', 'Sub Cat 2', 'lvl_3_cat-2'),
        ('Cat 2', 'Sub Cat 3', 'lvl_3_cat-3')
    ]

    for lvl_product in lvl_products:
        print(lvl_product)
        parent = None; main_parent = None
        for _ in range(len(lvl_product)):
            element = dsearch(data, lvl_product[_])
            print(element)
            if parent:
                parent['children'].append(element)
            if main_parent is None:
                main_parent = parent
            parent = element
        data.append(main_parent)
    print(data) 

我当前的输出

[
    {
        "children": [
            {
                "children": [
                    {
                        "children": [],
                        "name": "lvl_3_cat-1"
                    },
                    {
                        "children": [],
                        "name": "lvl_3_cat-2"
                    }
                ],
                "name": "Sub Cat 1"
            },
            {
                "children": [
                    {
                        "children": [],
                        "name": "lvl_3_cat-1"
                    },
                    {
                        "children": [],
                        "name": "lvl_3_cat-2"
                    }
                ],
                "name": "Sub Cat 1"
            }
        ],
        "name": "Cat 1"
    },
    {
        "children": [
            {
                "children": [
                    {
                        "children": [],
                        "name": "lvl_3_cat-1"
                    },
                    {
                        "children": [],
                        "name": "lvl_3_cat-2"
                    }
                ],
                "name": "Sub Cat 1"
            },
            {
                "children": [
                    {
                        "children": [],
                        "name": "lvl_3_cat-1"
                    },
                    {
                        "children": [],
                        "name": "lvl_3_cat-2"
                    }
                ],
                "name": "Sub Cat 1"
            }
        ],
        "name": "Cat 1"
    }
]

Answer 1

您可以使用基于 collections.defaultdict 的树状数据结构。这使用类别级别作为键，使用子树作为值:

from collections import defaultdict


def tree():
    return defaultdict(tree)


def insert(node, value):
    if value:
        key, *remainder = value
        insert(node[key], remainder)


data = [
    ('Cat 1', 'Sub Cat 1', 'lvl_3_cat-1'),
    ('Cat 1', 'Sub Cat 2', 'lvl_3_cat-2'),
    ('Cat 2', 'Sub Cat 3', 'lvl_3_cat-3'),
]
root = tree()
for sample in data:
    insert(root, sample)

import json
print(json.dumps(root, indent=2, default=dict))

这会产生以下数据结构:

{
  "Cat 1": {
    "Sub Cat 1": {
      "lvl_3_cat-1": {}
    },
    "Sub Cat 2": {
      "lvl_3_cat-2": {}
    }
  },
  "Cat 2": {
    "Sub Cat 3": {
      "lvl_3_cat-3": {}
    }
  }
}

---

如果您确实想保留带有 "name" 和 "children" 键的单独字典包装器，您可以使用以下函数转换上述树:

def convert(node):
    return [{'name': key, 'children': convert(value)} for key, value in node.items()]

from pprint import pprint
pprint(convert(root))

输出为:

[{'children': [{'children': [{'children': [], 'name': 'lvl_3_cat-1'}],
                'name': 'Sub Cat 1'},
               {'children': [{'children': [], 'name': 'lvl_3_cat-2'}],
                'name': 'Sub Cat 2'}],
  'name': 'Cat 1'},
 {'children': [{'children': [{'children': [], 'name': 'lvl_3_cat-3'}],
                'name': 'Sub Cat 3'}],
  'name': 'Cat 2'}]