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

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 的父级是否已经存在(如果存在，将值压入其数组)。 p>

是否有内置的 php 函数可以帮助我解决这个问题？您知道如何构建它吗？对于它的值(value)，我正在使用它在 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 以清除引用标志。在实践中，您可能无论如何都想在函数内部执行操作。