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

所以,

问题

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

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

问题是 – 转换该数组,使其成为一棵树.仅通过元素顺序和级别字段确定从属性.让我们将子元素定义为存储子节点的维度名称.对于上面的数组将是：

  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','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]

细节

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

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

可能还有其他 – 更短更清晰的方法来解决这个问题？它看起来像一些标准问题,但我没有找到任何相应的解决方案(有一个类似的question – 但OP有确切的parent_id从属关系,而我没有)

执行此操作将如下所示：

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

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!