編集：わかりました、私はこれをもう少し調べました。命名法に混乱があったと思います。data structure for a transveral treeあなたはPHPでを探していません。PHPのデータ構造としてツリーを使用し、。と呼ばれるメソッドを使用してそのツリーからデータを回復したいとしますmodified preorder tree traversal algorithm。
引用：
When working with a tree, we work from left to right, one layer at a time, descending to each node's children before assigning a right-hand number and moving on to the right. This approach is called the modified preorder tree traversal algorithm.
これは、PHPとMySQLで階層データを保存することについてです。PHPでは、単純なツリーを使用できます。問題は、MySQLであるフラットデータベースにツリーを格納するのは簡単ではないということです。1つのオプションは、PHPを取得し、そこから隣接リストを取得することです。これは基本的に、各アイテムとその親のリストです。このやり方にはいくつかの欠点があります。
もう1つの方法は、階層データから作成できるネストされたセットを記述するPHPツリーから情報を抽出することです。PHPツリーからこの情報を取得するには、変更されたプレオーダーツリートラバーサルアルゴリズムを使用する必要があります。これは、ツリーから特定の情報を抽出するために、ツリーを上下に実行する方法です。
隣接リストモデルを使用する場合でも、変更されたプレオーダーツリートラバーサルを使用して情報を取得する場合でも、まったく同じPHPツリーを使用します。違いは、ツリーから情報を取得する方法と、MySQLに情報を保存する方法になります。MySQLから情報を抽出する方法のコードは、引用したページにすでにあります。PHPとMySQLの間でデータを同期するには、そのページで説明されているMySQL手法とPHPツリークラスを使用する必要があります。
このために、ツリーを格納するクラスをPHPで作成しました。ノードを使用します。各ノードから完全なサブツリーにアクセスできるため、各ノードは完全なツリーのルートと考えることができます。ノードをツリーから分離する方が簡単で、オーバーヘッドも少なくなります。
クラスの重要な部分はshowAdjacencyメソッドです。これにより、変更されたプレオーダーツリートラバーサルを使用してツリーが実行され、名前ごとにlftとrgtの数量が表示され、データをネストされたセットとしてMySQLに保存できます。
ツリーを表示して視覚化することもできます。このクラスには削除メソッドがありません。これを実装するときは、削除されたノードの子をノードの親に渡す必要があります。多分後でそれをします。
投稿の下部にクラス全体を含めますが、変更されたプレオーダーツリートラバーサルのデータを取得する方法は次のとおりです。
// The modified preorder tree traversal.
private function showAdjacency($root, $spaces)
{
// Print the data first
if ($root)
{
// On the way down the tree, we get lft.
$left = ++$spaces;
foreach( $root->next as $child)
{
if ($child)
{
$spaces = $this->showAdjacency($child, $spaces);
}
}
}
// On the way back up, we get rgt.
$right = ++$spaces;
echo "$left - $right - $root->data <br/>";
return $spaces;
}
データベースとの同期に使用する配列に$root->data、$ rgt、および$lftを格納できることは明らかです。
これがクラス全体です。クラスの後、リンク先のページのサンプルデータを使用してツリーを作成し、lft値とrgt値、およびツリーの視覚化を出力します。
コードパッドでコードを実行できます
<?php
// Class defintions and methods:
// It's easier to use separate nodes. Each node still points to an entire and complete subtree.
class Node
{
public $data;
public $next = array();
}
// A first try at creating a tree with any number of branches from its nodes
// by Peter Ajtai - feel free to use and modify
class Tree
{
// The root
private $root;
public function __construct()
{
$this->root = NULL;
}
// The public wrapper.
// This is needed because we must start the recursive functions
// at the root, and we do not want to give public access to root.
// I am not familiar w overloading in PHP, maybe __set should be used for this
public function insertPub($data, $parent)
{
$root =& $this->root;
$this->insert($root, $data, $parent);
}
private function insert(&$root, $data, $parent)
{
// Create the root of the entire tree if no parent is passed in
if (!$root && !$parent)
{
$root = new Node;
$temp =& $root;
$temp->data = $data;
// Create space for next insertion
$temp->next[] = NULL;
} else if ($root->data == $parent)
{
// Add data as a child if we're at the parent, and we're done.
// Find the empty node to insert at
foreach($root->next as &$child)
{
// Insert at the first (and only) NULL
if (!$child)
{
$child = new Node;
$temp =& $child;
$temp->data = $data;
// Create space for next insertion
$temp->next[] = NULL;
}
}
// Create space for the next insertion
$root->next[] = NULL;
} else
{
// Keep searching for the parent as default behavior.
foreach($root->next as $child)
{
if ($child)
{
$this->insert($child, $data, $parent);
}
}
}
}
// Public wrapper for the display function.
public function showAdjPub()
{
echo "The neighbors:<br/><br/>";
$root =& $this->root;
$this->showAdjacency($root, 0);
echo "<br/>";
}
// The display function.
private function showAdjacency($root, $spaces)
{
// Print the data first
if ($root)
{
$left = ++$spaces;
foreach( $root->next as $child)
{
if ($child)
{
$spaces = $this->showAdjacency($child, $spaces);
}
}
}
$right = ++$spaces;
echo "$left - $right - $root->data <br/>";
return $spaces;
}
// Public wrapper for the display function.
public function showAllPub()
{
echo "The tree:<br/><br/>";
$root =& $this->root;
$this->showAll($root, 0);
echo "<br/>";
}
// The display function.
private function showAll($root, $spaces)
{
// Print the data first
if ($root)
{
for ($i=0; $i < $spaces; ++$i)
echo "---> ";
echo "$root->data <br/>";
++$spaces;
foreach( $root->next as $child)
{
if ($child)
{
$this->showAll($child, $spaces);
}
}
}
}
}
// Create a new instance of the tree
$myTree = new Tree;
// Insert the data into the tree.
// The following data would be retrieved using MySQL
$name = 'Electronics'; $parent = NULL;
$myTree->insertPub($name, $parent);
$name = 'Televisions'; $parent = 'Electronics';
$myTree->insertPub($name, $parent);
$name = 'Tube'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);
$name = 'Lcd'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);
$name = 'Plasma'; $parent = 'Televisions';
$myTree->insertPub($name, $parent);
$name = 'Portable Electronics'; $parent = 'Electronics';
$myTree->insertPub($name, $parent);
$name = 'MP3 Players'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);
$name = 'Flash'; $parent = 'MP3 Players';
$myTree->insertPub($name, $parent);
$name = 'CD Players'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);
$name = '2 Way Radios'; $parent = 'Portable Electronics';
$myTree->insertPub($name, $parent);
// Display adjacency
$myTree->showAdjPub();
// Show hierarchy
$myTree->showAllPub();
?>
PS：あなたが提案したようにネストされた配列にPHPでデータを保存することは非常に難しいでしょう。上記のクラスでは、データメンバーが削除された場合、ツリーが変更され（サブツリー全体の追加などを含む）、lft値rgtは引き続き正しく取得されます。
配列を使用して情報を格納する場合、親と子の両方を持つアイテムを削除するのは非常に困難であり、lftとrgtの値を更新するのは非常に困難です。最後に、大きなセット（サブツリー）を配列に追加することも非常に困難です。
ツリーは、この種の階層データを格納するための理想的な方法です。それは私たちの集合の概念を模倣しています。問題は、PHPはツリーを簡単に保存しますが、MySQLは簡単に保存できないため、PHPツリーから情報を抽出してMySQLデータベースに保存できるようにするには、変更されたプレオーダーツリートラバーサルのすべての困難な作業を実行する必要があります。