0

如何从 PHP 中的数组构建树，知道构建树需要遵循的规则？

我在代码中没有任何特定的地方可以找到真正错误的地方
无论如何，这些问题可能与我反复使用的按引用传递有关。
我没有使用递归，因为速度在这里真的很重要。根据输入数组的规则（我可以完全控制它们），这是可能的，而且速度更快，无需递归。

它是如何工作的：当你遍历数组时，每个元素的 ['start_order'] 是一个比前一个 ['start_order'] 更大的数字。
每次下一个元素的 ['start_order'] 大于此元素的 ['start_order'] 并且下一个元素的 ['end_order'] 小于此元素的 ['end_order']，则该元素是该元素的子元素.
在这一步之后，我必须找到该元素的所有子元素（我刚刚发现它是这个元素的子元素的那个）。

这是我的代码。

<?php
ksort($treeArray);
$tree = array();
$stack = array();
reset($treeArray);
$currentParent = &$treeArray[key($treeArray)];
$tree[] = &$treeArray[key($treeArray)];

while(next($treeArray) !== false){

    if(current($treeArray)['start_order'] <= $currentParent['end_order']){
        if(current($treeArray)['end_order'] <= $currentParent['end_order']){
            // There's a child of the previous

            // push the new parent
            $stack[] = $currentParent;

            if(!isset($currentParent['children'])){
                $currentParent['children'] = array();
            }
            $currentParent['children'][] = &$treeArray[key($treeArray)];
            $currentParent = current($treeArray);

        }else{
            // Supposed not to happen. Log the problem.
        }
    }else /* if(current($treeArray)['start_order'] > $currentParent['end_order']) */{
        // Pop the child here, there are no more children.
        if(($popedElement = array_pop($stack)) === NULL){
            $tree[] = $currentParent;
        }else{
            $popedElement['children'][] = &$treeArray[key($treeArray)];
            $stack[] = $popedElement;
            $currentParent = current($treeArray);
        }
    }
}

?>

例子：

它的输入数组在结构上可以是这样的：

[1][child1][child1child1][child2][child2child1][child2child2][child2child3][2][child2child1]

解析为这棵树：

[1]
    [child1]
        [child1child1]
    [child2]
        [child2child1]
        [child2child2]
        [child2child3]
[2]
    [child2child1]

并且不要忘记这个顺序保持不变。[child2child3] 从未出现在 [child2child2] 之前，[2] 从未出现在 [1] 之前。在这个类比中，几乎就像在处理 XML 时一样。

4

1 回答 1

0

在这里发现了问题。问题与我在尝试解决此问题时如何处理传递引用有关。

这是解决方案：

$tree[] = &$treeArray[key($treeArray)];
$currentParent = &$treeArray[key($treeArray)];
next($treeArray);

while(current($treeArray) !== false){

    if(current($treeArray)['start_order']['start_position'] <= $currentParent['end_order']['end_order']){
        if(current($treeArray)['end_order']['end_order'] <= $currentParent['end_order']['end_order']){
            // There's a child of the previous

            // push the new parent
            $stack[] = &$currentParent;

            $currentParent['children'][] = &$treeArray[key($treeArray)];

            $currentParent = &$treeArray[key($treeArray)];
        }else{
            // Supposed not to happen. Log the problem.
        }
        next($treeArray);
    }else /* if(current($treeArray)['start_order']['start_position'] > $currentParent['end_order']['end_order']) */{
        // Close previous element here. There are no more children.

        if(end($stack) === false){
            $currentParent = &$treeArray[key($treeArray)];
            $tree[] = &$treeArray[key($treeArray)];

            next($treeArray);
        }else{              
            $currentParent = &$stack[key($stack)];
            unset($stack[key($stack)]);
        }
    }
}

主要问题实际上是传递引用，它在 PHP 中与在 C 中不同。
为了解决这个问题，我无法同时使用 push 或 pop php 函数：
The push because the $var[] operator is更快并使用该功能。
弹出，因为它的返回是我之前推送的内容的副本，而不是我推送的实际元素。

Additionally, all variable assignments have to be explicitly made by reference (using the & character), so using current() for assignment is out of the question, instead I need to use the key() function like I did.

I also had a small but important bug that forced me to change the "while" instruction. It now contains current() instead of next(). That's only because after the pop of the stack I mustn't move to the next element. I need to do another iteration before I move to the next one. This solves the bad nesting generated when there are multiple tags closing in the same place.

Please note that this code is not optimized for speed.

于 2012-11-04T12:25:33.747 回答