| id | parent_id | name |
|---|---|---|
| 1 | 0 | A |
| 2 | 1 | AA |
| 3 | 1 | AB |
| 4 | 3 | ABA |
| 5 | 3 | ABB |
| 6 | 3 | ABC |
| 7 | 1 | AC |
| 8 | 7 | ACA |
| 9 | 8 | ACAA |
| 10 | 8 | ACAB |
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.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.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.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