php:ツリー構造アルゴリズム 2

1 食品 18

+-------------------------------------- ------ +
|
2 果物 11 12 肉 17
| -+ + ----------+
| 3 赤 6 7 黄 10 13 牛肉 14 15 豚肉 16 | | |
4 Cherry 5 8 Banana 9

このようにして、ツリー構造全体を左右の値を通じてデータベースに保存できます。続行する前に、以下の編集されたデータ表を見てみましょう。


+-----------------------+-----+-----+
|親の名前 |
+----------+-----+-----+ +----------+-----+-----+
SQL では「left」と「right」に特別な意味があるため、「lft」と「rgt」を使用して左右のフィールドを表す必要があります。 さらに、この構造ではツリー構造を表すために「親」フィールドは必要なくなりました。つまり、次のようなテーブル構造であれば十分です。

+-----------+-----+-----+
lft | --------+-----+-----+
1 |
3 | |
| 4 | 5 |
12 | |
| 15 |
+----------+-----+-----+
これで、データベースからのデータ データを取得するには、たとえば、「フルーツ」項目の下にあるすべてのノードを取得する必要がある場合、次のようなクエリ ステートメントを作成できます。以下の結果。


+------------+-----+-----+
名前 |
-----------+-----+-----+ フルーツ 2 |
| 4 | 5 | 黄色 | 9 | --+
ほら、たった 1 つのクエリでこれらすべてのノードを取得できます。上記の再帰関数のようにツリー構造全体を表示できるようにするには、そのようなクエリを並べ替える必要もあります。ノードの左辺値でソートします:

SELECT * FROM Tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
残りの問題は、レベルのインデントを表示する方法です。

function display_tree($root)
{
// ルートノードの左右の値を取得
$result = mysql_query('SELECT lft, rgt FROM ツリー ' .'WHERE name="'.$root.'";');
$row = mysql_fetch_array($result); // 空の右辺値スタックを準備します
$right = array();

// ルート ポイントのすべての子孫ノードを取得します
$result = mysql_query('SELECT name, lft, rgt FROM Tree '.
'WHERE lft BETWEEN '.$row[ 'lft'].' AND '.
$row['rgt'].' ORDER BY lft ASC;'); // 各行を表示します ( $row = mysql_fetch_array( $result))
{
// スタックが 1 つある場合のみチェックします
if (count($right)>0)
{
// かどうかをチェックしますノードを Stack
の外に移動する必要があります while ($right[count($right)-1] {
array_pop($right)
}
}

// ノードの名前をインデントします
echo str_repeat(' ',count($right)).$row['name']."n"; 🎜> // このノードをスタックに追加します
$right[] = $row['rgt']
}
}
?>
上記を実行すると、取得する関数と再帰関数は同じ結果になります。ただ、データベース クエリが 2 つしかないため、新しい関数の方が高速になる可能性があります。 ノードのパスを知るのはさらに簡単です。Cherry のパスを知りたい場合は、その左右の値 4 と 5 を使用してクエリを作成します。

SELECT name FROM Tree WHERE lft 5 ORDER BY lft ASC; これにより、次の結果が得られます。
+----------------+

+----------------+ | 食べ物 |
|
|
+----------+
では、あるノードにはいくつの子孫ノードがあるでしょうか。それは非常に単純で、子孫の総数 = (rvalue - left value - 1)/2 子孫 = (right - left - 1) / 2 信じられませんか?自分で計算してください。この単純な式を使用すると、「フルーツ 2-11」ノードには 4 つの子孫ノードがある一方、「バナナ 8-9」ノードには子孫ノードがない、つまり親ノードではないことがすぐに計算できます。
すごくないですか？私はこの方法を何度も使っていますが、それでもやるたびに素晴らしい気分になります。

これは確かに良い方法ですが、左と右の値を持つこのようなデータ テーブルを作成するのに役立つ方法はありますか?もう 1 つの関数を紹介します。この関数は、名前と親構造を持つテーブルを、左と右の値を持つデータ テーブルに自動的に変換します。


function再構築_tree($parent, $left) {
// このノードの右の値は左の値 + 1
$right = $ left+1;

// このノードのすべての子を取得します
$result = mysql_query('SELECT name FROM Tree '.
'WHEREparent="'.$parent.'";' );
while ($row = mysql_fetch_array($result)) {
// 各ノードに対するこの関数の再帰実行
// このノードの子
// $right は現在の正しい値これは
//再構築関数によってインクリメントされます
$right =再構築_tree($row['name'], $right);
}

//
// このノードの子を処理したので、正しい値もわかります
mysql_query('UPDATE Tree SET lft='.$left.', rgt='.
$right.' WHERE name="'.$parent.'";');

// このノードの正しい値を返します + 1
return $right+1; }
?>
もちろん、この関数は再帰関数です。左と右の値を使用してツリーを再構築するには、ルート ノードからこの関数を実行する必要があります。 ,1);
この関数は少し複雑に見えますが、その機能はテーブルに手動で番号を付けるのと同じで、3 次元の多層構造を左右の値を持つデータ テーブルに変換します。