一种实现左右值无限分类的算法

首先，介绍
产品分类，多级树结构论坛，邮件列表，以及许多其他地方，我们都遇到这样的问题：如何存储多层次的数据在PHP的应用中，提供后台数据的数据库通常是关系数据库，它可以节省大量数据，提供高效的数据检索和更新服务，而关系数据的基本形式是交错表。它是平面结构。如果我们想在关系数据库中存储多层次树结构，就需要做合理的翻译工作，然后用一些实践经验和人来讨论我所看到和听到的东西。
在平面数据库中，有两种常用的层次结构数据保存方法。
*邻接目录模式（邻接表模型）
*预排序遍历树算法（改进前序遍历树算法）
我不是计算机专业人员，也没有学过数据结构。所以这两个名字都是我自己翻译的。如果你说了什么不对的话，请开导我。这两件事看起来很可怕，但很容易理解。

两。模型
在这里，我使用一个简单的食品目录作为我们的样本数据。
我们的数据结构是这样的，下面是代码：
复制代码代码如下所示：
食品

| ---水果

| | ---红色

| | | --樱桃

| + ---黄色

| + Banana

+ ---肉
| --牛肉
+——猪肉

用英语照顾PHP爱好者
复制代码代码如下所示：
食品：食品
水果：水果
红色：红色
樱桃：樱桃
黄色：黄色
香蕉：香蕉
肉类：肉类
牛肉：牛肉
猪肉：猪肉

三。实现
1、邻接目录模型（邻接表模型）
这种模式在许多教程和书籍中经常使用，我们通过将一个属性父节点添加到每个节点以通过一个平面表来描述整个树结构来表示节点的父代，根据这个原则，示例中的数据可以转换成下表：
下面是代码：
复制代码代码如下所示：
----------------------- + +
| parent | name |
----------------------- + +
| |食品|
|食品|水果|
|水果|绿色|
|绿色|梨|
|水果|红|
| | |红樱桃
|水果|黄|
|黄|香蕉|
|食品|肉|
|肉|牛肉|
|肉|猪肉|
----------------------- + +

我们看到，梨是绿色的子节点，而绿色水果的子节点。根node'food'does没有父节点，来描述这个问题很简单，这个例子只使用名称来表示一个记录。在实际的数据库，你需要使用数字ID来标识每个节点，数据库结构是这样的：身份证、parent_id，名称，描述，选择。
有了这样的表，我们就可以通过数据库保存整个多级树结构。
显示多级树，如果我们需要显示这样的多级结构，我们需要一个递归函数。
下面是代码：
复制代码代码如下所示：
< PHP
$父是我们希望看到的子组的父级。
当我们深入到树中时，$水平会增加，
用于显示一个漂亮的缩进
功能display_children（合母，千元级）{
获取父节点的所有子节点$父
结果= mysql_query美元（
选择名称
从一棵树
父=。。$父
；
）；
显示每个子节点
而（$行= mysql_fetch_array（$结果））{
缩进的节点名
回声str_repeat（''，千元级）。$行{ 'name' }。；
再次调用函数显示子节点
display_children（$行{ 'name' }，千元级+ 1）；
}
}
>

利用整个结构的根节点（食物）的功能，可以打印出整个多级树结构。因为食物是根节点的父节点是空的，所以我们叫它display_children（整个树的内容将被显示：
复制代码代码如下所示：
食品
水果
红
樱桃
黄色的
香蕉
肉
牛肉
猪肉

如果你只想显示的整体结构的一部分，如果部分，你可以说它是这样的：display_children（'fruit '，0）；
几乎使用相同的方法，我们可以知道根节点到任何节点的路径。例如，樱桃的路径是食物>果实；红色是。
复制代码代码如下所示：
< PHP
是节点最深的节点吗
功能get_path（元结）{
父节点查询的节点
结果= mysql_query美元（
选择父
从一棵树
名字=。。$
；
）；
行= mysql_fetch_array美元（$结果）；
使用数组保存路径
$路径=数组（）；
如果不是要查询的根节点
（根父节点）
如果（$行{ 'parent}！=）{
路径的最后一部分到$节点，是名称。
$节点的父级
$路径{ } = { } $行'parent；
我们应该将路径添加到这个节点的父节点
路径
$路径= array_merge（get_path（$行{ 'parent}），$路径）；
}
路径返回
返回$路径；
}
>；

如果你使用这个功能的樱桃：print_r（get_path（'cherry '）），你会得到一个数组这样的：
复制代码代码如下所示：
（阵列
{ 0 }食物
{ 1 } =水果
{ 2 } >红色
）

然后如何打印成你想要的格式是你的事情。
缺点：
这种方法很简单，容易理解，手很好，但也有一些缺点，主要原因是操作慢。由于每个节点都需要数据库查询，当数据足够大时，需要进行大量的查询才能完成一棵树，而且由于递归操作，每一级递归都需要占用一些内存，因此空间利用效率也很低。

2、预排序遍历树算法
现在让我们看一个方法没有使用递归计算更快速地看一看，那就是先根遍历算法。
这种方法可能相对较小，并且最初的使用不像上述方法那样容易理解。但是，由于该方法不使用递归查询算法，因而具有较高的查询效率。

我们将在下面的方式画在纸上的多级数据，食物的根节点的左写1然后沿着这棵树继续下来的水果写2和移动的左侧，沿边缘的树上每个节点的左、右数。最后一个号码18对食物的右侧。在下面这幅图，你可以看到整个号码标有多级结构。（不明白吗弄清楚你的手指是怎么回事，把数字从1数到18。不明白，再数数，注意移动手指。
这些数字表示每个节点之间的关系。红的号码是3和6，这是食品1-18.also后代节点，我们可以看到所有的2多个节点的左值和右值是小于11水果2-11后裔。
下面是代码：
复制代码代码如下所示：
1食品18

------------------------------ + +

2水果1112肉17

+ + + + ------------- ------------

3红67黄1013牛肉1415猪肉16

4樱桃58香蕉9

因此，整个树结构可以通过左右两个值存储在数据库中。
下面是代码：
复制代码代码如下所示：
+ + + + ---------- ------------ ----- ----- +
公司名称| LFT | | | RGT |
+ + + + ---------- ------------ ----- ----- +
| | Food | 1 | 18 |
|食品|水果| 2 | 11 |
|水果|红| 3 | 6 |
|红|樱桃| 4 | 5 |
|水果|黄| 7 | 10 |
|黄|香蕉| 8 | 9 |
|食品|肉| 12 | 17 |
|肉|牛肉| 13 | 14 |
|肉|猪肉| 15 | 16 |
+ + + + ---------- ------------ ----- ----- +

注：由于左和右有SQL中的特殊意义，我们需要使用LFT 和团为代表的左、右领域。此外，母领域不再需要这个结构表示树结构。也就是说，下面的表结构是足够的。
下面是代码：
复制代码代码如下所示：
+ + + + ------------ ----- -----
名称LFT RGT | | | |
+ + + + ------------ ----- -----
|食品| 1 | 18 |
|水果| 2 | 11 |
|红| 3 | 6 |
|樱桃| 4 | 5 |
|黄| 7 | 10 |
|香蕉| 8 | 9 |
|肉| 12 | 17 |
|牛肉| 13 | 14 |
|猪肉| 15 | 16 |
+ + + + ------------ ----- -----

现在，我们可以从数据库中获取数据，例如，我们需要将所有的节点放在水果项下以这样的方式来写查询：
复制代码代码如下所示：
SELECT * FROM树现在2和11之间；

此查询获得以下结果。
下面是代码：
复制代码代码如下所示：
+ + + + ------------ ----- -----
名称LFT RGT | | | |
+ + + + ------------ ----- -----
|水果| 2 | 11 |
|红| 3 | 6 |
|樱桃| 4 | 5 |
|黄| 7 | 10 |
|香蕉| 8 | 9 |
+ + + + ------------ ----- -----

你看，你可以得到所有这些节点只要查询了。为了喜欢的递归函数上面显示整个树结构，我们也需要这样的节点左值排序查询：
复制代码代码如下所示：
SELECT * FROM树现在2和11阶之间的LFT ASC；

剩下的问题说明了层次结构是如何缩进的。
下面是代码：
复制代码代码如下所示：
< PHP
功能display_tree（$根）{
获取关于根节点的值
结果= mysql_query美元（
选择LFT，RGT
从一棵树
名字=。。$
；
）；
行= mysql_fetch_array美元（$结果）；
准备 / /空栈右值
数组（）；
获取根节点的所有子节点
结果= mysql_query美元（
选择名字，LFT，RGT
从一棵树
现在之间的。行'lft'} {美元。'和'。'rgt'} { $行。
通过LFT ASC秩序
；
）；
显示每一行
而（$行= mysql_fetch_array（$结果））{
仅检查堆栈是否存在
如果（计数（$右）> 0）{
检查是否应该从堆栈中移除节点。
而（$权{计数（美元对1美元）} { } <<行'rgt）{
array_pop（$权）；
}
}
缩进的节点名
回声str_repeat（''，计数（$右））。$行{ 'name' }。；
将此节点放入堆栈中
$权{ } = { } $行'rgt；
}
}
>

如果你运行上面的函数，你将得到与递归函数相同的结果，因为我们的新函数可能会更快，因为只有2个数据库查询。
知道节点的路径更容易，如果我们想知道樱桃的路径，我们使用它的左值和右值4和5进行查询。
复制代码代码如下所示：
选择的名字从树那里LFT；5阶的LFT ASC；

这将产生以下结果：
下面是代码：
复制代码代码如下所示：
------------ + +
|名字|
------------ + +
|食品|
|水果|
|红|
------------ + +

那么一个节点有多少个后代节点呢很简单，儿童总人数（1 = -右值） / 2
复制代码代码如下所示：
子=（右-左1） 2

不相信吗他是一口井。
这个简单的公式，我们可以快速计算出水果2-11节点有4个子孙节点，而香蕉8-9节点没有子节点，即它不是一个父节点。
太神奇了，不是吗这种方法我已经用过很多次了，但每次我都用它。
这的确是一个很好的方法，但是是否有任何方法可以帮助我们构建具有这样一个左右值的数据表呢这里有一个函数，它可以自动将名称和父结构的表转换为具有左右两个值的表。
下面是代码：
复制代码代码如下所示：
< PHP
功能rebuild_tree（合母，左美元）{
这个节点的正确值是左值+ 1。
$ = $ + 1；
此节点的所有子节点
结果= mysql_query美元（
选择名称
从一棵树
父=。。$父
；
）；
而（$行= mysql_fetch_array（$结果））{
该函数的递归执行
这个节点
$右边是当前的右/值，它是
由rebuild_tree功能 / /递增
右rebuild_tree美元（$行{ 'name' }，为右）；
}
得到了左边的/我们有价值的，现在我们已经处理了
这个节点的孩子也知道正确的值。
mysql_query（
更新树
集
LFT =。。剩下的美元，
RGT =。好吧。
名字=。。$父
；
）；
返回此节点1的正确值
返回$右+ 1；
}
>

当然，这个函数是一个递归函数，我们需要从根节点开始运行这个函数，用左、右值重建树。
复制代码代码如下所示：
rebuild_tree（'food '，1）；

这个函数看起来有点复杂，但它的功能类似于手工编号的表，它是将三维多层结构转换成具有左、右值的数据表。
那么我们如何增加、更新和删除这样一个结构的节点呢
一般有两种添加节点的方法：
第一种方法是保留原始名称和父结构，通过旧方法向数据添加数据。添加一个数据后，rebuild_tree函数进行重新编码的整体结构。
第二，更有效的方式是改变所有的价值观，在新的节点的右侧。例如，我们要添加一个新的水果草莓（草莓），将红色节点的最后一个子节点。首先我们需要为它房间。红是一个rvalue应该从6到8，黄7-10 的价值应改为9-12.we可以举一反三，如果你想让新值的所有值大于5的节点间（5红是一个而最后一个孩子）加2。所以我们做数据库操作，这样：
复制代码代码如下所示：
更新树集团=团+ 2，RGT > 5；
更新树集LFT = LFT + 2 > 5；

这将为新插入的值腾出空间，现在您可以在空出的空间中设置一个新的数据节点，其左值和右值分别为6和7。
复制代码代码如下所示：
插入树集LFT = 6，RGT = 7，= 'strawberry的名字；

再做一次查询，怎么样很快。

四。结论
现在，您可以使用两种不同的方法来设计多级数据库结构。接受的方法完全取决于你的个人判断。但我更喜欢多层次和大结构的第二种方法，第一种方法比较方便，如果查询的数量很少，但需要经常添加和更新。
此外，如果数据库支持也可以使用rebuild_tree（）函数触发和空间操作数据库，自动插入和更新的时间，这样你就可以获得更好的效率，SQL语句，你添加新节点将变得更简单。