logo标签列表

将扁平数组转换为树形结构，只需进行一次循环

phparraystree
6

那么，

问题

假设我们有一个具有以下结构的扁平数组：

$array = [
  ['level'=>1, 'name' => 'Root #1'],
  ['level'=>1, 'name' => 'Root #2'],
  ['level'=>2, 'name' => 'subroot 2-1'],
  ['level'=>3, 'name' => '__subroot 2-1/1'],
  ['level'=>2, 'name' => 'subroot 2-2'],
  ['level'=>1, 'name' => 'Root #3']
];

问题是 - 要将该数组转换为树形结构。层次关系仅由元素顺序和“level”字段决定。让我们将“children”定义为存储子节点的维度名称。对于上述数组，这将是： 
array (
  array (
    'level' => 1,
    'name' => 'Root #1',
  ),
  array (
    'level' => 1,
    'name' => 'Root #2',
    'children' =>
    array (
      array (
        'level' => 2,
        'name' => 'subroot 2-1',
        'children' =>
        array (
          array (
            'level' => 3,
            'name' => '__subroot 2-1/1',
          ),
        ),
      ),
      array (
        'level' => 2,
        'name' => 'subroot 2-2',
      ),
    ),
  ),
  array (
    'level' => 1,
    'name' => 'Root #3',
  ),
)
更多解释：如果不明确谁是谁的父节点，请看以下代码，它可以很容易地展示这个思路：
function visualize($array)
{
   foreach($array as $item)
   {
      echo(str_repeat('-', $item['level']).'['.$item['name'].']'.PHP_EOL);
   }
}
visualize($array);

-对于上面的数组，它是这样的：

-[根 #1]
-[根 #2]
--[子根 2-1]
---[__子子根 2-1/1]
--[子根 2-2]
-[根 #3]

具体要求

对于期望解决方案和输入数组都有一些限制：

  • 输入数组总是有效的：这意味着其结构始终可以重构为树形结构。没有负数/非数字级别，没有无效的级别结构等奇怪的事情。
  • 输入数组可能很大，目前最大级别没有限制
  • 解决方案必须使用单个循环来解决问题，因此我们不能将数组拆分为块，应用递归或以某种方式跳转到数组中。只需简单的foreach（或另一个循环-无关紧要），每个元素依次处理即可。

我的方法

目前，我使用堆栈实现了解决方案。我正在使用引用并维护堆栈的当前元素，在当前步骤中将写入该元素。也就是说：

function getTree(&$array)
{
   $level = 0;
   $tree  = [];
   $stack = [&$tree];
   foreach($array as $item)
   {
      if($item['level']>$level) //expand stack for new items
      {
         //if there are child elements, add last to stack:
         $top = key($stack);
         if(count($stack[$top]))
         {
            end($stack[$top]);
            $stack[] = &$stack[$top][key($stack[$top])];
         }
         //add ['children'] dim to top stack element
         end($stack);
         $top = key($stack);
         $stack[$top]['children'] = [];
         $stack[] = &$stack[$top]['children'];
      }
      while($item['level']<$level--) //pop till certain level
      {
         //two times: one for last pointer, one for ['children'] dim
         array_pop($stack);
         array_pop($stack);
      }
      //add item to stack top:
      end($stack);
      $stack[key($stack)][] = $item;
      $level = $item['level'];
   }
   return $tree;
}

-既然内容很长，我已经创建了一个使用和输出示例。

问题

正如您所看到的，我的解决方案相当冗长，并且依赖于引用和数组内部指针处理（例如 end()等），因此问题是：

可能有其他更短，更清晰的方法来解决这个问题吗？ 看起来像一些标准问题，但我没有找到任何相应的解决方案（有一个类似的问题 - 但在那里 OP 具有确切的parent_id隶属性而我没有）

2个回答
3
你的问题好在输入总是格式正确的，因此你实际上需要做的只是找到每个节点的子节点（如果有）或者找到每个节点的父节点（如果有）。后者更适合这里，因为我们知道如果一个节点的级别大于一且是初始扁平数组中级别等于当前节点级别减一的最近节点，则该节点有父节点。根据这个规则，我们可以跟踪我们感兴趣的几个节点。更确切地说，每当我们找到两个级别相同的节点时，先找到的节点就不能有更多的子节点。
具体实现如下：
function buildTree(array &$nodes) {
    $activeNodes = [];

    foreach ($nodes as $index => &$node) {
        //remove if you don't want empty ['children'] dim for nodes without childs
        $node['children'] = [];
        $level = $node['level'];
        $activeNodes[$level] = &$node;

        if ($level > 1) {
            $activeNodes[$level - 1]['children'][] = &$node;
            unset($nodes[$index]);
        }
    }
}

演示

1
使用递归实现的代码：
 function buildTreeHelper(&$array, $currentLevel = 1)
 {
     $result = array();
     $lastIndex = 0;
     while($pair = each($array)) {
         list(, $row) = $pair;
         $level = $row['level'];
         if ($level > $currentLevel) {
             $result[$lastIndex]['children'] = buildTreeHelper($array, $level);
         } else if ($level == $currentLevel) {
             $result[++$lastIndex] = $row;
         } else {
             prev($array); // shift back
             break;
         }
     }
     return $result;
 }

 function buildTree($array)
 {
     reset($array);
     return buildTreeHelper($array);
 }

 $array = [
  ['level'=>1, 'name' => 'Root #1'],
  ['level'=>1, 'name' => 'Root #2'],
  ['level'=>2, 'name' => 'subroot 2-1'],
  ['level'=>3, 'name' => '__subroot 2-1/1'],
  ['level'=>2, 'name' => 'subroot 2-2'],
  ['level'=>1, 'name' => 'Root #3']
];

 print_r(buildTree($array));
谢谢你。即使它不符合我的要求，它仍然很有趣。然而，在清理了我的函数代码后，我采取了一些措施 - 它们在1E6迭代计数和数组方面都具有相同的时间，这是在问题中指定的（我的版本总共70秒，而你的版本为74.5秒）。我还在简单的数组上进行了测试（所有级别都为1），并获得了类似的结果（我的版本为34秒，而你的版本为39秒）。这是预期的，因为两个函数具有相同的大O估计。 - Alma Do
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接