在最近的项目中，我需要从数据库中挑选出带有层级关系的数据，并根据记录的parent_id构建数据之间的父子关系，最终形成一个树状结构的父子孙关系结构，并用数组的形式保存起来。经过搜索和研究，最终找到了下方的算法代码，仅做参考。

首先，查询得到的数据以数组的形式返回：

array(
  array('id' => 5,'parent_id' => 0,...),
  array('id' => 9,'parent_id' => 0,...),
  array('id' => 12,'parent_id' => 5,...),
  array('id' => 19,'parent_id' => 5,...),
  array('id' => 21,'parent_id' => 0,...),
  array('id' => 23,'parent_id' => 12,...),
  array('id' => 24,'parent_id' => 12,...),
  array('id' => 26,'parent_id' => 23,...),
  array('id' => 29,'parent_id' => 9,...),
  array('id' => 31,'parent_id' => 12,...),
  ...
)

通过观察，我们可以发现顶级数组是由包含id,parent_id的数组组成的，这些数组之间存在着一定的父子关系，而且仅以parent_id的形式表现出来。现在，我们实际上想要得到下面的结果：

array(
  array(
    'id' => 5,
    'children' => array(
      array(
        'id' => 12,
        'children' => array(
          array(
            'id' => 23,
            'children' => array(
              array('id' => 26)
            )
          ),
          array('id' => 24),
          array('id' => 31)
        )
      ),
      array('id' => 19)
    )
  ),
  array(
    'id' => 9,
    'children' => array(
      array('id' => 29)
    )
  ),
  array('id' => 21),
  ...
)

也就是通过数组的形式，用一个children元素来包含该元素的子元素，并且层级分明。

那么如何来快速实现呢？我们通过下面一个函数来实现。

function array_tree($array) {
  $result = array();
  $tmp = array();
  foreach($array as $item) {
    if($item['parent_id'] == 0) {
      $i = count($result);
      $result[$i] = $item;
      $id = $item['id'];
      $tmp[$id] = &$result[$i];
    }
    else {
      $id = $item['id'];
      $parent_id = $item['parent_id'];
      $parent = $tmp[$parent_id];
      $i = count($parent['children']);
      $tmp[$parent_id]['children'][$i] = $item;
      $tmp[$id] = &$tmp[$parent_id]['children'][$i];
    }
  }
  return $result;
}

上面我用红色标注了&符号，具体是什么意思，及其原理又是怎么实现的呢？

&引用是PHP中非常特殊的一种变量引用方式。我们不过多深入的去讲解，简单的讲，就是：

当$b = &$a时，$b和$a同时引用同一个内容（指针指向同一块内存），无论$a或$b谁发生变化，这个内容都会发生变化，进而呈现为$a和$b保持同步的变化。

要解除这种引用，只有先将引用释放。可是并没有一种运算可以达到释放引用的目的，所以我们可以通过unset($a)的方式，也可以通过重新引用另外一个变量来释放原来的引用（但是又和其他变量引用，比如$b = &$c）。

这时，我们再来分析上面的实现函数。

$tmp[$id] = &$result[$i];

这一句保证了当无论$tmp[$id]还是$result[$i]发生变化，都会让另外一个值同时发生变化。而

$tmp[$parent_id]['children'][$i] = $item;

实际上导致$result[$parent_id]发生了变化。

用我们上面的数据进行演示验证：

[0] => array('id' => 5,'parent_id' => 0,...)

$result[0] = array('id' => 5,'parent_id' => 0,...)

$tmp[5] = &$result[0]  // 第一个&出现了

$tmp[5] = array('id' => 5,'parent_id' => 0,...)  // 内部结果

而当执行往下执行，碰到array('id' => 12,'parent_id' => 5,...)时，发生了：

[2]=> array('id' => 12,'parent_id' => 5,...)

$tmp[5]['children'][0] = array('id' => 12,'parent_id' => 5,...) // ①

由于&引用的关系，所以实际上

$result[0]['children'][0] = array('id' => 12,'parent_id' => 5,...) // 内部结果

这个时候$temp[5]是一个已经包含children子元素的二维数组，如果往下执行遇到array('id' => 23,'parent_id' => 12,...)时，你就会发现

[5]=> array('id' => 23,'parent_id' => 12,...)

$tmp[12]['children'][0] = array('id' => 23,'parent_id' => 12,...)

$result[?]['children'][0] = array('id' => 23,'parent_id' => 12,...) // 我们以为会发生的结果，其实并没有发生

因为没有找到一个$tmp[12] = & $result[?]，也就是说没有一个与$tmp[12]对应的引用，$tmp[12]的变化不会引起其他任何值的变化，$tmp[12]这个家伙会在返回值中丢失（因为返回值是$result）。

而$tmp[$id] = &$tmp[$parent_id]['children'][$i];这一句起到了关键性作用。加上这一句之后，我们再来跑一遍array('id' => 23,'parent_id' => 12,...)这个元素。

[2]=> array('id' => 12,'parent_id' => 5,...)

$tmp[5]['children'][0] = array('id' => 12,'parent_id' => 5,...)  // 重新从①开始演示

$result[0]['children'][0] = array('id' => 12,'parent_id' => 5,...) // 内部结果

$tmp[12] = &$tmp[5]['children'][0]  // 第二个&出现了

[5]=> array('id' => 23,'parent_id' => 12,...)

$tmp[12]['children'][0] = array('id' => 23,'parent_id' => 12,...)

由于第二个&引用的原因，实际上发生了：

$tmp[5]['children'][0]['children'][0] = array('id' => 23,'parent_id' => 12,...) // 内部结果

$result[0]['children'][0]['children'][0] = array('id' => 23,'parent_id' => 12,...) // 内部结果

这个时候你可能已经看出了端倪。父子关系变成了 5 > 12 > 23，而这组关系，全部存储在了id=5的这个顶级元素中，以多重的children元素实现了父子孙结构。

如此循环往复，你就会发现，无论你的父子关系多深，这个函数都能准确的构建对应的父子关系，最终形成树形结构存储在$result中，将其返回。

该算法有一个问题，就是要求原始数组中，parent_id必须出现在该元素之前，否则将导致该元素无法加入到某个元素的children中去。

2015-11-16 5932