我们知道数据库一般是以一个列表(id,pid)的形式保存树的。如何提取这棵树呢？最简单的方法就是根据pid循环查表。但是毫无疑问，这会产生巨大的数据库查询开销。
那么一般建议的方法是一次性将全部相关数据全查出来，但是这就涉及到一个问题，如何快速的构建一棵树。
我曾经一直以为，这是一个复杂的操作，至少需要一个递归，时间复杂度不会是O(n)。
前段时间，一个工作上的需求，需要解决这个问题。我仔细想了想，发现完全可以通过单层循环解决这个问题，实现如下：
1 function list2Tree($listItem, $idx = 'id', $pIdx = 'pid', $childKey= 'list'){ 2 $map = array(); 3 $pMap = array(); 4 5 foreach($listItem as $item){ 6 $id = $item[$idx]; 7 $pid = $item[$pIdx]; 8 $map[$id] = &$item; 9 unset($item);10 } 11 12 foreach($map as $id => &$item){13 $pid = $item[$pIdx];14 empty($item[$childKey]) && $item[$childKey] = array();15 16 if(! isset($map[$pid])){17 $pMap[$id] = &$item; 18 } 19 else{ 20 $pItem= &$map[$pid];21 $pItem[$childKey][] = &$item;22 } 23 24 unset($item, $pItem);25 }26 27 return array_shift($pMap);28 }
测试一下：
1 // 路径方便识别父子关系 2 $json = <<<JSON 3 [ 4 { 5 "id": 2, 6 "pid": 1, 7 "path": "/se" 8 }, 9 {10 "id": 3,11 "pid": 2,12 "path": "/se/4901"13 },14 {15 "id": 4,16 "pid": 5,17 "path": "/se/4901/mask/query"18 },19 {20 "id": 5,21 "pid": 3,22 "path": "/se/4901/mask"23 },24 {25 "id": 6,26 "pid": 2,27 "path": "/se/4902"28 },29 {30 "id": 7,31 "pid": 6,32 "path": "/se/4902/mask"33 }34 ]35 JSON;36 37 $list = json_decode($json, true);38 39 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) { } } } } }}
成功把列表转成了树