平变换数组树一次性循环 [英] Transform flat array to tree with one-time loop
问题描述
SO，
问题
假设我们有以下结构平面数组：
Suppose we have flat array with following structure:
$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']
];
问题是 - 变换数组所以它会变成一棵树。居次只与元素的顺序和级别字段确定。让我们来定义孩子作为维度的存储子节点的名称。对于数组以上，这将是：
The issue is - transform that array so it will became a tree. Subordination is determined only with elements order and level field. Let's define children as a name of dimension for storing child nodes. For array above that will be:
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',
),
)
一个多一点说明，如果不是明显的谁是谁的家长：以下code可以轻松地可视化的想法：
A little more clarifications, if it's not obvious who is parent for who: following code could easily visualize idea:
function visualize($array)
{
foreach($array as $item)
{
echo(str_repeat('-', $item['level']).'['.$item['name'].']'.PHP_EOL);
}
}
visualize($array);
- 用于阵列上面是：
-for array above it's:
-[Root #1]
-[Root #2]
--[subroot 2-1]
---[__subroot 2-1/1]
--[subroot 2-2]
-[Root #3]
具体细节
有既为期望的解决方案和输入数组一些限制：
There are some restrictions both for desired solution and input array:
- 输入数组的总是有效的：这意味着它的结构总是可以重构为树结构。没有这样奇怪的事情负/非数字的水平，没有无效层次结构，电子T.C。
- 输入数组可以是巨大的，目前，最高水平不限
- 解决方案必须解决与单循环的问题，所以我们不能拆分阵列块，应用递归或数组中跳莫名其妙。只是简单的
的foreach（或其他循环 - 这并不重要），只有一次，每个元素一个接一个的处理方式
- Input array is always valid: that means it's structure can always be refactored to tree structure. No such weird things as negative/non-numeric levels, no invalid levels structure, e t.c.
- Input array can be huge and, currently, maximum level is not restricted
- Solution must resolve a matter with single loop, so we can not split array to chunks, apply recursion or jump within array somehow. Just simple
foreach(or another loop - it does not matter), only once, each element one-by-one should be handled.
我的做法
目前，我有堆栈的解决方案。我与引用工作，并保持到写作将在当前步骤完成栈的当前元素。这就是：
Currently, I have solution with stack. I'm working with references and maintaining current element of stack to which writing will be done at current step. That is:
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;
}
- 由于它足够长的时间，我创建的使用和放大器的样品;输出。
问题
正如你所看到的，我的解决方案是很长，它依赖于引用和放大器;数组内部指针处理（诸如端（）），这样的问题是
As you can see, my solution is quite long and it relies on references & array internal pointer handling (such things as end()), so the question is:
可能还有其他的 - 来解决这个问题更短和更清晰的方式？它看起来像一些标准的问题，但我还没有发现任何相应的解决方案（有一个类似的问题 - 但有OP具有确切 PARENT_ID 从属关系，而我却没有）
May be there are other - shorter and clearer ways to resolve this issue? It looks like some standard question, but I've not found any corresponding solution (there is one similar question - but there OP has exact parent_id subordination while I have not)
推荐答案
有关问题的好处是，你的输入总是格式正确因此您实际的问题是缩小到寻找孩子的每一个节点，如果他们存在或发现父母对于每个节点，如果它有一个。后者更适合在这里，因为我们知道，节点具有父，如果其电平超过一个并且它是在它上面有电平初始平面阵列等于当前节点减一水平的最近的节点。根据这一点，我们可以只跟踪上我们感兴趣的几个节点。更确切地说，每当我们发现与同级别的两个节点，被发现较早不能有更多的孩子的节点。
The good thing about your problem is that your input is always formatted properly so your actual problem is narrowed down to finding children for each node if they exist or finding parent for each node if it has one. The latter one is more suitable here, because we know that node has parent if its level is more than one and it is the nearest node above it in initial flat array with level that equals level of current node minus one. According to this we can just keep track on few nodes that we are interested in. To be more exact whenever we find two nodes with the same level, the node that was found earlier can't have more children.
本实施将是这样的：
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]);
}
}
}
这篇关于平变换数组树一次性循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
