代码之美——简单无限分类分析

1、引言
无限分类在很多应用中是会经常用到的，比如CMS的文章分类表，工厂生产的BOM物料，在线商店Products产品分类表，等等。
很多初学者对无限分类的算法还是不能深刻的理解，七月十五在这里献丑，为大家初略的讲述一下无限分类表的基本算法。
关键词： 无限分类, 族谱, 递归, SQL

2、数据结构（族谱）
我们以一个家族的族谱来构建一个无限分类。其数据结构如下。[code]
+---------------------------+
| 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      |    孙女     |
+----+--------+-------------+
| .. | ...    |    ....     |
+---------------------------+
[/code]可以看到我们只需要设计一个ID跟一个PARENT(来自其内部ID)，就可以构建出整个族谱之间的联系。
比如：
1)、已知任一ID，可以求得祖先族系树
如已知 ID=11（外孙）, 很容易就跟据ID跟PARENT的关系查得祖先树(含自身)如下：[code]
array(
    array(11, 10, 外孙),
    array(10, 4, 女儿),
    array(4, 2, 自己),
    array(2, 1, 父亲)
    array(1, 0, 祖父)
)
[/code]2)、已知任一ID，可以求其后代(含自己)列表
比如已知ID=4（自己），跟据ID和PARENT关系可以查得后代如下：[code]
array(
    array(4, 2, 自己),
    array(5, 4, 儿子),
    array(6, 5, 孙子),
    array(12, 5, 孙女),
    array(10, 4, 女儿),
    array(11, 10, 外孙)
)
[/code]3、SQL
根据以上的数据结构我们创建一个MySQL<span href="tag.php?name=%CA%FD%BE%DD%BF%E2" class="t_tag">数据库</span>[code]
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, '孙女');
[/code]4、算法
其余的与无限分类无关的算法，我这里就不演示了。与无限分类有关的算法有两个。
其一、祖先树。（我们以一维数组来取得所有列的详细数据）
其二、后代表。（因为涉及到实际应用的关联操作，我们这里给出求出一组指定id的所有后代id集合的一维数组的方法）
1)、祖先树
以指定的id求得其父母辈的id，如果存在，则再以求得id求父母辈的id，直到求不到其父母辈的id为止，返回一个二维数组。
2)、后代ID表
以指定的id求得其子女的id,如果存在，则再以求得的id来求子女id，直到求不到其子女id为止，返回一个含有所有求得id的一维数组。

5、代码
[php]
<?php
/**
* 族谱
*
* 以一个实例演示简单无限分类的算法
*
* @copyrihgt HentStudio, 2008
* @author 七月十五 <[email protected]>
* @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、附件
family.zip
7、结语
当然以上只实现了无限分类的基本算法，对于无限分类的数据结构的分析还有很多的版本，不同的版本实现也是不一样的。
我这里只给出var_dump的内容，具体到应用里如何使用，相信大家都能掌握。实用代码我就不画蛇添足了。帖图两张以飨读者。
如果无限分类能在SQL层面求得结果的话那是最好的，比如以一句或若干句SQL求得，或以SQL的存储过程求得。七月十五才疏学浅，目前只能从外部程序（PHP）层面实现了无限分类的上述功能。如果大家有更好的解决方法，欢迎指教，谢谢。


祖先导航树



删除指定的IDs及其所有后代


[以上两图来自LeoPHP的example的RBAC]

8、补充
一直想利用一句SQL来求解，以SQL递归可以实现。
现公布第二个问题的SQL递归不完善的求解方法（不含己身）
但这个SQL还不能实现任意深度的查询。[code]
SELECT p2 . *
FROM family AS p1, family AS p2
WHERE p1.id = p2.parent
AND (
p1.id = 4
OR p1.parent = 4
)
[/code]第一个问题的SQL就留给大家思考写出来吧。

[本文为七月十五原创，转载请注明出自PHPChina]

支持一下

在这里发贴可以赚图书?

效率效率

呵呵，按照中国的传统来说，外孙的祖先，不应该算到自己这个族谱上吧
:lol:

俺这个是超级族谱:lol:

还不一样是递归吗，还有别的方法吗？

需要花点时间才能看明白

好复杂啊！

把东西选出来放在一个大数组里再操作，只查一次表，这样会查询多太多次数据库
放到一个大数组里后，找到的一个id就把大数组里相应项删除，这查少做多少无用循环

呵呵，关注中

好难看懂了

真厉害。。

lz，你的这个算法，小数据量还好，要是大数据量，你的数据库会成为瓶颈的~~；
如果有多棵树的话，你的效率也会下降~~
建议：
1. 增加一个rootid的字段，用来标识一个节点属于那个树的分类；
2. 增加一个path的字段，用来记录，从根节点到自己的路径；
3. 增加一个level的字段，记录自己的所属层级；

获取一个节点的前驱节点时候，可以通过path，一次性获得，之需要一个sql语句；
获取一个节点的后继结点的时候，可以通过path将路径与自己路径前面部分相同的节点取出即可；
获取多棵树的节点（分开显示），通过rootid一次性获得后，在php程序里面做相应的计算。

这种方法适合于查找较多的情况，但更新一个节点或者删除一个节点需要将后继结点都更新。
建议尽量将压力放在PHP程序上，而不是数据库上。

这是我的一点想法，请大家讨论吧~~

下载不到，发个给我好吗？[email protected]

学习当中。。。。。