热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

无限级分类[预排序遍历树算法]-PHP源码

无限级分类[预排序遍历树算法]
无限级分类[预排序遍历树算法]

预排序遍历树算法

现在让我们看一看另外一种不使用递归计算,更加快速的方法,这就是预排序遍历树算法(modified preorder tree traversal algorithm)
这种方法大家可能接触的比较少,初次使用也不像上面的方法容易理解,但是由于这种方法不使用递归查询算法,有更高的查询效率。

我们首先将多级数据按照下面的方式画在纸上,在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进,沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你可以看到整个标好了数字的多级结构。(没有看懂?用你的手指指着数字从1数到18就明白怎么回事了。还不明白,再数一遍,注意移动你的手指)。
这些数字标明了各个节点之间的关系,"Red"的号是3和6,它是 "Food" 1-18 的子孙节点。 同样,我们可以看到 所有左值大于2和右值小于11的节点 都是"Fruit" 2-11 的子孙节点

以下是代码: 1 Food 18

|

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

| |

2 Fruit 11 12 Meat 17

| |

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

| | | |

3 Red 6 7 Yellow 10 13 Beef 14 15 Pork 16

| |

4 Cherry 5 8 Banana 9
这样整个树状结构可以通过左右值来存储到数据库中。继续之前,我们看一看下面整理过的数据表。

以下是代码: +----------+------------+-----+-----+

| parent | name | lft | rgt |

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

| | Food | 1 | 18 |

| Food | Fruit | 2 | 11 |

| Fruit | Red | 3 | 6 |

| Red | Cherry | 4 | 5 |

| Fruit | Yellow | 7 | 10 |

| Yellow | Banana | 8 | 9 |

| Food | Meat | 12 | 17 |

| Meat | Beef | 13 | 14 |

| Meat | Pork | 15 | 16 |

+----------+------------+-----+-----+
注意:由于"left"和"right"在 SQL中有特殊的意义,所以我们需要用"lft"和"rgt"来表示左右字段。 另外这种结构中不再需要"parent"字段来表示树状结构。也就是 说下面这样的表结构就足够了。

以下是代码: +------------+-----+-----+

| name | lft | rgt |

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

| Food | 1 | 18 |

| Fruit | 2 | 11 |

| Red | 3 | 6 |

| Cherry | 4 | 5 |

| Yellow | 7 | 10 |

| Banana | 8 | 9 |

| Meat | 12 | 17 |

| Beef | 13 | 14 |

| Pork | 15 | 16 |

+------------+-----+-----+
好了我们现在可以从数据库中获取数据了,例如我们需要得到"Fruit"项下的所有所有节点就可以这样写查询语句: SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
这个查询得到了以下的结果。

以下是代码: +------------+-----+-----+

| name | lft | rgt |

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

| Fruit | 2 | 11 |

| Red | 3 | 6 |

| Cherry | 4 | 5 |

| Yellow | 7 | 10 |

| Banana | 8 | 9 |

+------------+-----+-----+
看到了吧,只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构,我们还需要对这样的查询进行排序。用节点的左值进行排序: SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
剩下的问题如何显示层级的缩进了。
以下是代码:

function display_tree($root) {

// 得到根节点的左右值

$result = mysql_query("

SELECT lft, rgt

FROM tree

WHERE name = '" . $root . "'

;"

);

$row = mysql_fetch_array($result);

// 准备一个空的右值堆栈

$right = array();

// 获得根基点的所有子孙节点

$result = mysql_query("

SELECT name, lft, rgt

FROM tree

WHERE lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] ."'

ORDER BY lft ASC

;"

);

// 显示每一行

while ($row = mysql_fetch_array($result)) {

// only check stack if there is one

if (count($right) > 0) {

// 检查我们是否应该将节点移出堆栈

while ($right[count($right) - 1] <$row['rgt']) {

array_pop($right);

}

}

// 缩进显示节点的名称

echo str_repeat(' ',count($right)) . $row['name'] . "n";

// 将这个节点加入到堆栈中

$right[] = $row['rgt'];

}

}

?>


如果你运行一下以上的函数就会得到和递归函数一样的结果。只是我们的这个新的函数可能会更快一些,因为只有2次数据库查询。
要获知一个节点的路径就更简单了,如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。 SELECT name FROM tree WHERE lft <4 AND rgt >; 5 ORDER BY lft ASC;
这样就会得到以下的结果:

以下是代码: +------------+

| name |

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

| Food |

| Fruit |

| Red |

+------------+
那么某个节点到底有多少子孙节点呢?很简单,子孙总数=(右值-左值-1)/2 descendants = (right – left - 1) / 2
不相信?自己算一算啦。
用这个简单的公式,我们可以很快的算出"Fruit 2-11"节点有4个子孙节点,而"Banana 8-9"节点没有子孙节点,也就是说它不是一个父节点了。
很神奇吧?虽然我已经多次用过这个方法,但是每次这样做的时候还是感到很神奇。
这的确是个很好的办法,但是有什么办法能够帮我们建立这样有左右值的数据表呢?这里再介绍一个函数给大家,这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。
以下是代码:

function rebuild_tree($parent, $left) {

// the right value of this node is the left value + 1

$right = $left+1;

// get all children of this node

$result = mysql_query("

SELECT name

FROM tree

WHERE parent = '" . $parent . "'

;"

);

while ($row = mysql_fetch_array($result)) {

// recursive execution of this function for each

// child of this node

// $right is the current right value, which is

// incremented by the rebuild_tree function

$right = rebuild_tree($row['name'], $right);

}

// we've got the left value, and now that we've processed

// the children of this node we also know the right value

mysql_query("

UPDATE tree

SET

lft = '" . $left . "',

rgt= '" . $right . "'

WHERE name = '" . $parent . "'

;"

);

// return the right value of this node + 1

return $right + 1;

}

?>


当然这个函数是一个递归函数,我们需要从根节点开始运行这个函数来重建一个带有左右值的树 rebuild_tree('Food',1);


这个函数看上去有些复杂,但是它的作用和手工对表进行编号一样,就是将立体多层结构的转换成一个带有左右值的数据表。

那么对于这样的结构我们该如何增加,更新和删除一个节点呢?
增加一个节点一般有两种方法:
第一种,保留原有的name 和parent结构,用老方法向数据中添加数据,每增加一条数据以后使用rebuild_tree函数对整个结构重新进行一次编号。
第二种,效率更高的办法是改变所有位于新节点右侧的数值。举例来说:我们想增加一种新的水果"Strawberry"(草莓)它将成为"Red"节点的最后一个子节点。首先我们需要为它腾出一些空间。"Red"的右值应当从6改成8,"Yellow 7-10 "的左右值则应当改成 9-12。 依次类推我们可以得知,如果要给新的值腾出空间需要给所有左右值大于5的节点 (5 是"Red"最后一个子节点的右值) 加上2。 所以我们这样进行数据库操作: UPDATE tree SET rgt = rgt + 2 WHERE rgt > 5;

UPDATE tree SET lft = lft + 2 WHERE lft > 5;
这样就为新插入的值腾出了空间,现在可以在腾出的空间里建立一个新的数据节点了, 它的左右值分别是6和7 INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';
再做一次查询看看吧!怎么样?很快吧。

四、结语
好了,现在你可以用两种不同的方法设计你的多级数据库结构了,采用何种方式完全取决于你个人的判断,但是对于层次多数量大的结构我更喜欢第二种方法。如果查询量较小但是需要频繁添加和更新的数据,则第一种方法更为简便。
另外,如果数据库支持的话 你还可以将rebuild_tree()和 腾出空间的操作写成数据库端的触发器函数, 在插入和更新的时候自动执行, 这样可以得到更好的运行效率, 而且你添加新节点的SQL语句会变得更加简单。

推荐阅读
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • PHP 编程疑难解析与知识点汇总
    本文详细解答了 PHP 编程中的常见问题,并提供了丰富的代码示例和解决方案,帮助开发者更好地理解和应用 PHP 知识。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • PHP 5.2.5 安装与配置指南
    本文详细介绍了 PHP 5.2.5 的安装和配置步骤,帮助开发者解决常见的环境配置问题,特别是上传图片时遇到的错误。通过本教程,您可以顺利搭建并优化 PHP 运行环境。 ... [详细]
  • 深入理解 SQL 视图、存储过程与事务
    本文详细介绍了SQL中的视图、存储过程和事务的概念及应用。视图为用户提供了一种灵活的数据查询方式,存储过程则封装了复杂的SQL逻辑,而事务确保了数据库操作的完整性和一致性。 ... [详细]
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • 本文详细介绍了如何通过多种编程语言(如PHP、JSP)实现网站与MySQL数据库的连接,包括创建数据库、表的基本操作,以及数据的读取和写入方法。 ... [详细]
  • 机器学习中的相似度度量与模型优化
    本文探讨了机器学习中常见的相似度度量方法,包括余弦相似度、欧氏距离和马氏距离,并详细介绍了如何通过选择合适的模型复杂度和正则化来提高模型的泛化能力。此外,文章还涵盖了模型评估的各种方法和指标,以及不同分类器的工作原理和应用场景。 ... [详细]
  • 深入解析JVM垃圾收集器
    本文基于《深入理解Java虚拟机:JVM高级特性与最佳实践》第二版,详细探讨了JVM中不同类型的垃圾收集器及其工作原理。通过介绍各种垃圾收集器的特性和应用场景,帮助读者更好地理解和优化JVM内存管理。 ... [详细]
  • 本文将介绍如何使用 Go 语言编写和运行一个简单的“Hello, World!”程序。内容涵盖开发环境配置、代码结构解析及执行步骤。 ... [详细]
  • This guide provides a comprehensive step-by-step approach to successfully installing the MongoDB PHP driver on XAMPP for macOS, ensuring a smooth and efficient setup process. ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 如何在PHPcms网站中添加广告
    本文详细介绍了在PHPcms网站后台添加广告的方法,涵盖多种常见的广告形式,如百度广告和Google广告,并提供了相关设置的步骤。同时,文章还探讨了优化网站流量的SEO策略。 ... [详细]
  • 深入理解C++中的KMP算法:高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法,探讨其在字符串匹配问题上的优势。通过对比暴力匹配(BF)算法,展示KMP算法如何利用前缀表优化匹配过程,显著提升效率。 ... [详细]
  • 在使用SQL Server进行动态SQL查询时,如果遇到LIKE语句无法正确返回预期结果的情况,通常是因为参数传递方式不当。本文将详细探讨这一问题,并提供解决方案及相关的技术背景。 ... [详细]
author-avatar
林林净洁_526
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有