列表list转树形结构(python/golang/js/php)

1. 原数据

data = [
	{id: 1, parent_id: 0, name: "A"},
	{id: 2, parent_id: 1, name: "AA"},
	{id: 3, parent_id: 1, name: "AB"},
	{id: 4, parent_id: 3, name: "ABA"},
	{id: 5, parent_id: 3, name: "ABB"},
	{id: 6, parent_id: 3, name: "ABC"},
	{id: 7, parent_id: 1, name: "AC"},
	{id: 8, parent_id: 7, name: "ACA"},
	{id: 9, parent_id: 8, name: "ACAA"},
	{id: 10, parent_id: 8, name: "ACAB"},
]

2. 利用对象内存共享生成嵌套结构

2.1 算法原理

2.2 算法实现

2.2.1 JS

function list_to_tree(data) {
	/**
	* @data: 由id和parent_id组成的树形结构二维数据, 元数据中id必须大于0
	*/
	res = {};
	for (let i = 0; i < data.length; i++) {
	    row = data[i];
	    // 此行代码用以统一根节点的paren_id, 跟节点的parent_id 可以为 0 或 null
	    row.parent_id = row.parent_id ? row.parent_id : 0
		if (res[row.id]) {
			Object.assign(res[row.id], {id: row.id, text: row.name});
	    } else {
			res[row.id] = {id: row.id, text: row.name, children: []};
	    }
	    if (res[row.parent_id]) {
	        res[row.parent_id].children.push(res[row.id]);
	    } else {
			res[row.parent_id] = {children: [res[row.id]]};
	    }
	}
	return res[0].children
}

2.2.2 Python

def list_to_tree(data):
    res = {}
    for v in data:
        v["parent_id"] = v["parent_id"] if v["parent_id"] else 0
        res.setdefault(v["id"], v).update(v)
        res.setdefault(v["parent_id"], {}).setdefault("children", []).append(res.get(v["id"], v))
    return res[0]["children"]

2.2.3 go

func listToTree(data []map[string]interface{}) []map[string]interface{} {
	res := make(map[int]map[string]interface{})
	for _, v := range data {
		id := v["id"].(int)
		parentID := v["parent_id"].(int)
		if res[id] != nil {
			v["children"] = res[id]["children"]
			res[id] = v
		} else {
			v["children"] = []map[string]interface{}{}
			res[id] = v
		}
		if res[parentID] != nil {
			res[parentID]["children"] = append(
				res[parentID]["children"].([]map[string]interface{}),
				res[id],
			)
		} else {
			res[parentID] = map[string]interface{}{
				"children": []map[string]interface{}{
					res[id],
				},
			}
		}
	}
	return res[0]["children"].([]map[string]interface{})
}

2.2.4 php

function listToTree($list) {
    $res = [];
    foreach ($list as &$v) {
        $id = $v['id'];
        $parentId = $v['parent_id'];
        //构造map给parent_id查找追加用
        if (isset($res[$id])) {
            $v['child'] = &$res[$id]['child'];//child放到v里边
            $res[$id] = $v;
        } else {
            $v['child'] = [];
            $res[$id] = $v;
        }
        //追加带child的自己到parent_id的child数组中
        if (isset($res[$parentId])) {
            $res[$parentId]['child'][] = &$res[$id];
        } else {
            $res[$parentId] = ['child' => [&$res[$id]]];
        }
    }
    return $res[0]['child'];
}

$data = [
  ['id'=> 1, 'parent_id' => 0, 'name' => "A"],
  ['id'=> 2, 'parent_id' => 1, 'name' => "AA"],
  ['id'=> 3, 'parent_id' => 1, 'name' => "AB"],
  ['id'=> 4, 'parent_id' => 3, 'name' => "ABA"],
  ['id'=> 5, 'parent_id' => 3, 'name' => "ABB"],
  ['id'=> 6, 'parent_id' => 3, 'name' => "ABC"],
  ['id'=> 7, 'parent_id' => 1, 'name' => "AC"],
  ['id'=> 8, 'parent_id' => 7, 'name' => "ACA"],
  ['id'=> 9, 'parent_id' => 8, 'name' => "ACAA"],
  ['id'=> 10, 'parent_id' => 8, 'name' => "ACAB"],
];

$res = listToTree($data);

2.3 运行结果

[
	{id: 1, text: "A", children: [
		{id: 2, text: "AA", children: []},
		{id: 3, text: "AB", children: [
			{id: 4, text: "ABA", children: []},
			{id: 5, text: "ABB", children: []},
			{id: 6, text: "ABC", children: []}
		]},
		{id: 7, text: "AC", children: [
			{id: 8, text: "ACA", children: [
				{id: 9, text: "ACAA", children: []},
				{id: 10, text: "ACAB", children: []}
			]}
		]}
	]}
]

3. 递归

3.1 算法实现

3.1.1 python

def list_to_tree2(list_data, parent_id=0):
    res = []
    for v in list_data:
        if v['parent_id'] == parent_id:
            v['children'] = get_tree_recursive(list_data, v['id'])
            res.append(v)
    return res

4. 运算效率对比

4.1 python

s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
i = 0
data = []
for v1 in s:
    i += 1
    data.append({'id': i, 'parent_id': 0, 'name': v1})
    p1 = i
    for v2 in s:
        i += 1
        data.append({'id': i, 'parent_id': p1, 'name': v1+v2})
        p2 = i
        for v3 in s:
            i += 1
            data.append({'id': i, 'parent_id': p2, 'name': v1+v2+v3})
len(data)

生成18278条三层嵌套数据结构

如上图所示, 递归版耗时18s, 而循环版仅耗时25ms