1、引言
无限分类在很多应用中是会经常用到的，比如CMS的文章分类表，工厂生产的BOM物料，在线商店Products产品分类表，等等。
很多初学者对无限分类的算法还是不能深刻的理解，七月十五在这里献丑，为大家初略的讲述一下无限分类表的基本算法。
关键词： 无限分类, 族谱, 递归, SQL
2、数据结构（族谱）
我们以一个家族的族谱来构建一个无限分类。其数据结构如下。- +---------------------------+
- | 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=11（外孙）, 很容易就跟据ID跟PARENT的关系查得祖先树(含自身)如下：- array(
- array(11, 10, 外孙),
- array(10, 4, 女儿),
- array(4, 2, 自己),
- array(2, 1, 父亲)
- array(1, 0, 祖父)
- )
比如已知ID=4（自己），跟据ID和PARENT关系可以查得后代如下：- array(
- array(4, 2, 自己),
- array(5, 4, 儿子),
- array(6, 5, 孙子),
- array(12, 5, 孙女),
- array(10, 4, 女儿),
- array(11, 10, 外孙)
- )
根据以上的数据结构我们创建一个MySQL<span href="tag.php?name=%CA%FD%BE%DD%BF%E2" class="t_tag">数据库</span>- CREATE DATABASE family DEFAULT CHARSET 'utf8';
- USE family;
- CREATE TABLE family (
- id INT(10) UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
- parent INT(10) UNSIGNED NOT NULL DEFAULT '0',
- name CHAR(30) NOT NULL DEFAULT '',
- UNIQUE KEY (parent, name)
- );
- INSERT INTO family (id, parent, name )
- VALUES
- ( 1, 0, '祖父'),
- ( 2, 1, '父亲'),
- ( 3, 1, '叔伯'),
- ( 4, 2, '自己'),
- ( 5, 4, '儿子'),
- ( 6, 5, '孙子'),
- ( 7, 2, '姐妹'),
- ( 8, 3, '表亲'),
- ( 9, 7, '甥儿'),
- ( 10, 4, '女儿'),
- ( 11, 10, '外孙'),
- ( 12, 5, '孙女');
其余的与无限分类无关的算法，我这里就不演示了。与无限分类有关的算法有两个。
其一、祖先树。（我们以一维数组来取得所有列的详细数据）
其二、后代表。（因为涉及到实际应用的关联操作，我们这里给出求出一组指定id的所有后代id集合的一维数组的方法）
1)、祖先树
以指定的id求得其父母辈的id，如果存在，则再以求得id求父母辈的id，直到求不到其父母辈的id为止，返回一个二维数组。
2)、后代ID表
以指定的id求得其子女的id,如果存在，则再以求得的id来求子女id，直到求不到其子女id为止，返回一个含有所有求得id的一维数组。
5、代码
[php]
<?php
/**
* 族谱
*
* 以一个实例演示简单无限分类的算法
*
* @copyrihgt HentStudio, 2008
* @author 七月十五 <zergdo@gmail.com>
* @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 = <span href="tag.php?name=mysql" class="t_tag">mysql</span>_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 '<pre>';
var_dump(getForefathers(11)); /* 输出ID=11的祖先树 */
var_dump(getOffspring(array(3, 4))); /* 输出ID=3及ID=4的后代ID表 */
echo '</pre>';
[/php]
6、附件
7、结语
当然以上只实现了无限分类的基本算法，对于无限分类的数据结构的分析还有很多的版本，不同的版本实现也是不一样的。
我这里只给出var_dump的内容，具体到应用里如何使用，相信大家都能掌握。实用代码我就不画蛇添足了。帖图两张以飨读者。
如果无限分类能在SQL层面求得结果的话那是最好的，比如以一句或若干句SQL求得，或以SQL的存储过程求得。七月十五才疏学浅，目前只能从外部程序（PHP）层面实现了无限分类的上述功能。如果大家有更好的解决方法，欢迎指教，谢谢。
[以上两图来自LeoPHP的example的RBAC]
8、补充
一直想利用一句SQL来求解，以SQL递归可以实现。
现公布第二个问题的SQL递归不完善的求解方法（不含己身）
但这个SQL还不能实现任意深度的查询。- SELECT p2 . *
- FROM family AS p1, family AS p2
- WHERE p1.id = p2.parent
- AND (
- p1.id = 4
- OR p1.parent = 4
- )
[本文为七月十五原创，转载请注明出自PHPChina] |
发表于 2008-9-23 17:03
| 
发表于 2008-9-23 17:39
| 
