根据父/子关系对数组值进行排序

Question

我正在尝试对数组进行排序,以确保任何项的父项始终存在于数组中.例如:

Array
(
    [0] => Array
        (
            [0] => 207306
            [1] => Bob
            [2] => 
        )

    [1] => Array
        (
            [0] => 199730
            [1] => Sam
            [2] => 199714
        )

    [2] => Array
        (
            [0] => 199728
            [1] => Simon
            [2] => 207306
        )

    [3] => Array
        (
            [0] => 199714
            [1] => John
            [2] => 207306
        )

    [4] => Array
        (
            [0] => 199716
            [1] => Tom
            [2] => 199718
        )

    [5] => Array
        (
            [0] => 199718
            [1] => Phillip
            [2] => 207306
        )

    [6] => Array
        (
            [0] => 199720
            [1] => James
            [2] => 207306
        )

)

在上面的数组中,这个"失败",因为[1] [2](Sam)还不存在,[4] [2](Tom)也没有.

在这种情况下,正确的输出将是,因为Sam和Tom的父母在它们出现在数组中之前已经存在:

Array
(
    [0] => Array
        (
            [0] => 207306
            [1] => Bob
            [2] => 
        )

    [1] => Array
        (
            [0] => 199714
            [1] => John
            [2] => 207306
        )


    [2] => Array
        (
            [0] => 199730
            [1] => Sam
            [2] => 199714
        )

    [3] => Array
        (
            [0] => 199728
            [1] => Simon
            [2] => 207306
        )


    [4] => Array
        (
            [0] => 199718
            [1] => Phillip
            [2] => 207306
        )


    [5] => Array
        (
            [0] => 199716
            [1] => Tom
            [2] => 199718
        )

    [6] => Array
        (
            [0] => 199720
            [1] => James
            [2] => 207306
        )

)

我找到了一个答案/sf/answers/907298031/非常接近,但它似乎只有一个深度(即只有一个父级),而在我的情况下可能有1或10个级别深层次的.

如何对数组进行排序,以便除非其父元素在它之前已经存在,否则不会出现任何值？

Answer 1

这将简单地命令数组(在O(n)中)首先放置所有没有父项的数组,然后迭代地将其父项已经在数组中,直到没有子项将当前元素作为父项.

# map the children by parent
$parents = ['' => []];
foreach ($array as $val) {
    $parents[$val[2]][] = $val;
}
# start with those with no parent
$sorted = $parents[''];
# add the children the current nodes are parent of until the array is empty
foreach ($sorted as &$val) {
    if (isset($parents[$val[0]])) {
        foreach ($parents[$val[0]] as $next) {
            $sorted[] = $next;
        }
    }
}

此代码需要PHP 7,它可能无法在某些情况下工作,PHP 5下-为PHP 5的兼容性,你将不得不交换foreach ($sorted as &$val)用for ($val = reset($sorted); $val; $val = next($sorted)):

# a bit slower loop which works in all versions
for ($val = reset($sorted); $val; $val = next($sorted)) {
    if (isset($parents[$val[0]])) {
        foreach ($parents[$val[0]] as $next) {
            $sorted[] = $next;
        }
    }
}

现场演示:https://3v4l.org/Uk6Gs

Answer 2

这种方法怎么样：

创建一个空数组result。

循环遍历数组，仅取出 [2] 为空的项目并将其插入到result.

完成此循环后，您可以在 -loopforeach内使用 -Loop while。使用-Loop，您可以从数组中foreach取出每个项目，其中 [2] 已经是 的一部分。只要你的数组包含任何东西，你就可以这样做。result

$result = array();
$result[''] = 'root';

while(!empty($yourArray)){
  foreach($yourArray as $i=>$value){
    if(isset($result[$value[2]])){
      // use the next line only to show old order
      $value['oldIndex'] = $i;
      $result[$value[0]] = $value;
      unset($yourArray[$i]);
    }
  }
}

unset($result['']);

PS：在遍历数组时删除数组的一部分可能会遇到麻烦。如果你这样做...尝试解决这个问题:)

PPS：如果您的数组有未解决的循环或没有父级的子级，请考虑中断条件。