编辑:好的,我进一步研究了一下。我认为术语混淆了。您不是在寻找 PHP 中的遍历树的数据结构。您想要在 PHP 中使用树作为数据结构,并且您想使用称为
修改的先序树遍历算法
的方法从该树中恢复数据。
引用:
在处理树时,我们从左到右逐层向下工作,首先降到每个节点的子节点,然后分配右侧编号并继续向右移动。这种方法称为修改的先序树遍历算法。
这篇文章是关于在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数据库中。