将含有父ID的列表转成树，id列表成树

将含有父ID的列表转成树，id列表成树

我们知道数据库一般是以一个列表(id,pid)的形式保存树的。如何提取这棵树呢？最简单的方法就是根据pid循环查表。但是毫无疑问，这会产生巨大的数据库查询开销。

那么一般建议的方法是一次性将全部相关数据全查出来，但是这就涉及到一个问题，如何快速的构建一棵树。

我曾经一直以为，这是一个复杂的操作，至少需要一个递归，时间复杂度不会是O(n)。

前段时间，一个工作上的需求，需要解决这个问题。我仔细想了想，发现完全可以通过单层循环解决这个问题，实现如下：

<span> 1</span> <span>function</span> list2Tree(<span>$listItem</span>, <span>$idx</span> = 'id', <span>$pIdx</span> = 'pid', <span>$childKey</span>= 'list'<span>){
</span><span> 2</span>     <span>$map</span> = <span>array</span><span>();
</span><span> 3</span>     <span>$pMap</span> = <span>array</span><span>();
</span><span> 4</span> 
<span> 5</span>     <span>foreach</span>(<span>$listItem</span> <span>as</span> <span>$item</span><span>){
</span><span> 6</span>         <span>$id</span> = <span>$item</span>[<span>$idx</span><span>];
</span><span> 7</span>         <span>$pid</span> = <span>$item</span>[<span>$pIdx</span><span>];
</span><span> 8</span>         <span>$map</span>[<span>$id</span>] = &<span>$item</span><span>;
</span><span> 9</span>         <span>unset</span>(<span>$item</span><span>);
</span><span>10</span> <span>    }       
</span><span>11</span>             
<span>12</span>     <span>foreach</span>(<span>$map</span> <span>as</span> <span>$id</span> => &<span>$item</span><span>){
</span><span>13</span>         <span>$pid</span> = <span>$item</span>[<span>$pIdx</span><span>];
</span><span>14</span>         <span>$item</span>[<span>$childKey</span>] = <span>array</span><span>();
</span><span>15</span> 
<span>16</span>         <span>if</span>(! <span>isset</span>(<span>$map</span>[<span>$pid</span><span>])){
</span><span>17</span>             <span>$pMap</span>[<span>$id</span>] = &<span>$item</span><span>; 
</span><span>18</span> <span>        }       
</span><span>19</span>         <span>else</span><span>{   
</span><span>20</span>             <span>$pItem</span>= &<span>$map</span>[<span>$pid</span><span>];
</span><span>21</span>             <span>$pItem</span>[<span>$childKey</span>][] = &<span>$item</span><span>;
</span><span>22</span> <span>        }   
</span><span>23</span> 
<span>24</span>         <span>unset</span>(<span>$item</span>, <span>$pItem</span><span>);
</span><span>25</span> <span>    }
</span><span>26</span>    
<span>27</span>     <span>return</span> <span>array_shift</span>(<span>$pMap</span><span>);
</span><span>28</span> }

测试一下：

<span> 1</span> <span>//</span><span> 路径方便识别父子关系</span>
<span> 2</span> <span>$json</span> = <<<<span>JSON
</span><span> 3</span> <span>[
</span><span> 4</span> <span>    {
</span><span> 5</span>         "id": 2,
<span> 6</span>         "pid": 1,
<span> 7</span>         "path": "/se"
<span> 8</span>     },
<span> 9</span> <span>    {
</span><span>10</span>         "id": 3,
<span>11</span>         "pid": 2,
<span>12</span>         "path": "/se/4901"
<span>13</span>     },
<span>14</span> <span>    {
</span><span>15</span>         "id": 4,
<span>16</span>         "pid": 5,
<span>17</span>         "path": "/se/4901/mask/query"
<span>18</span>     },
<span>19</span> <span>        {
</span><span>20</span>         "id": 5,
<span>21</span>         "pid": 3,
<span>22</span>         "path": "/se/4901/mask"
<span>23</span>     },
<span>24</span> <span>    {
</span><span>25</span>         "id": 6,
<span>26</span>         "pid": 2,
<span>27</span>         "path": "/se/4902"
<span>28</span>     },
<span>29</span> <span>    {
</span><span>30</span>         "id": 7,
<span>31</span>         "pid": 6,
<span>32</span>         "path": "/se/4902/mask"
<span>33</span> <span>    }
</span><span>34</span> <span>]
</span><span>35</span> <span>JSON;
</span><span>36</span> 
<span>37</span> <span>$list</span> = json_decode(<span>$json</span>, <span>true</span><span>);
</span><span>38</span> 
<span>39</span> <span>var_dump</span>(list2Tree(<span>$list</span>));

结果：

<span>array</span>(4<span>) {
  [</span>"id"]=><span>
  int(</span>2<span>)
  [</span>"pid"]=><span>
  int(</span>1<span>)
  [</span>"path"]=>
  <span>string</span>(3) "/se"<span>
  [</span>"list"]=>
  <span>array</span>(2<span>) {
    [</span>0]=>
    <span>array</span>(4<span>) {
      [</span>"id"]=><span>
      int(</span>3<span>)
      [</span>"pid"]=><span>
      int(</span>2<span>)
      [</span>"path"]=>
      <span>string</span>(8) "/se/4901"<span>
      [</span>"list"]=>
      <span>array</span>(1<span>) {
        [</span>0]=>
        <span>array</span>(4<span>) {
          [</span>"id"]=><span>
          int(</span>5<span>)
          [</span>"pid"]=><span>
          int(</span>3<span>)
          [</span>"path"]=>
          <span>string</span>(13) "/se/4901/mask"<span>
          [</span>"list"]=>
          <span>array</span>(0<span>) {
          }
        }
      }
    }
    [</span>1]=>
    <span>array</span>(4<span>) {
      [</span>"id"]=><span>
      int(</span>6<span>)
      [</span>"pid"]=><span>
      int(</span>2<span>)
      [</span>"path"]=>
      <span>string</span>(8) "/se/4902"<span>
      [</span>"list"]=>
      <span>array</span>(1<span>) {
        [</span>0]=>
        <span>array</span>(4<span>) {
          [</span>"id"]=><span>
          int(</span>7<span>)
          [</span>"pid"]=><span>
          int(</span>6<span>)
          [</span>"path"]=>
          <span>string</span>(13) "/se/4902/mask"<span>
          [</span>"list"]=>
          <span>array</span>(0<span>) {
          }
        }
      }
    }
  }
}</span>

成功把列表转成了树