PHP无限分类

lsx220 贡献于2014-09-05

作者 微软用户  创建于2009-09-28 05:08:00   修改者微软用户  修改于2009-09-28 05:34:00字数11848

文档摘要:递归是一种函数调用自身的机制。这是一种强大的特性可以把某些复杂的东西变得很简单。有一个使用递归的例子是快速排序(quicksort)。不幸的是,PHP并不擅长递归。Zeev,一个PHP开发人员,说道:“PHP 4.0(Zend)对密集数据使用了栈方式,而不是使用堆方式。也就是说它能容忍的递归函数的数量限制和其他语言比起来明显少。”见bug 1901。这是一个很不好的借口。每一个编程语言都应该提供良好的递归支持。
关键词:

 无限分类 一. 父子ID法 (1) 数据结构(族谱) 二. +---------------------------+ 三. | ID | PARENT |    NAME     | 四. +----+--------+-------------+ 五. | 1  | 0      |    祖父     | 六. +----+--------+-------------+ 七. | 2  | 1      |    父亲     | 八. +----+--------+-------------+ 九. | 3  | 1      |    叔伯     | 十. +----+--------+-------------+ 十一. | 4  | 2      |    自己     | 十二. +----+--------+-------------+ 十三. | 5  | 4      |    儿子     | 十四. +----+--------+-------------+ 十五. | 6  | 5      |    孙子     | 十六. +----+--------+-------------+ 十七. | 7  | 2      |    姐妹     | 十八. +----+--------+-------------+ 十九. | 8  | 3      |    表亲     | 二十. +----+--------+-------------+ 二十一. | 9  | 7      |    甥儿     | 二十二. +----+--------+-------------+ 二十三. | 10 | 4      |    女儿     | 二十四. +----+--------+-------------+ 二十五. | 11 | 10     |    外孙     | 二十六. +----+--------+-------------+ 二十七. | 12 | 5      |    孙女     | 二十八. +----+--------+-------------+ 二十九. | .. | ...    |    ....     | 三十. +---------------------------+ 求值: 1)、已知任一ID,可以求得祖先ID表 2)、已知任一ID,可以求祖先ID表(含自己) 3)、已知任一ID,后代ID表 3)、已知任一ID,后代ID表(含自己) (2)PHP代码 * @version $Id: family.php, v 0.0.1 2008/09/23 16:07:25 uw Exp $ */ /** * 获取祖先树二维数组,长幼逆序,不含己身 * @param int $id 己身所在id * @return array */ function _getForefathers($id) {     $data = array();     $sql = "         SELECT *         FROM family         WHERE id = (             SELECT parent             FROM family             WHERE id = '" . $id ."')         ;";     $re = mysql_query($sql);     if(mysql_num_rows($re)) {   /* 如果存在有祖先 */         $data[] = $rs = mysql_fetch_assoc($re);         $data = array_merge($data, _getForefathers($rs['id'])); /* 递归查询 */          return $data;     } else {         return $data;     } } /** * 获取祖先树二维数组,长幼顺序,含己身 * @param int $id 己身所在id * @return array */ function getForefathers($id) {     return array_reverse(array_merge(array(mysql_fetch_assoc(mysql_query("SELECT * FROM family WHERE id = '" . $id . "'; "))), _getForefathers($id))); } /** * 获取指定id的所有后代,不含指定id * @param mixed $id 指定id, 有可能是array * @return array 所有后代id的一维数组 */ function _getOffspring($id) {     $data = array();     $ids = array();     if(!is_array($id)) { $id = array($id); }     $id = implode(', ', $id);     $sql = "         SELECT *                FROM family                WHERE parent IN (" . $id . ") ;";     $re = mysql_query($sql);     if(mysql_num_rows($re)) {         while($rs = mysql_fetch_assoc($re)) {                    $ids[] = $rs['id'];                }                $ids = array_merge($ids, _getOffspring($ids));                return $ids;     } else {         return  $ids;     } } /** * 获得指定id的所有后代,含指定id * @param mixed $id 指定id, 有可能是array * @return array 所有后代的和指定id的一维数组 */ function getOffspring($id) {     if(!is_array($id)) { $id = array($id); }     return array_merge($id, _getOffspring($id)); } /* 主程序 */ ini_set('default_charset', 'utf-8');    /* 设定HTML输出编码为utf-8 */ mysql_connect('localhost', 'root', ''); /* 连接MySQL */ mysql_select_db('family');              /* 打开family数据库 */ mysql_query("SET NAMES 'utf8'");        /* 设定数据库输出编码 */ echo '
';    var_dump(getForefathers(11));           /* 输出ID=11的祖先树 */    var_dump(getOffspring(array(3, 4)));     /* 输出ID=3及ID=4的后代ID表 */    echo '
'; 二.左右值法 适合数据量小且不经常改动的无限分类。 Type_id Name Lft Rgt 1 商品 1 18 2 食品 2 11 3 肉类 3 6 4 猪肉 4 5 5 蔬菜类 7 10 6 白菜 8 9 7 电器 12 17 8 电视机 13 14 9 电冰箱 15 16   看一下上面的表就知道了,左值大于1右值小于18的为商品,左值小于2右值大于11的为食品。如果商品分类还要多的话,左右值就要动态更新。   优点:在消除递归的前提下实现了无限分级,而且查询条件是基于整形数字比较的,效率很高。可以进行先序列表,添加,修改,删除,同层平移等常规操作,基本满足需求。   缺点:由于这种左右值编码的方式和常见的阿拉伯数字直观排序不同,再加上节点在树中的层次,顺序不是直观显示出来,而必须通过简单的公式计算后得到,需要花费一定的时间对其数学模型进行深入理解。而且,采用该方案编写相关存储过程,新增,删除,同层平移节点需要对整个树进行查询修改,由此导致的代码复杂度,耦合度较高,修改维护的风险较高。 三.理解概念 (1)PHP的递归   1. 对递归的不良支持   递归是一种函数调用自身的机制。这是一种强大的特性可以把某些复杂的东西变得很简单。有一个使用递归的例子是快速排序(quicksort)。不幸的是,PHP并不擅长递归。Zeev,一个PHP开发人员,说道:“PHP 4.0(Zend)对密集数据使用了栈方式,而不是使用堆方式。也就是说它能容忍的递归函数的数量限制和其他语言比起来明显少。”见bug 1901。这是一个很不好的借口。每一个编程语言都应该提供良好的递归支持。 那么递归的数量限制到底是多少? 多大的数量递归会导致溢出或效率低下? 没人给出具体数据,我也没见到有关的测试文献。 我想无限分类这么一点数据量还不足以把PHP递归给撑死了。 其实PHP递归完全可以加以控制很好的运用。 如果因一点点的不足而不用递归,岂非因噎废食! (2)//我写的下拉列表栏目显示 function treelm(&$row,$id,$repeat){     $pre = str_repeat('  ',$repeat);     $pre .= $repeat > 0 ? '|-' : '';     foreach( $row as $val){         if( $val['parent'] == $id ){             $tmpstr .= "{$pre}{$val['title']}\r\n";             $tmpstr .= treelm($row,$val['id'],$repeat+1);         }     }     return $tmpstr; } (3)1 取得后代分类ID(含自己) //将数据转化成数组,很容易做到     $a_list = array(             1=>array('ID'=>1, 'PARENT'=>0, 'NAME'=>'祖父'),             2=>array('ID'=>2, 'PARENT'=>1, 'NAME'=>'父亲'),             3=>array('ID'=>3, 'PARENT'=>1, 'NAME'=>'叔伯'),             4=>array('ID'=>4, 'PARENT'=>2, 'NAME'=>'自己'),             5=>array('ID'=>5, 'PARENT'=>4, 'NAME'=>'儿子'),             6=>array('ID'=>6, 'PARENT'=>5, 'NAME'=>'孙子'),             7=>array('ID'=>7, 'PARENT'=>2, 'NAME'=>'姐妹'),             8=>array('ID'=>8, 'PARENT'=>3, 'NAME'=>'表亲'),             9=>array('ID'=>9, 'PARENT'=>7, 'NAME'=>'甥儿'),             10=>array('ID'=>10, 'PARENT'=>4, 'NAME'=>'女儿'),             11=>array('ID'=>11, 'PARENT'=>10, 'NAME'=>'外孙'),             12=>array('ID'=>12, 'PARENT'=>5, 'NAME'=>'孙女')             );         //将数组转变成树,因为使用了引用,所以不会占用太多的内存,一行代码搞定         foreach ($a_list as $id => $item) if ($item['PARENT']) $a_list[$item['PARENT']][$item['ID']] = &$a_list[$id];         //获得自己的全部子孙,自己的ID为4         print_r($a_list[4]); //结果如下: /* Array (     [ID] => 4     [PARENT] => 2     [NAME] => 自己     [5] => Array         (             [ID] => 5             [PARENT] => 4             [NAME] => 儿子             [6] => Array                 (                     [ID] => 6                     [PARENT] => 5                     [NAME] => 孙子                 )             [12] => Array                 (                     [ID] => 12                     [PARENT] => 5                     [NAME] => 孙女                 )         )     [10] => Array         (             [ID] => 10             [PARENT] => 4             [NAME] => 女儿             [11] => Array                 (                     [ID] => 11                     [PARENT] => 10                     [NAME] => 外孙                 )         ) ) */ (4) 左右值法无限分类值得深入研究。参见:http://bbs.phpchina.com/thread-92550-1-1.html 关于父子ID法,可以一次性读出存为数组,利用数组来做二叉树或B树实现算法。参见讨论区帖子实现:http://bbs.phpchina.com/thread-81976-1-1.html 四.算法 左右值无限分类实现算法[转] 一、引言 产品分类,多级的树状结构的论坛,邮件列表等许多地方我们都会遇到这样的问题:如何存储多级结构的数据?在PHP的应用中,提供后台数据存储的通常是关系型数据库,它能够保存大量的数据,提供高效的数据检索和更新服务。然而关系型数据的基本形式是纵横交错的表,是一个平面的结构,如果要将多级树状结构存储在关系型数据库里就需要进行合理的翻译工作。接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下: 层级结构的数据保存在平面的数据库中基本上有两种常用设计方法: 1. 毗邻目录模式(adjacency list model) 2. 预排序遍历树算法(modified preorder tree traversal algorithm) 我不是计算机专业的,也没有学过什么数据结构的东西,所以这两个名字都是我自己按照字面的意思翻的,如果说错了还请多多指教。这两个东西听着好像很吓人,其实非常容易理解。 二、模型 这里我用一个简单食品目录作为我们的示例数据。 我们的数据结构是这样的,以下是代码: 1. Food 2. | 3. |---Fruit 4. |    | 5. |    |---Red 6. |    |    | 7. |    |    |--Cherry 8. |    | 9. |    +---Yellow 10. |          | 11. |          +--Banana 12. | 13. +---Meat 14.       |--Beef 15.       +--Pork 复制代码 为了照顾那些英文一塌糊涂的PHP爱好者 1. Food  : 食物 2. Fruit : 水果 3. Red   : 红色 4. Cherry: 樱桃 5. Yellow: 黄色 6. Banana: 香蕉 7. Meat  : 肉类 8. Beef  : 牛肉 9. Pork  : 猪肉 复制代码 三、实现 1、毗邻目录模式(adjacency list model) 这种模式我们经常用到,很多的教程和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则,例子中的数据可以转化成如下的表: 以下是代码: 1. +-----------------------+ 2. |   parent |    name    | 3. +-----------------------+ 4. |          |    Food    | 5. |   Food   |   Fruit    | 6. |   Fruit  |    Green   | 7. |   Green  |    Pear    | 8. |   Fruit  |    Red     | 9. |   Red    |    Cherry  | 10. |   Fruit  |    Yellow  | 11. |   Yellow |    Banana  | 12. |   Food   |    Meat    | 13. |   Meat   |    Beef    | 14. |   Meat   |    Pork    | 15. +-----------------------+ 复制代码 我们看到 Pear 是Green的一个子节点,Green是Fruit的一个子节点。而根节点'Food'没有父节点。 为了简单地描述这个问题, 这个例子中只用了name来表示一个记录。 在实际的数据库中,你需要用数字的id来标示每个节点,数据库的表结构大概应该像这样:id, parent_id, name, descrīption。 有了这样的表我们就可以通过数据库保存整个多级树状结构了。 显示多级树,如果我们需要显示这样的一个多级结构需要一个递归函数。 以下是代码: 复制代码 对整个结构的根节点(Food)使用这个函数就可以打印出整个多级树结构,由于Food是根节点它的父节点是空的,所以这样调用: display_children('',0)。将显示整个树的内容: 1. Food 2.     Fruit 3.         Red 4.             Cherry 5.         Yellow 6.             Banana 7.     Meat 8.         Beef 9.         Pork 复制代码 如果你只想显示整个结构中的一部分,比如说水果部分,就可以这样调用:display_children('Fruit',0); 几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是 "Food >; Fruit >; Red"。 为了得到这样的一个路径我们需要从最深的一级"Cherry"开始, 查询得到它的父节点"Red"把它添加到路径中, 然后我们再查询Red的父节点并把它也添加到路径中,以此类推直到最高层的"Food",以下是代码: ; 复制代码 如果对"Cherry"使用这个函数:print_r(get_path('Cherry')),就会得到这样的一个数组了: 1. Array ( 2.     [0] => Food 3.     [1] => Fruit 4.     [2] => Red 5. ) 复制代码 接下来如何把它打印成你希望的格式,就是你的事情了。 缺点: 这种方法很简单,容易理解,好上手。但是也有一些缺点。主要是因为运行速度很慢,由于得到每个节点都需要进行数据库查询,数据量大的时候要进行很多查询才能完成一个树。另外由于要进行递归运算,递归的每一级都需要占用一些内存所以在空间利用上效率也比较低。 2、预排序遍历树算法 现在让我们看一看另外一种不使用递归计算,更加快速的方法,这就是预排序遍历树算法(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.                          1 Food 18 2.                              | 3.             +------------------------------+ 4.             |                              | 5.         2 Fruit 11                     12 Meat 17 6.             |                              | 7.     +-------------+                 +------------+ 8.     |             |                 |            | 9. 3 Red 6      7 Yellow 10       13 Beef 14   15 Pork 16 10.     |             | 11. 4 Cherry 5    8 Banana 9 复制代码 这样整个树状结构可以通过左右值来存储到数据库中。继续之前,我们看一看下面整理过的数据表。 以下是代码: 1. +----------+------------+-----+-----+ 2. |  parent  |    name    | lft | rgt | 3. +----------+------------+-----+-----+ 4. |          |    Food    | 1   | 18  | 5. |   Food   |   Fruit    | 2   | 11  | 6. |   Fruit  |    Red     | 3   |  6  | 7. |   Red    |    Cherry  | 4   |  5  | 8. |   Fruit  |    Yellow  | 7   | 10  | 9. |   Yellow |    Banana  | 8   |  9  | 10. |   Food   |    Meat    | 12  | 17  | 11. |   Meat   |    Beef    | 13  | 14  | 12. |   Meat   |    Pork    | 15  | 16  | 13. +----------+------------+-----+-----+ 复制代码 注意:由于"left"和"right"在 SQL中有特殊的意义,所以我们需要用"lft"和"rgt"来表示左右字段。 另外这种结构中不再需要"parent"字段来表示树状结构。也就是 说下面这样的表结构就足够了。 以下是代码: 1. +------------+-----+-----+ 2. |    name    | lft | rgt | 3. +------------+-----+-----+ 4. |    Food    | 1   | 18  | 5. |    Fruit   | 2   | 11  | 6. |    Red     | 3   |  6  | 7. |    Cherry  | 4   |  5  | 8. |    Yellow  | 7   | 10  | 9. |    Banana  | 8   |  9  | 10. |    Meat    | 12  | 17  | 11. |    Beef    | 13  | 14  | 12. |    Pork    | 15  | 16  | 13. +------------+-----+-----+ 复制代码 好了我们现在可以从数据库中获取数据了,例如我们需要得到"Fruit"项下的所有所有节点就可以这样写查询语句: 1. SELECT * FROM tree WHERE lft BETWEEN 2 AND 11; 复制代码 这个查询得到了以下的结果。 以下是代码: 1. +------------+-----+-----+ 2. |    name    | lft | rgt | 3. +------------+-----+-----+ 4. |    Fruit   | 2   | 11  | 5. |    Red     | 3   |  6  | 6. |    Cherry  | 4   |  5  | 7. |    Yellow  | 7   | 10  | 8. |    Banana  | 8   |  9  | 9. +------------+-----+-----+ 复制代码 看到了吧,只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构,我们还需要对这样的查询进行排序。用节点的左值进行排序: 1. SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC; 复制代码 剩下的问题如何显示层级的缩进了。 以下是代码:  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来做一个查询。 1. SELECT name FROM tree WHERE lft < 4 AND rgt >; 5 ORDER BY lft ASC; 复制代码 这样就会得到以下的结果: 以下是代码: 1. +------------+ 2. |    name    | 3. +------------+ 4. |    Food    | 5. |    Fruit   | 6. |    Red     | 7. +------------+ 复制代码 那么某个节点到底有多少子孙节点呢?很简单,子孙总数=(右值-左值-1)/2 1. descendants = (right – left - 1) / 2 复制代码 不相信?自己算一算啦。 用这个简单的公式,我们可以很快的算出"Fruit 2-11"节点有4个子孙节点,而"Banana 8-9"节点没有子孙节点,也就是说它不是一个父节点了。 很神奇吧?虽然我已经多次用过这个方法,但是每次这样做的时候还是感到很神奇。 这的确是个很好的办法,但是有什么办法能够帮我们建立这样有左右值的数据表呢?这里再介绍一个函数给大家,这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。 以下是代码: 复制代码 当然这个函数是一个递归函数,我们需要从根节点开始运行这个函数来重建一个带有左右值的树 rebuild_tree('Food',1); 复制代码 这个函数看上去有些复杂,但是它的作用和手工对表进行编号一样,就是将立体多层结构的转换成一个带有左右值的数据表。 那么对于这样的结构我们该如何增加,更新和删除一个节点呢? 增加一个节点一般有两种方法: 第一种,保留原有的name 和parent结构,用老方法向数据中添加数据,每增加一条数据以后使用rebuild_tree函数对整个结构重新进行一次编号。 第二种,效率更高的办法是改变所有位于新节点右侧的数值。举例来说:我们想增加一种新的水果"Strawberry"(草莓)它将成为"Red"节点的最后一个子节点。首先我们需要为它腾出一些空间。"Red"的右值应当从6改成8,"Yellow 7-10 "的左右值则应当改成 9-12。 依次类推我们可以得知,如果要给新的值腾出空间需要给所有左右值大于5的节点 (5 是"Red"最后一个子节点的右值) 加上2。 所以我们这样进行数据库操作: 1. UPDATE tree SET rgt = rgt + 2 WHERE rgt > 5; 2. UPDATE tree SET lft = lft + 2 WHERE lft > 5; 复制代码 这样就为新插入的值腾出了空间,现在可以在腾出的空间里建立一个新的数据节点了, 它的左右值分别是6和7 1. INSERT INTO tree SET lft=6, rgt=7, name='Strawberry'; 复制代码 再做一次查询看看吧!怎么样?很快吧。 四、结语 好了,现在你可以用两种不同的方法设计你的多级数据库结构了,采用何种方式完全取决于你个人的判断,但是对于层次多数量大的结构我更喜欢第二种方法。如果查询量较小但是需要频繁添加和更新的数据,则第一种方法更为简便。 另外,如果数据库支持的话 你还可以将rebuild_tree()和 腾出空间的操作写成数据库端的触发器函数, 在插入和更新的时候自动执行, 这样可以得到更好的运行效率, 而且你添加新节点的SQL语句会变得更加简单。

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档