PHP RecursiveIteratorIterator和嵌套集合

Question

我有一个层次结构的一组对象。有顶“根”节点具有子节点，这反过来有子节点等我试图使用嵌套集模型，其中每个每个节点的“侧面”的编号来定义这个结构保存到数据库该层次结构，以Managing Hierarchical Data in MySQL：

alt text http://dev.mysql.com/tech-resources/articles/hierarchical-data-4.png

我的问题是计算左边和右边的值。我通常使用RecursiveIteratorIterator遍历层次结构，但是我无法计算出数字，而无需通过引用来解析索引变量的递归函数。

任何想法？

这可能是没有用的，但是这是（不正确）的代码，我目前有：

$iterator = new RecursiveIteratorIterator(
    new Node_List(array($root)), 
    RecursiveIteratorIterator::SELF_FIRST); 

$i = 0;  
foreach ($iterator as $node) { 
    $node->left = ++$i; 
    $node->right = ++$i; 
} 

正如你所看到的，将给予这样的：

Node 
    Node 
    Node 

左，权值：

Node (1, 2) 
    Node (3, 4) 
    Node (5, 6) 

当他们应该是：

Node (1, 6) 
    Node (2, 3) 
    Node (4, 5) 

Answer 1

我想通了，这里的解决方案（simplifed）：

$iterator = new RecursiveIteratorIterator(
    new Site_Node_List(array($root)), 
    RecursiveIteratorIterator::SELF_FIRST); 

$sides = array(); 
$s = 0; 
$i = 0; 
$parents = array(); 
foreach ($iterator as $item) { 
    $js = array_splice($parents, $depth, count($parents), array($i)); 
    foreach (array_reverse($js) as $j) { 
     $sides[$j]['right'] = ++$s; 
    } 
    $sides[$i]['left'] = ++$s; 
    $i++; 
} 
foreach (array_reverse($parents) as $j) { 
    $sides[$j]['right'] = ++$s; 
} 

这是上午在我的实际代码的简化版本，它只是存储“边“的价值在一个单独的数组中，但它表明了原则。

其基本思想是将所有父节点（由深度值跟踪）存储在数组中，并且只在循环中写入“左”值。然后，当深度减少时，意味着你已经恢复了层次结构，所以父母数组拼接以去除不再相关的数组，并且将它们循环（反向）设置“正确”值。最后，你必须在最后循环其余的父母。

Answer 2

这也不是没有可能递归来解决这个问题。你需要的东西像下面这样：

function tag_recursive($node, &$number) { 
    $node->left = $number++; 
    foreach ($node->children as &$child) { 
     tag_recursive($child, $number); 
    } 
    $node->right = $number++; 
} 

function tag($node) { 
    $number = 1; 
    tag_recursive($node, $number); 
    // $number is now highest id + 1 
}