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

Question

所以,

问题

假设我们有平面阵列,结构如下:

$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]

细节

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

• 输入数组始终有效:这意味着它的结构总是可以重构为树结构.没有像负数/非数字级别那样奇怪的东西,没有无效的级别结构,e tc
• 输入数组可能很大,目前最大级别不受限制
• 解决方案必须使用单循环解决问题,因此我们不能将数组拆分为块,应用递归或以某种方式在数组内跳转.只是简单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从属关系,而我还没有)

Answer 1

关于您的问题的好处是您的输入始终格式正确，因此您的实际问题缩小到为每个节点查找子节点（如果存在）或为每个节点查找父节点（如果有）。后一个在这里更合适，因为我们知道如果该节点的级别大于 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]);
        }
    }
}

演示