解析PHP无限级分类方法及代码

当前第2页 返回上一页

由于新的表结构，这不需要花太多功夫。你可以看一下，例如，4-5的“Cherry”节点，你会发现祖先的左值都小于4，同时右值都大于5。这样，我们就可以使用下面这个查询：
SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
注意，就像前面的查询一样，我们必须使用一个ORDER BY子句来对节点排序。这个查询将返回：

+-------+
| title |
+-------+
| Food  |
| Fruit |
| Red   |
+-------+

我们现在只要把各行连起来，就可以得到“Cherry”的路径了。
有多少个后续节点？How Many Descendants
如果你给我一个节点的左值和右值，我就可以告诉你他有多少个后续节点，只要利用一点点数学知识。
因为每个后续节点依次会对这个节点的右值增加2，所以后续节点的数量可以这样计算：
descendants = (right – left - 1) / 2
利用这个简单的公式，我可以立刻告诉你2-11的“Fruit”节点有4个后续节点，8-9的“Banana”节点只是1个子节点，而不是父节点。

自动化树遍历
现在你对这个表做一些事情，我们应该学习如何自动的建立表了。这是一个不错的练习，首先用一个小的树，我们也需要一个脚本来帮我们完成对节点的计数。
让我们先写一个脚本用来把一个邻接列表转换成前序遍历树表格。

这是一个递归函数。你要从rebuild_tree('Food',1); 开始，这个函数就会获取所有的“Food”节点的子节点。

如果没有子节点，他就直接设置它的左值和右值。左值已经给出了，1，右值则是左值加1。如果有子节点，函数重复并且返回最后一个右值。这个右值用来作为“Food”的右值。

递归让这个函数有点复杂难于理解。然而，这个函数确实得到了同样的结果。他沿着树走，添加每一个他看见的节点。你运行了这个函数之后，你会发现左值和右值和预期的是一样的（一个快速检验的方法：根节点的右值应该是节点数量的两倍）。

添加一个节点
我们如何给这棵树添加一个节点？有两种方式：在表中保留“parent”列并且重新运行rebuild_tree() 函数——一个很简单但却不是很优雅的函数；或者你可以更新所有新节点右边的节点的左值和右值。

第一个想法比较简单。你使用邻接列表方法来更新，同时使用改进前序遍历树来查询。如果你想添加一个新的节点，你只需要把节点插入表格，并且设置好parent列。然后，你只需要重新运行rebuild_tree() 函数。这做起来很简单，但是对大的树效率不高。

第二种添加和删除节点的方法是更新新节点右边的所有节点。让我们看一下例子。我们要添加一种新的水果——“Strawberry”，作为“Red” 的最后一个子节点。首先，我们要腾出一个空间。“Red”的右值要从6变成8，7-10的“Yellow”节点要变成9-12，如此类推。更新“Red” 节点意味着我们要把所有左值和右值大于5的节点加上2。

我们用一下查询：
UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
现在我们可以添加一个新的节点“Strawberry”来填补这个新的空间。这个节点左值为6右值为7。
INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';
如果我们运行display_tree() 函数，我们将发现我们新的“Strawberry”节点已经成功地插入了树中：Food
 Fruit
   Red
     Cherry
     Strawberry
   Yellow
     Banana
 Meat
   Beef
   Pork

缺点
首先，改进前序遍历树算法看上去很难理解。它当然没有邻接列表方法简单。然而，一旦你习惯了左值和右值这两个属性，他就会变得清晰起来，你可以用这个技术来完成临街列表能完成的所有事情，同时改进前序遍历树算法更快。当然，更新树需要很多查询，要慢一点，但是取得节点却可以只用一个查询。

最后一点：就像我已经说得我部推荐你使用节点的标题来引用这个节点。你应该遵循数据库标准化的基本规则。我没有使用数字标识是因为用了之后例子就比较难读。

算法3