Редактировать: Хорошо, я посмотрел на это немного больше. Я думаю, что произошла путаница в номенклатуре. Вы не ищете 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. Один из вариантов - взять PHP и извлечь из него список смежности. По сути это список каждого элемента и его родителей. Этот способ делать вещи имеет некоторые недостатки.
Другой метод заключается в извлечении информации из дерева 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, а также визуализацию дерева.
Вы можете запустить код на 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: Хранить данные в PHP во вложенных массивах, как вы предлагали, будет очень сложно. В приведенном выше классе, если удаляется элемент данных, дерево изменяется (включая добавления целых поддеревьев и т. Д.), Значения lft и rgt будут по-прежнему извлечены правильно.
Если вы используете массивы для хранения информации, вам будет очень трудно удалить элементы, у которых есть как родители, так и дети, а обновление значений lft и rgt будет очень трудным. Наконец, добавление больших массивов (поддеревьев) в массив также будет чрезвычайно трудным.
Дерево действительно идеальный способ хранения иерархических данных такого рода. Это имитирует наши представления о множествах. Проблема в том, что, хотя PHP легко хранит деревья, MySQL этого не делает, поэтому нам нужно пройти всю сложную работу по измененному обходу дерева предзаказа, чтобы извлечь информацию из дерева PHP, чтобы мы могли сохранить ее в базе данных MySQL.