use*_*841 7 php mptt modified-preorder-tree-t data-structures
我没有CS或数据结构的背景知识.我想创建一个PHP类,它存储一个修改过的预订序横向树,用于操作和与数据库同步.
基本上我需要存储数据,如:
+-------------+----------------------+-----+-----+
| category_id | name | lft | rgt |
+-------------+----------------------+-----+-----+
| 1 | ELECTRONICS | 1 | 20 |
| 2 | TELEVISIONS | 2 | 9 |
| 3 | TUBE | 3 | 4 |
| 4 | LCD | 5 | 6 |
| 5 | PLASMA | 7 | 8 |
| 6 | PORTABLE ELECTRONICS | 10 | 19 |
| 7 | MP3 PLAYERS | 11 | 14 |
| 8 | FLASH | 12 | 13 |
| 9 | CD PLAYERS | 15 | 16 |
| 10 | 2 WAY RADIOS | 17 | 18 |
+-------------+----------------------+-----+-----+
我在考虑使用数组,但看起来很麻烦.如果它是这样的数组数组:array( 'name'=> "PORTABLE ELECTRONICS", 'lft' => 10, 'rgt' = 19 )那么重复循环遍历该数组会很麻烦,以确保所有数字都存在,等等.
由于PHP有一些新的数据结构可用,我想知道这些中的任何一个是否会比使用数组带来任何好处？
编辑:此类不会是存储在数据库表中的树的网关.(如果是的话,我只会对类进行查询.)它只是某种PHP数据结构中的独立mmpt.
编辑:好的,我再看一下这个.我认为命名法有所混淆.你不是在寻找data structure for a transveral treePHP.您希望在PHP中使用树作为数据结构,并且您希望使用名为the的方法从该树恢复数据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中,我们可以使用一个简单的树.问题是在平面数据库中存储树并不容易.一种选择是从中获取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值以及树形图.
<?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 valuse将非常困难.最后,向阵列添加大集(子树)也非常困难.
树真的是存储这种分层数据的理想方式.它模仿我们的集合概念.问题是虽然PHP很容易存储树,但MySQL却没有,所以我们需要经历修改的预订树遍历的所有困难工作,以便从PHP树中提取信息,以便我们可以将它存储在MySQL数据库中.