![将含有父ID的列表转成树 将含有父ID的列表转成树](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
我们知道数据库一般是以一个列表(id,pid)的形式保存树的。如何提取这棵树呢?最简单的方法就是根据pid循环查表。但是毫无疑问,这会产生巨大的数据库查询开销。
那么一般建议的方法是一次性将全部相关数据全查出来,但是这就涉及到一个问题,如何快速的构建一棵树。
我曾经一直以为,这是一个复杂的操作,至少需要一个递归,时间复杂度不会是O(n)。
前段时间,一个工作上的需求,需要解决这个问题。我仔细想了想,发现完全可以通过单层循环解决这个问题,实现如下:
function list2Tree($listItem, $idx = 'id', $pIdx = 'pid', $childKey= 'list'){
$map = array();
$pMap = array(); foreach($listItem as $item){
$id = $item[$idx];
$pid = $item[$pIdx];
$map[$id] = &$item;
unset($item);
} foreach($map as $id => &$item){
$pid = $item[$pIdx];
empty($item[$childKey]) && $item[$childKey] = array(); if(! isset($map[$pid])){
$pMap[$id] = &$item;
}
else{
$pItem= &$map[$pid];
$pItem[$childKey][] = &$item;
} unset($item, $pItem);
} return array_shift($pMap);
}
测试一下:
// 路径方便识别父子关系
$json = <<<JSON
[
{
"id": 2,
"pid": 1,
"path": "/se"
},
{
"id": 3,
"pid": 2,
"path": "/se/4901"
},
{
"id": 4,
"pid": 5,
"path": "/se/4901/mask/query"
},
{
"id": 5,
"pid": 3,
"path": "/se/4901/mask"
},
{
"id": 6,
"pid": 2,
"path": "/se/4902"
},
{
"id": 7,
"pid": 6,
"path": "/se/4902/mask"
}
]
JSON; $list = json_decode($json, true); var_dump(list2Tree($list));
结果:
array(4) {
["id"]=>
int(2)
["pid"]=>
int(1)
["path"]=>
string(3) "/se"
["list"]=>
array(2) {
[0]=>
array(4) {
["id"]=>
int(3)
["pid"]=>
int(2)
["path"]=>
string(8) "/se/4901"
["list"]=>
array(1) {
[0]=>
array(4) {
["id"]=>
int(5)
["pid"]=>
int(3)
["path"]=>
string(13) "/se/4901/mask"
["list"]=>
array(0) {
}
}
}
}
[1]=>
array(4) {
["id"]=>
int(6)
["pid"]=>
int(2)
["path"]=>
string(8) "/se/4902"
["list"]=>
array(1) {
[0]=>
array(4) {
["id"]=>
int(7)
["pid"]=>
int(6)
["path"]=>
string(13) "/se/4902/mask"
["list"]=>
array(0) {
}
}
}
}
}
}
成功把列表转成了树