PHP网页编程之PHP技能实例：树形布局的算法
基础这个东西，有人问学php需要任何基础不? 从喜悦村上转载，之前也读过此文，讲述得仍是对照清晰的。产物分类，多级的树状布局的服装论坛，邮件列表等很多中央咱们城市碰到如许的成绩：若何存储多级布局的数据？
在PHP的使用中，供应后台数据存储的凡是是关系型数据库，它可以保留大批的数据，供应高效的数据检索和更新办事。但是关系型数据的根基模式是犬牙交错的表，是一个立体的布局，假如要将多级树状布局存储在关系型数据库里就需求停止公道的翻译任务。接上去我会将本人的所见所闻和一些适用的经历和人人切磋一下。
层级布局的数据保留在立体的数据库中根基上有两种经常使用设计办法：
毗连目次形式(adjacency list model)
预排序遍历树算法(modified preorder tree traversal algorithm)
我不是盘算机专业的，也没有学过甚么数据布局的器材，所以这两个名字都是我本人依照字面的意思翻的，假如说错了还请多多指教。
这两个器材听着仿佛很吓人，其实十分轻易了解。这里我用一个复杂食物目次作为咱们的示例数据。 咱们的数据布局是如许的:
Food
|
|---Fruit
| |
| |---Red
| | |
| | |--Cherry
| |
| |---Yellow
| |
| |--Banana
|
|---Meat
|
|--Beef
|
|--Pork
为了照料那些英文乌烟瘴气的PHP喜好者
Food:食品
Fruit:生果
Red:白色
Cherry:樱桃
Yellow:黄色
Banana:喷鼻蕉
Meat:肉类
Beef:牛肉
Pork:猪肉
毗连目次形式(adjacency list model)
这类形式咱们常常用到，良多的教程和书中也引见过。咱们经由过程给每一个节点增添一个属性 parent 来暗示这个节点的父节点从而将全部树状布局经由过程立体的表描写出来。依据这个准绳，例子中的数据可以转化成以下的表：
+-----------------------+
| parent | name |
+-----------------------+
| | Food |
| Food | Fruit |
| Fruit | Green |
| Green | Pear |
| Fruit | Red |
| Red | Cherry |
| Fruit | Yellow |
| Yellow | Banana |
| Food | Meat |
| Meat | Beef |
| Meat | Pork |
+-----------------------+
咱们看到 Pear 是Green的一个子节点，Green是Fruit的一个子节点。而根节点'Food'没有父节点。 为了复杂地描写这个成绩， 这个例子中只用了name来暗示一个纪录。 在实践的数据库中，你需求用数字的id来标示每一个节点，数据库的表布局也许应当像如许：id, parent_id, name, description。有了如许的表咱们就能够经由过程数据库保留全部多级树状布局了。
显示多级树
假如咱们需求显示如许的一个多级布局需求一个递归函数。
<?php
// $parent is the parent of the children we want to see
// $level is increased when we go deeper into the tree,
// used to display a nice indented tree
function display_children($parent, $level)
{
// 取得一个 父节点 $parent 的一切子节点
$result = mysql_query('SELECT name FROM tree '.
'WHERE parent="'.$parent.'";');
// 显示每一个子节点
while ($row = mysql_fetch_array($result))
{
// 缩进显示节点称号
echo str_repeat(' ',$level).$row['name']."n";
//再次挪用这个函数显示子节点的子节点
display_children($row['name'], $level+1);
}
}
?>
对全部布局的根节点（Food）利用这个函数就能够打印出全部多级树布局，因为Food是根节点它的父节点是空的，所以如许挪用: display_children('',0)。将显示全部树的内容：
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
假如你只想显示全部布局中的一局部，好比说生果局部，就能够如许挪用：
display_children('Fruit',0);
几近利用一样的办法咱们可以晓得从根节点就任意节点的途径。好比 Cherry 的途径是 "Food > Fruit > Red"。 为了失掉如许的一个途径咱们需求从最深的一级"Cherry"入手下手， 查询失掉它的父节点"Red"把它添加到途径中， 然后咱们再查询Red的父节点并把它也添加到途径中，以此类推直到最高层的"Food"
<?php
// $node 是谁人最深的节点
function get_path($node)
{
// 查询这个节点的父节点
$result = mysql_query('SELECT parent FROM tree '.
'WHERE name="'.$node.'";');
$row = mysql_fetch_array($result);
// 用一个数组保留途径
$path = array();
// 假如不是根节点则持续向上查询
// (根节点没有父节点)
if ($row['parent']!='')
{
// the last part of the path to $node, is the name
// of the parent of $node
$path[] = $row['parent'];
// we should add the path to the parent of this node
// to the path
$path = array_merge(get_path($row['parent']), $path);
}
// return the path
return $path;
}
?>
假如对"Cherry"利用这个函数：print_r(get_path('Cherry'))，就会失掉如许的一个数组了：
Array
(
=> Food
=> Fruit
=> Red
)
接上去若何把它打印成你但愿的格局，就是你的工作了。
弱点：这类办法很复杂，轻易了解，好上手。然而也有一些弱点。次要是由于运转速度很慢，因为失掉每一个节点都需求停止数据库查询，数据量大的时分要停止良多查询才干完成一个树。别的因为要停止递归运算，递归的每级都需求占用一些内存所以在空间使用上效力也对照低。
如今让咱们看一看别的一种不利用递归盘算，加倍疾速的办法，这就是预排序遍历树算法(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;
剩下的成绩若何显示层级的缩进了。
<?php
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<$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 C left - 1) / 2 不信任？本人算一算啦。用这个复杂的公式，咱们可以很快的算出"Fruit 2-11"节点有4个子孙节点，而"Banana 8-9"节点没有子孙节点，也就是说它不是一个父节点了。
很奇异吧？固然我已屡次用过这个办法，然而每次如许做的时分仍是感应很奇异。
这切实其实是个很好的举措，然而有甚么举措可以帮咱们创立如许有摆布值的数据表呢？这里再引见一个函数给人人，这个函数可以将name和parent布局的表主动转换成带有摆布值的数据表。
<?php
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语句会变得加倍复杂。
类递归法
Posted by 访客 on 2004, May 31 - 9:18am.
我用类 递归法 写了段法式，跟文章中的递归不完整一样
正筹办移植到 xoops 中:
http://dev.xoops.org/modules/xfmod/project/?ulink
已呈现内存溢呈现象
不外筹办持续采取递归法，只是需求持续改善
但愿无机会跟列位会商cms
说php的话，首先得提一下数组，开始的时候我是最烦数组的，总是被弄的晕头转向，不过后来呢，我觉得数组里php里最强大的存储方法，所以建议新手们要学好数组。 在我安装pear包的时候老是提示，缺少某某文件，才发现 那群extension 的排列是应该有一点的顺序，而我安装的版本的排序不是正常的排序。没办法我只好把那群冒号加了上去，只留下我需要使用的扩展。 真正的方向了，如果将来要去开发团队，你一定要学好smarty ,phplib这样的模板引擎， 写的比较杂，因为我也是个新手，不当至于大家多多指正。 多看优秀程序员编写的代码，仔细理解他们解决问题的方法，对自身有很大的帮助。 装在C盘下面可以利用windows的ghost功能可以还原回来（顺便当做是重转啦），当然啦我的编译目录要放在别的盘下，不然自己的劳动成果就悲剧啦。 遇到出错的时候，我经常把错误信息直接复制到 google的搜索栏，一般情况都是能搜到结果的，不过有时候会搜出来一大片英文的出来，这时候就得过滤一下，吧中文的弄出来，挨着式方法。 爱上php，他也会爱上你。 作为一个合格的coder 编码的规范是必须，命名方面我推崇“驼峰法”，另外就是自己写的代码最好要带注释，不然时间长了，就算是自己的代码估计看起来都费事，更不用说别人拉。 开发工具也会慢慢的更专业，每个公司的可能不一样，但是zend studio是个大伙都会用的。 首先声明：我是一个菜鸟，是一个初学者。学习了一段php后总是感觉自己没有提高，无奈。经过反思我认为我学习过程中存在很多问题，我改变了学习方法后自我感觉有了明显的进步。 学好程序语言，多些才是王道，写两个小时代码的作用绝对超过看一天书，这个我是深有体会（顺便还能练打字速度）。 这些都是最基本最常用功能，我们这些菜鸟在系统学习后，可以先对这些功能深入研究。 在学习的过程中不能怕麻烦，不能有懒惰的思想。学习php首先应该搭建一个lamp环境或者是wamp环境。这是学习php开发的根本。虽然网络上有很多集成的环境，安装很方便，使用起来也很稳定、 其实也不算什么什么心得，在各位大侠算是小巫见大巫了吧，望大家不要见笑，若其中有错误的地方请各位大虾斧正。 曾经犯过一个很低级的错误，我在文件命名的时候用了一个横线\\\\\\\'-\\\\\\\' 号，结果找了好几个小时的错误，事实是命名的时候 是不能用横线 \\\\\\\'-\\\\\\\' 的，应该用的是下划线\\\\\\\'_\\\\\\\' ; 如果你可以写完像留言板这样的程序，那么你可以去一些别人的代码了， 遇到出错的时候，我经常把错误信息直接复制到 google的搜索栏，一般情况都是能搜到结果的，不过有时候会搜出来一大片英文的出来，这时候就得过滤一下，吧中文的弄出来，挨着式方法。
页:
[1]