5

階層内に一連のオブジェクトがあります。最上位の「ルート」ノードがあり、子ノードがあり、子ノードなどがあります。ネストされたセットモデルを使用して、この構造をDBに保存しようとしています。各ノードの各「側」は定義するために番号が付けられていますMySQL での階層データの管理のように、階層:

代替テキスト
(ソース: mysql.com )

私の問題は、左右の値を計算することです。私は通常、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)
4

2 に答える 2

4

私はそれを理解しました、ここに解決策があります（簡略化）：

$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;
}

これは、「サイド」値を別の配列に格納するだけなので、実際のコードの単純化されたバージョンですが、原理を示しています。

基本的な考え方は、すべての親ノード (深さの値で追跡) を配列に格納し、「左」の値のみをループに書き込むことです。次に、深さが減少すると、階層を上に戻ったことを意味するため、親配列は関連しなくなったものを削除するために接合され、「正しい」値を設定して (逆に) ループされます。最後に、最後に残りの親をループする必要があります。

于 2009-02-05T23:08:19.900 に答える
0

この問題は、再帰なしでは解決できません。次のようなものが必要です。

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
}
于 2009-02-05T21:43:10.353 に答える