使用一次性循环将平面数组转换为树

SO,

问题

假设我们有具有以下结构的平面数组：

$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);

-对于上面的数组来说是：

-[Root #1]
-[Root #2]
--[subroot 2-1]
---[__subroot 2-1/1]
--[subroot 2-2]
-[Root #3]
  

规格

所需的解决方案和输入数组都有一些限制：

• 输入数组是始终有效：这意味着它的结构总是可以重构为树结构。没有诸如负/非数字级别、没有无效级别结构等奇怪的事情。
• 输入数组可能很大，目前最大级别不受限制
• 解决方案must解决问题single循环，所以我们不能将数组分割成块，应用递归或以某种方式在数组中跳转。就简单了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;
}

-因为它足够长，我创建了一个sample使用和输出。

问题

正如您所看到的，我的解决方案很长，它依赖于引用和数组内部指针处理（例如end()), so 问题是:

可能还有其他更短、更清晰的方法来解决这个问题？它看起来像是一些标准问题，但我没有找到任何相应的解决方案（有一个类似的解决方案）question- 但有OP有确切的parent_id服从，而我没有）

关于您的问题的好处是您的输入始终格式正确，因此您的实际问题缩小到为每个节点查找子节点（如果存在）或为每个节点查找父节点（如果有）。后一个在这里更合适，因为我们知道如果该节点的级别大于 1，并且它是初始平面数组中位于该节点之上的最近节点，级别等于当前节点的级别减 1，则该节点有父节点。据此，我们可以只跟踪我们感兴趣的几个节点。更准确地说，每当我们找到具有相同级别的两个节点时，较早找到的节点不能有更多的子节点。

其实现将如下所示：

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]);
        }
    }
}

Demo