Edit: Bien, investigué esto un poco más. Creo que hubo una confusión en la nomenclatura. No estás buscando un data structure for a transveral tree en PHP. Desea utilizar un árbol como estructura de datos en PHP y desea recuperar datos de ese árbol mediante un método llamado modified preorder tree traversal algorithm.
Quoting:
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.
Esto es sobre el almacenamiento de datos jerárquicos en PHP vs MySQL. En PHP podemos usar un árbol simple. El problema es que no es fácil almacenar un árbol en la base de datos plana que es MySQL. Una opción es tomar de allí la lista PHP y de recuperación y adyacencia. Esto es esencialmente una lista de cada elemento y sus padres. Esta forma de hacer las cosas tiene algunos inconvenientes.
Otro método es extraer información del árbol de PHP que describe los conjuntos anidados que se pueden crear a partir de los datos jerárquicos. Para obtener esta información del árbol PHP, necesitamos usar un algoritmo de cruce de árbol preordenador modificado. Este es un método para subir y bajar el árbol para extraer cierta información del mismo.
Si usamos el modelo de lista de adyacencia o el recorrido de árbol de preordenamiento modificado para recuperar la información, utilizamos exactamente el mismo árbol de PHP. La diferencia es cómo recuperamos la información del árbol y cómo almacenamos la información en MySQL.El código de cómo extraer la información de MySQL ya está en the page you quoted. Para sincronizar los datos entre PHP y MySQL solo tienes que usar las técnicas de MySQL descritas en esa página y una clase de árbol PHP.
Para esto, creé una clase en PHP que almacena un árbol. Utiliza un nodo. Cada nodo se puede considerar como la raíz de un árbol completo, ya que desde cada nodo se puede acceder a un subárbol completo. Era más fácil separar el nodo del árbol y causa menos sobrecarga.
La parte importante de la clase es showAdjacency método. Esto ejecuta el árbol utilizando un cruce de árbol de preordenamiento modificado, y muestra lft y rgt cantidad para cada nombre que le permite almacenar los datos en MySQL como un conjunto anidado.
También puede mostrar el árbol para que pueda visualizarlo. El método de eliminación falta en esta clase. Cuando lo implemente, debe pasar los elementos secundarios del nodo eliminado al elemento primario del nodo. Quizás lo haga más tarde.
Voy a incluir a toda la clase en la parte inferior del poste, pero aquí es cómo se recuperan los datos para el recorrido del árbol preorden modificación:
// 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;
}
Puede almacenar obviamente $ Raíz> datos, $ rgt, y $ lft en una matriz que usa para sincronizar con su base de datos.
Aquí está toda la clase. Después de la clase, creo un árbol con los datos de muestra del the page you linked to y obtengo los valores de lft y rgt, así como la visualización del árbol.
You can run the code on Codepad
<?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: almacenar los datos en PHP en matrices anidadas como usted sugirió que sería muy difícil. En la clase anterior, si se elimina un miembro de datos, se modifica el árbol (incluidas las adiciones de subárboles enteros, etc.) los valores lft y rgt se recuperarán correctamente.
Si utiliza matrices para almacenar la información, le resultará extremadamente difícil eliminar elementos que tengan padres e hijos, y la actualización de lft y rgt valuse sería muy difícil. Finalmente, agregar conjuntos grandes (subárboles) a la matriz también sería extremadamente difícil.
Un árbol es realmente la forma ideal de almacenar este tipo de datos jerárquicos. Se imita nuestra noción de conjuntos. El problema es que mientras PHP almacena árboles fácilmente, MySQL no lo hace, así que tenemos que pasar por todo el trabajo difícil del recorrido de árbol de preordenamiento modificado para extraer información del árbol PHP para que podamos almacenarlo en MySQL db.
* (recurso) * http://matthewturland.com/2010/05/20/new-spl-features-in-php-5-3/ – Gordon
Heh, de hecho no la adyacencia sino el modelo de conjunto anidado. No creo que ninguno de estos nuevos SPL ayude, ya que el _nodo_ en sí mismo más sabe de sus vecinos, no solo de los padres. Simplemente tendría un montón de objetos que tienen una referencia a los objetos a la izquierda y a la derecha, con un tipo de patrón "Compuesto" para hacer cambios en cascada. – Wrikken
Puede valer la pena echarle un vistazo a cómo [Doctrine] [http://www.propelorm.org/browser/branches/1.6/generator/lib/behavior/nestedset] y [Propel] [http: //trac.doctrine -project.org/browser/branches/1.2/lib/Doctrine/Node] manipular conjuntos anidados. Es posible que necesite construir algunos modelos ficticios para obtener una buena visión del código, especialmente con Propel. – prodigitalson