將含有父ID的列表轉成樹，id列表成樹

將含有父ID的列表轉成樹，id列表成樹

我們知道數據庫一般是以一個列表(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         $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) {
          }
        }
      }
    }
  }
}

成功把列表轉成了樹