分析PHP的无限分类方法和代码

无论是想建立自己的论坛，在网站上发布新闻，还是自己编写CMS程序，都会遇到数据库中存储分层数据的情况。同时，除非您使用像XML这样的数据库，否则关系数据库中的表不是分层的，它们只是一个平面列表。因此，您必须找到一种方法来转换分层数据库。树结构是一个非常常见的问题，它有几种解决方案。主要有两种方法：邻接表模型和改进的预序遍历树算法。在本文中，我们将讨论这两种保存分层数据的方法。我将举一个在线杂货店的树形图的例子。这家杂货店按类别、颜色和种类组织食物。树形图如下：。

本文包含一些代码示例来演示如何保存和获取数据。我选择PHP来写例子，因为我经常使用这种语言，很多人也使用或者知道这种语言。你可以很容易地把它们翻译成你自己的语言。邻接表模型我们要尝试的第一个——和最漂亮的——方法叫做“邻接表模型”或“递归方法”。这是一个优雅的方法，因为您只需要一个简单的方法来迭代您的树。我们食品店的邻接表如下：。

如您所见，为每个节点保存一个“父”节点。我们可以看到“梨”是“青”的子节点，青是“果”的子节点，以此类推。根节点“Food”，则它的父节点没有值。为了简单起见，我只使用“title”的值来标识每个节点。当然，在实际的数据库中，您应该使用数字标识。显示树现在我们已经将树放入数据库，我们必须编写一个显示函数。该函数将从根节点——开始，没有父节点——的节点将同时显示该节点的所有子节点。对于这些子节点，函数还应该获取并显示该子节点的子节点。然后，对于它们的子节点，该函数将再次显示所有子节点，以此类推。您可能已经注意到，在这个函数的描述中有一个通用的模式。我们可以简单地编写一个函数来获取特定节点的子节点。然后，该函数在每个子节点上调用自己，以再次显示它们的子节点。这就是“递归”机制，所以这个方法叫“递归法”。

要实现整个树，我们只需要调用一个空字符串作为$parent，并且$ level=0: display _ children('，0)的函数；函数返回我们的食物商店的树形视图如下：foodfoundcherryyellowbananmeanebeefwork注意，如果你只想看到一个子树，你可以告诉函数从另一个节点开始。例如，要显示“水果”子树，只需要显示_ children(‘水果’，0)；节点路径使用类似的函数。如果您只知道节点的名称或标识，我们也可以查询节点的路径。比如“樱桃”的路径是“菜”“果”“红”。要获得这条路径，我们的功能必须从最深层次开始：“Cheery”。但是然后找到这个节点的父节点并将其添加到路径中。在我们的例子中，这个父节点是“红色”。如果我们知道“红”是“樱桃”的父节点。

这个函数现在返回指定节点的路径。他将路径作为数组返回，这样我们就可以使用print _ r(get _ path(' Cherry '))；为了显示，结果是Array([0]=食物[1]=水果[2]=红色)不足。我们可以看到，这确实是一个很好的方法。他容易理解，代码简单。但是邻接表模型的缺点在哪里？在大多数编程语言中，它既慢又低效。这主要是“递归”造成的。每次查询节点时，我们都必须访问数据库。每次查询数据库都需要一些时间，这使得函数处理巨大的树非常慢。这个函数不太快的第二个原因可能是你使用的语言。与Lisp不同，大多数语言不是为递归函数设计的。对于每个节点，函数调用自己来生成一个新实例。因此，对于4级树，您可能必须同时运行4个函数副本。每个函数占用一块内存，初始化需要一定的时间，所以在处理大树时递归比较慢。改进前言遍历树现在，让我们看看存储树的另一种方法。递归可能比较慢，所以我们尽量不使用递归函数。我们还希望最小化数据库查询的数量。最好一次只需要查询一次。让我们先把树水平摆放。从根节点(“Food”)开始，然后在他的左边写1。然后按照树的顺序(从上到下)在“水果”左边写2。这样，你沿着树的边界行走(这被称为“遍历”)，然后同时在每个节点的左右两边写数字。最后，我们回到根节点“Food”，在右边写了18。下面是一棵标有数字的树，遍历的顺序用箭头标出。

我们称这些数字为左值和右值(例如，“Food”的左值为1，右值为18)。如您所见，这些数字按时显示了每个节点之间的关系。因为“红色”有3和6两个值，所以它是“食物”节点的后继节点，值为1-18。同样的，我们可以推断所有左值大于2、右值小于11的节点都是2-11的“Food”节点的后继节点。这样，树的结构由左值和右值存储。这种通过整树多次计算节点的方法称为“改进的序遍历树”算法。在继续之前，让我们看看表中的这些值：。

请注意，“左”和“右”在SQL中有特殊的含义。因此，我们只能用“lft”和“rgt”来表示这两列。其实Mysql可以用“`”，比如“` left `”，MSSQL可以用“[]”括起来，比如“[left]”，以免和关键词冲突。)还要注意，我们这里不需要“父”列。我们只需要使用lft和rgt来存储树的结构。获取树如果要显示具有左右值的树，必须首先确定要获取的节点。例如，如果你想得到“水果”子树，你应该选择那些左边值从2到11的节点。用SQL语句表示：从树中选择*其中lft介于2和11之间；这将返回：。

现在整个树都在一个查询中。现在，我们希望像前面的递归函数一样显示树，并希望向查询中添加ORDER BY子句。如果您在表中添加和删除行，您的表可能会有问题，因此我们需要根据它们的左值进行排序。从EN 2和11号订单之间的树中选择*；只剩下缩进了。为了显示树结构，子节点应该比其父节点稍微缩进一些。我们可以保存一堆正确的值。每次从一个节点的子节点开始时，都会将该节点的正确值添加到堆栈中。您还知道子节点的右值小于父节点的右值，因此通过将当前节点的右值与堆栈中的前一个节点进行比较，可以判断您是否显示了该父节点的子节点。当您完成显示此节点时，您将从堆栈中删除它的正确值。要获得当前节点的层数，只需计算堆栈中的元素。

如果运行这段代码，可以得到与上一节讨论的递归函数相同的结果。这个函数可能会快一点：它不使用递归，只使用两个查询节点的路径。利用新算法，我们需要找到另一种新方法来获得指定节点的路径。这样，我们需要这个节点的祖先列表。因为新的表结构，它不需要太多的努力。你可以看一下，比如4-5的“Cherry”节点，你会发现祖先的左值都小于4，而右值都大于5。这样，我们可以使用以下查询：从树中选择标题，其中lft4和rgt5按lftasc排序；请注意，就像前面的查询一样，我们必须使用ORDER BY子句对节点进行排序。查询将返回：-|标题|-|食物| |水果| |红色|-有多少后续节点？有多少后代如果你给我一个节点的左右值，我可以告诉你它有多少后续节点，只要你用一点数学知识。因为每个后续节点会依次将这个节点的右值增加2，后续节点的个数可以计算如下：后代=(右-左-1)/2有了这个简单的公式，我可以马上告诉你，2-11的“水果”节点有4个后续节点，8-9的“香蕉”节点只是一个子节点，不是父节点。自动树遍历既然您已经对这个表做了一些事情，我们应该学习如何自动构建这个表。这是一个很好的练习。首先，我们用一棵小树。我们还需要一个脚本来帮助我们计算节点。让我们编写一个脚本，将邻接表转换为预先遍历树的表。

这是一个递归函数。您要从rebuild_tree('Food '，1)开始；首先，这个函数会得到“Food”节点的所有子节点。如果没有子节点，他直接设置它的左右值。左边的值是1，右边的值是左边的值加1。如果有子节点，函数将重复并返回最后一个正确的值。这个权利值被用作“食物”的权利值。递归使这个函数有点复杂和难以理解。然而，这个函数确实得到了相同的结果。他沿着树走，并添加了他看到的每个节点。运行此函数后，您会发现左右值与预期值相同(快速测试方法：根节点的右值应该是节点数的两倍)。添加节点我们如何向此树添加节点？有两种方法：保留表中的“parent”列，重新运行rebuild_tree()函数——，一个简单但不是很优雅的函数；或者，您可以在所有新节点的右侧更新节点的左右值。第一个想法相对简单。你用邻接表的方法来更新，同时你用改进的预序遍历树来查询。如果要添加新节点，只需将该节点插入到表中并设置父列即可。然后，您只需要重新运行rebuild_tree()函数。这很容易做到，但对于大树来说效率不高。添加和删除节点的第二种方法是更新新节点右侧的所有节点。我们来看一个例子。我们想添加一个新的水果——“草莓”作为“红”的最后一个子节点。首先，我们需要腾出空间。“红色”的右值应该从6更改为8，7-10的“黄色”节点应该更改为9-12，以此类推。更新“红色”节点意味着向左右值大于5的所有节点添加2。让我们使用查询：UPDATE树SET rgt=rgt 2 WHERE rgt5更新树集lft=lft 2，其中lft 5；现在我们可以添加一个新节点“草莓”来填充这个新空间。这个节点的左边值是6，右边值是7。插入树集lft=6，rgt=7，标题='草莓'；如果运行display_tree()函数，我们会发现我们新的“草莓”节点已经成功插入到树中：食物水果红色樱桃草莓黄色香蕉肉蜜蜂猪肉缺点首先，似乎很难理解订单前遍历树的改进算法。肯定没有邻接表法那么简单。然而，一旦你习惯了左值和右值，它就会变得清晰。您可以使用这项技术来完成正面列表可以完成的所有事情，同时，改进预排序遍历树算法会更快。当然，更新树需要大量的查询，这样比较慢，但是只能用一个查询来获取节点。总而言之，您现在已经熟悉了在数据库中存储树的两种方法。虽然在我的办公室中改进的序言遍历树算法的性能更好，但是邻接表方法在您的特殊情况下可能会表现得更好。这是你来决定最后一点：我已经说过了，我们部门建议你用节点的标题来指代这个节点。您应该遵循数据库规范化的基本规则。我没有使用数字身份证，因为使用后很难阅读该示例。算法3

在MYSQL中，数据表大致是create table _ types (id整数不为null auto _ increment，parent _ id整数，node varchar (255)，主键(ID))，如上图所示，紫色是数据记录的ID号。框中的数字是每个记录的节点字段，记录了记录的父标识和父标识的父标识.这样，如果我们想在ID为7的记录下插入ID为13的新记录，新记录的节点就是1，2，7，13。如果我们想找到一个节点下的所有子节点，我们不需要递归，只需要一个SQL。比如“查找ID为2的所有子节点”，从table _ types中选择*其中节点像‘1，2，%’，我们来讨论一下这个算法的有效性和缺点！上次看到的左右值的算法在搜索中是非常好的，但是如果频繁插入的话，它的性能会非常差，因为每次插入一个新的节点，父节点下面的所有记录都需要更新。的正确值。上面的算法插入特别简单，只要找到父ID的根即可。搜索似乎还不错，避免了递归。