PHP数组 - 如何将1维数组转换为嵌套的多维数组？

Question

从MySQL(具有一个ID列和一个PARENT列表示层次关系的表)检索层次结构时,我将结果映射到枚举数组中,如下所示(对于此示例,数字是任意的):

Array ( [3] => Array ( [7] => Array () ), [7] => Array ( [8] => Array () ) )

通知3是7的父级,7是8的父级(这可以继续;并且任何父级可以有多个子级).

我想将此数组缩小为嵌套的多维数组,如下所示:

Array ( [3] => Array ( [7] => Array ( [8] => Array () ) ) )

也就是说,每个NEW id都会自动分配一个空数组.无论如何,任何ID的孩子都会被推入他们父母的阵列中.

请查看下图以进一步说明:

alt text http://img263.imageshack.us/img263/4986/array.gif

这可能会导致复杂的递归操作,因为我总是必须检查具有任何特定ID的父级是否已经存在(如果是,则将值推入其数组中).

是否有内置的PHP功能可以帮助我这个？你对如何构建这个有任何想法吗？对于它的价值,我使用它来构建wordpress中的导航栏(可以包含类别,子类别,帖子......基本上任何东西).

Answer 1

这个想法是你保留一个辅助数组，其中包含你找到的所有节点（父节点和子节点）。该数组的值是支持结果的引用。

这会在线性时间内构建树（array_key_exists 执行哈希表查找，平均时间为 O(1)）：

//table contains (id, parent)
$orig = array(
    11 => 8,
    7 => 3,
    8 => 7,
    99 => 8,
    16 => 8,
);

$childrenTable = array();
$result = array();

foreach ($orig as $n => $p) {
    //parent was not seen before, put on root
    if (!array_key_exists($p, $childrenTable)) {
        $childrenTable[$p] = array();
        $result[$p] = &$childrenTable[$p];
    }
    //child was not seen before
    if (!array_key_exists($n, $childrenTable)) {
        $childrenTable[$n] = array();
    }

    //root node has a parent after all, relocate
    if (array_key_exists($n, $result)) {
        unset($result[$n]);
    }

    $childrenTable[$p][$n] = &$childrenTable[$n];
}
unset($childrenTable);

var_dump($result);

给出

array(1) {
  [3]=>
  array(1) {
    [7]=>
    array(1) {
      [8]=>
      array(3) {
        [11]=>
        array(0) {
        }
        [99]=>
        array(0) {
        }
        [16]=>
        array(0) {
        }
      }
    }
  }
}

编辑：$childrenTable最后取消设置以清除参考标志。在实践中，您可能无论如何都想在函数内执行该操作。