父子ID法无限分类的简单实现算法
父子ID法无限分类的简单实现算法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 | 孙女 |
+----+--------+-------------+
| .. | ... | .... |
+---------------------------+复制代码可以看到我们只需要设计一个ID跟一个PARENT(来自其内部ID)，就可以构建出整个族谱之间的联系。
比如：
1)、已知任一ID，可以求得祖先族系树
如已知 ID=11（外孙）, 很容易就跟据ID跟PARENT的关系查得祖先树(含自身)如下： array(
array(11, 10, 外孙),
array(10, 4, 女儿),
array(4, 2, 自己),
array(2, 1, 父亲)
array(1, 0, 祖父)
)
复制代码2)、已知任一ID，可以求其后代(含自己)列表
比如已知ID=4（自己），跟据ID和PARENT关系可以查得后代如下： array(
array(4, 2, 自己),
array(5, 4, 儿子),
array(6, 5, 孙子),
array(12, 5, 孙女),
array(10, 4, 女儿),
array(11, 10, 外孙)
)复制代码3、SQL
根据以上的数据结构我们创建一个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, '孙女');复制代码4、算法
其余的与无限分类无关的算法，我这里就不演示了。与无限分类有关的算法有两个。
其一、祖先树。（我们以一维数组来取得所有列的详细数据）
其二、后代表。（因为涉及到实际应用的关联操作，我们这里给出求出一组指定id的所有后代id集合的一维数组的方法）
1)、祖先树
以指定的id求得其父母辈的id，如果存在，则再以求得id求父母辈的id，直到求不到其父母辈的id为止，返回一个二维数组。
2)、后代ID表
以指定的id求得其子女的id,如果存在，则再以求得的id来求子女id，直到求不到其子女id为止，返回一个含有所有求得id的一维数组。
5、代码
<?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>';
6、附件
2008-9-23 17:03
7、结语
当然以上只实现了无限分类的基本算法，对于无限分类的数据结构的分析还有很多的版本，不同的版本实现也是不一样的。
我这里只给出var_dump的内容，具体到应用里如何使用，相信大家都能掌握。实用代码我就不画蛇添足了。帖图两张以飨读者。
如果无限分类能在SQL层面求得结果的话那是最好的，比如以一句或若干句SQL求得，或以SQL的存储过程求得。七月十五才疏学浅，目前只能从外部程序（PHP）层面实现了无限分类的上述功能。如果大家有更好的解决方法，欢迎指教，谢谢。
祖先导航树
2008-9-23 17:03删除指定的IDs及其所有后代
2008-9-23 17:03
[以上两图来自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
)复制代码第一个问题的SQL就留给大家思考写出来吧。
页:
[1]