使用一次性循环将平面数组转换为树 [英] Transform flat array to tree with one-time loop
问题描述
所以，
问题
假设我们有以下结构的平面数组:
$array = [['级别'=>1，'名称'=>'根#1']，['级别'=>1，'名称'=>'根 #2'],['级别'=>2，'名称'=>'子根 2-1'],['级别'=>3，'名称'=>'__subroot 2-1/1'],['级别'=>2，'名称'=>'子根 2-2'],['级别'=>1，'名称'=>'根 #3']];问题是 - 转换该数组，使其成为一棵树.从属仅由元素顺序和 level 字段确定.让我们将 children 定义为用于存储子节点的维度名称.对于上面的数组，将是:
多一点澄清，如果谁是谁的父母不明显:下面的代码可以很容易地形象化想法:
函数可视化($array){foreach($array 作为 $item){echo(str_repeat('-', $item['level']).'['.$item['name'].']'.PHP_EOL);}}可视化($数组)；-对于它上面的数组:
<前>-[根 #1]-[根 #2]--[子根2-1]---[__subroot 2-1/1]--[子根2-2]-[根 #3]规格
所需解和输入数组都有一些限制:
- 输入数组总是有效:这意味着它的结构总是可以重构为树结构.没有负/非数字级别，没有无效级别结构等奇怪的事情
- 输入数组可能很大，目前，最大级别不受限制
- 解决方案必须用single循环解决问题，这样我们就不能将数组拆分成块、应用递归或以某种方式在数组内跳转.只是简单的
foreach(或另一个循环 - 没关系)，只有一次，每个元素都应该被一个一个地处理.
我的方法
目前，我有堆栈解决方案.我正在处理引用并维护将在当前步骤写入的堆栈的当前元素.即:
function getTree(&$array){$级别 = 0;$tree = [];$stack = [&$tree];foreach($array 作为 $item){if($item['level']>$level)//为新项目扩展堆栈{//如果有子元素，将最后添加到堆栈中:$top = key($stack);如果(计数($stack[$top])){结束($stack[$top])；$stack[] = &$stack[$top][key($stack[$top])];}//添加 ['children'] dim 到栈顶元素结束($堆栈)；$top = key($stack);$stack[$top]['children'] = [];$stack[] = &$stack[$top]['children'];}while($item['level']<$level--)//弹出到某个级别{//两次:一次用于最后一个指针，一次用于 ['children'] dimarray_pop($stack);array_pop($stack);}//将项目添加到堆栈顶部:结束($堆栈)；$stack[key($stack)][] = $item;$level = $item['level'];}返回 $tree;}-由于时间够长，我创建了一个示例 使用&输出.
问题
正如你所看到的，我的解决方案很长，它依赖于参考资料 &数组内部指针处理(例如end())，所以问题是:
可能还有其他更短、更清晰的方法来解决这个问题吗?它看起来像一些标准问题，但我没有找到任何相应的解决方案(有一个类似的 问题 - 但 OP 有确切的 parent_id 从属关系，而我没有)
你的问题的好处是你的输入总是格式正确，所以你的实际问题缩小到为每个节点寻找子节点(如果它们存在)或找到父节点对于每个节点，如果它有一个.后一个在这里更合适，因为我们知道如果节点的级别大于一，则该节点有父节点，并且它是初始平面数组中距离它最近的节点，级别等于当前节点的级别减一.据此，我们可以只跟踪我们感兴趣的几个节点.更准确地说，每当我们找到两个级别相同的节点时，较早找到的节点不能有更多的子节点.
它的实现看起来像这样:
function buildTree(array &$nodes) {$activeNodes = [];foreach ($nodes as $index => &$node) {//如果您不希望没有子节点的节点为空 ['children'] 暗淡，则删除$node['children'] = [];$level = $node['level'];$activeNodes[$level] = &$node;如果 ($level > 1) {$activeNodes[$level - 1]['children'][] = &$node;取消设置($nodes[$index])；}}}SO,
The problem
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',
),
)
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]
Specifics
There are some restrictions both for desired solution and input array:
- 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.
My approach
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;
}
-since it's long enough, I've created a sample of usage & output.
The question
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:
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.
Implementation of this will look like this:
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屋！
