Convert the list containing the parent ID into a tree, and the id list into a tree_PHP tutorial

Convert the list containing the parent ID into a tree, and the id list into a tree

We know that the database generally saves the tree in the form of a list (id, pid). How to extract this tree? The simplest method is to look up the table in a loop based on pid. But there is no doubt that this will generate huge database query overhead.

The generally recommended method is to find all relevant data at once, but this involves a problem, how to quickly build a tree.

I always thought that this was a complex operation that required at least one recursion, and the time complexity would not be O(n).

Some time ago, I had a work requirement and needed to solve this problem. I thought about it carefully and found that this problem can be solved through a single-layer loop, as follows:

<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> }

Test it:

<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>));

Result:

<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>

Successfully converted the list into a tree

http://www.bkjia.com/PHPjc/1102845.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/1102845.htmlTechArticleConvert the list containing the parent ID into a tree, and the id list into a tree. We know that the database is generally a list (id , pid) to save the tree. How to extract this tree? The easiest way is to...