php无限分类.docx
《php无限分类.docx》由会员分享，可在线阅读，更多相关《php无限分类.docx（25页珍藏版）》请在冰点文库上搜索。
php无限分类
无限分类
一．父子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代码
php
/**
* 族谱
*
* 以一个实例演示简单无限分类的算法
*
* @copyrihgt HentStudio, 2008
* @author 七月十五 <[email=zergdo@]zergdo@[/email]>
* @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 = name=mysql" class="t_tag">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开发人员，说道：
“PHP4.0（Zend）对密集数据使用了栈方式，而不是使用堆方式。
也就是说它能容忍的递归函数的数量限制和其他语言比起来明显少。
”见bug1901。
这是一个很不好的借口。
每一个编程语言都应该提供良好的递归支持。
那么递归的数量限制到底是多少？
多大的数量递归会导致溢出或效率低下？
没人给出具体数据，我也没见到有关的测试文献。
我想无限分类这么一点数据量还不足以把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）
左右值法无限分类值得深入研究。
参见：
关于父子ID法，可以一次性读出存为数组，利用数组来做二叉树或B树实现算法。
参见讨论区帖子实现：
四．算法
左右值无限分类实现算法[转]
一、引言
产品分类，多级的树状结构的论坛，邮件列表等许多地方我们都会遇到这样的问题：
如何存储多级结构的数据？
在PHP的应用中，提供后台数据存储的通常是关系型数据库，它能够保存大量的数据，提供高效的数据检索和更新服务。
然而关系型数据的基本形式是纵横交错的表，是一个平面的结构，如果要将多级树状结构存储在关系型数据库里就需要进行合理的翻译工作。
接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下：
层级结构的数据保存在平面的数据库中基本上有两种常用设计方法：
1.毗邻目录模式（adjacencylistmodel）
2.预排序遍历树算法（modifiedpreordertreetraversalalgorithm）
我不是计算机专业的，也没有学过什么数据结构的东西，所以这两个名字都是我自己按照字面的意思翻的，如果说错了还请多多指教。
这两个东西听着好像很吓人，其实非常容易理解。
二、模型
这里我用一个简单食品目录作为我们的示例数据。
我们的数据结构是这样的，以下是代码：
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、毗邻目录模式（adjacencylistmodel）
这种模式我们经常用到，很多的教程和书中也介绍过。
我们通过给每个节点增加一个属性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。
有了这样的表我们就可以通过数据库保存整个多级树状结构了。
显示多级树，如果我们需要显示这样的一个多级结构需要一个递归函数。
以下是代码：
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）。
将显示整个树的内容：
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"。
为了得到这样的一个路径我们需要从最深的一级"
升级会员 