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 
}