PHP RecursiveIteratorIterator và bộ lồng nhau

Question

Tôi có một bộ các đối tượng trong một hierachy. Có một nút "root" đầu và có nút con, có nút con, vv .. Tôi đang cố gắng lưu cấu trúc này vào một DB bằng cách sử dụng mô hình tập lồng nhau, trong đó mỗi "bên" của mỗi nút được đánh số để xác định hệ thống phân cấp, như trong Managing Hierarchical Data in MySQL:

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

vấn đề của tôi là tính trái và giá trị đúng. Tôi thường sử dụng RecursiveIteratorIterator để lặp qua phân cấp, nhưng tôi không thể tìm ra cách tính số mà không dùng đến hàm đệ quy phân tích biến chỉ mục theo tham chiếu.

Bất kỳ ý tưởng nào?

Có lẽ không sử dụng, nhưng đây là (không chính xác) mã Tôi hiện có:

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

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

Như bạn thấy, mà sẽ cung cấp cho một cái gì đó như thế này:

Node 
    Node 
    Node 

trái và giá trị phù hợp của:

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

Khi cần có:

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

Answer 1

I figured it out, đây là giải pháp (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; 
} 

Đây là sáng hơn phiên bản đơn giản của mã thực tế của tôi, vì nó chỉ lưu trữ " bên "giá trị trong một mảng riêng biệt, nhưng nó thể hiện nguyên tắc.

Ý tưởng cơ bản là bạn lưu trữ tất cả các nút cha (được theo dõi bởi giá trị độ sâu) trong một mảng và chỉ ghi các giá trị "trái" trong vòng lặp của bạn. Sau đó, khi độ sâu giảm nó có nghĩa là bạn đã sao lưu hệ thống phân cấp, vì vậy mảng cha được nối để loại bỏ những cái không còn phù hợp nữa, và chúng được lặp lại (ngược lại) thiết lập các giá trị "đúng". Cuối cùng, bạn phải lặp lại các bậc cha mẹ còn lại ở cuối.

Answer 2

Không thể giải quyết vấn đề này mà không cần đệ quy. Bạn cần một cái gì đó như sau:

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 
}