无限分类的思路是怎样的？

Question

抽象的数据结构就是一个树或者森林结构，每一个分类都相当于一个结点，每一个结点都有一个前驱（除了顶级结点）和n个直接后继。
按照这样的分析，数据库中只需要一个主索引字段（[id]）和一个父结点索引号字段（[parent]）就可以实现。
[id]为自动编号
[parent]，顶级结点（顶级分类）的值设为0，顶级分类的直接子分类（二级结点）的[parent]设为顶级结点的[id]值；二级分类的直接子分类（三级结点）的[parent]设为二级分类的[id]；…………以次类推，n级子分类的[parent]设为n-1级的[id]。这样在使用的时候，选择顶级分类，就是SELECT * FROM table WHERE parent=0；某n-1级分类之下的所有n级分类就是："SELECT * FROM table WHERE parent="& rootID.（其中rootid是该n-1级分类的[id]字段值。
思路和数据库设计就是这样，具体的代码我就不给了。

Answer 1

在 文章管理系统 或者论坛等类似的程序里面啊
例如论坛分成“程序”、“娱乐”等大类
然后“程序”下面又可分成 “PHP”、“asp”等小类
然后“PHP”下面又可在分“安装”，“设置”等子类
然后...
假设可以一直细分下去，就是 无限分类 啊

Answer 2

to  N1rvana(焦油坑中的兽神) 按你这样的思路，如果我要把这棵树结构显示出来，岂不是要执行多条sql语句？
效率问题...btw:我问问思路，代码也不是必需的:)

Answer 3

数据表设计三项：Id,ParentId,TypeNameuse databasename;
go
create Table TableName(
Id int default 0 not null auto_increcment,
Parent int default 0,--0 表示根目录。
TypeName char(20) not null,
);
go

Answer 4

to:shuzai() 按照我的思路，要表现出树型结构，也可以只用一条（顶多2条）sql语句。但是代码上需要一点小技巧，无非是往复循环而已，你不妨自己想想怎么作。另外一种做法是在树型结构展开结点的时候再执行Sql语句，起初只显示根级分类。（表面上类似CSDN的效果，具体实现上可能不同）关于这个东西的思路，抽象的数据结构在我看来只有上面说的这一种，如果你熟悉链表应该能够理解。

Answer 5

我大概看过那些程序，不过今天看到一个“关于一种新的分类算法：位编码算法的讨论”的帖子
http://be10.ods.org/avenger/bbs/index.php?act=ST&f=2&t=3073&s=32b8d07f14a4c299b9e82597c4b77985
看看大家有没有更高效率的算法而已：）

Answer 6

嗯，我看了以下楼主说的帖子和文章，是一种我没听过的想法（但只是实现上的不同，抽象的数据结构还是一个道理），不过也就像那个帖子里讨论的结果——未必有大的实用价值和实用效率。而VBB的实现也只是变化了一种形式，而且parentlist: id,id,id的做法在需要显示较为丰富的子类信息时就显得不太够了，只用作一个树型菜单是够了。就像那篇帖子里有位朋友说的“不要被一个新奇的方法蒙住眼睛, 要看清楚本质”，本质就是树的抽象数据结构。

Answer 7

http://expert.csdn.net/Expert/topic/2484/2484597.xml?temp=.6393701

Answer 8

请 N1rvana 把你说的用php写出来，好么？

Answer 9

真的需要无限分类吗？有谁会分个七八级呢？要具体问题具体分析。真要的话可以给每一类建立一个子类字段，然后把所有子类id 保存在这个字段里用“，”分开，sql 查后再切割。但是这种bt表也有问题。

Answer 10

Your data must save like this:
id,topic,child_l,parent,child_r,content
。。
我写的东东 在：
http://sf.linuxforum.net/snippet/detail.php?type=snippet&id=1
没有删除节点的，需要删除节点吗？哈哈
绝对好用！～～～

Answer 11

summer419 设计得数据库过与复杂

Answer 12

无限分类代码！
刚才看见一位朋友想要这方面的资料。偶感兴趣，就写了个！
数据库如下：
-- 建立数据库和表格。
drop database if exists Dbtest1;
create database Dbtest1;
use Dbtest1;
go
create Table type_tree(
id int default '0' not null auto_increment,
parentid int default 0,
typename char(20) not null,
primary key(id),
);
insert into type_tree(parentid,typename) values(0,'a');
insert into type_tree(parentid,typename) values(0,'b');
insert into type_tree(parentid,typename) values(0,'c');
insert into type_tree(parentid,typename) values(0,'d');
insert into type_tree(parentid,typename) values(0,'e');insert into type_tree(parentid,typename) values(1,'f');
insert into type_tree(parentid,typename) values(1,'g');
insert into type_tree(parentid,typename) values(1,'h');insert into type_tree(parentid,typename) values(6,'i');
insert into type_tree(parentid,typename) values(6,'j');insert into type_tree(parentid,typename) values(10,'k');
--tree is a(f(ij(k))gh)bcde
--理论分析的树结构图： afijkghbcde
gophp代码如下：
<?php
//Type Tree;
function TypeTree($id){
if(empty($id)) $id=0;
$hConn=mysql_connect('localhost','root','');
mysql_select_db('dbtest1');
$hResult=mysql_query("select * from type_tree where parentid=".$id,$hConn);
while($obj=mysql_fetch_object($hResult)){
echo $obj->typename."<br/>";
TypeTree($obj->id);
}
}
/*
$hConn=mysql_connect('localhost','root','') or die ('连接失败');
mysql_select_db('dbtest1');
$hResult=mysql_query("select * from type_tree where parentid=0",$hConn) or die (' 查询失败');
while($obj=mysql_fetch_object($hResult)){
echo "<font size=5>".$obj->typename."</font><br/>";
TypeTree($obj->id);
}*/
//两种方法都ok！（测试过！）
TypeTree(0);
?>
运行结果如下：a
f
i
j
k
g
h
b
c
d
e

Answer 13

1、首先，楼主给出的算法实际上是“树”的变形。
2、N1rvana(焦油坑中的兽神) 给出的是基于两叉树遍历的典型结构
3、在数据库中，记录数可视为无限的，所以（2）可认为是无限分类的
4、在数据库中，字段的宽度是有限的。所以他不可能保存“无限分类”的数据
5、就算法而言。递归是遍历树的最好算法，但他受到堆栈的限制。所以依然是“有限”的
6、递归算法可方便的转化成非递归算法，只是需要自己维护中间数据。由于受到内存的限制，依然是“有限”的。受限情况要比递归好些
7、在一般应用中，实际需要的层次是有限的。所以用“中序排序法”效率最高。只是该算法由于受到数字字段精度的限制，使得层次在10层左右。应该说还是足够了

Answer 14

唠叨可以解释一下“中序排序法”吗？google里也没搜着，呵呵

Answer 15

to:blueice2002呵呵，你复制的代码是我写的！

Answer 16

用中值排序基数法实现树状结构——让递归滚一边去 
 廖家远 发表于 2000-07-26 03:07:25 Joy ASP ←返回版面   用中值排序基数法实现树状结构    在BBS的编写中，经常有人问怎样实现树状结构？一个比较不负责任的回答是：使用递归算法。当然，递归是一个可行的办法(二叉树的历遍也好象只能使用递归算法)，但对于BBS来说，这样做势必要进行大量的Sql查询(虽然可以使用存储过程来做，但要从根本上加快速度，则应该考虑更快的算法)。
下面给出一个可行的彻底屏弃递的实现树状结构的算法。    下面给出另一种使用“使用中值排序基数法”实现树状结构：
一、主要思想：增加一个排序基数字段ordernum，回复同一根贴的贴子中插入贴子时，排序基数ordernum取两者的中值。
    为了叙述的简洁，在此只讨论与树状结构有关的字段。在表中增加三个冗余字段，rootid——用于记录根id，deep——用于记录回复的深度(为0时表示根贴)，ordernum——排序基数(关键所在)。表forum与(只列与树状结构有关的字段)：
id   rootid   deep    ordernum
其中id、rootid、deep均为int型(deep可为tinyint型)，ordernum为float型。例：(在此为了简单，使用一个小的起始排序基数，在实际应用中，应使用较大的起始基数，且应取2的整数次幂，如65536=2^16，下面所说的排序均指按ordernum从小到大排序)。
id   rootid    deep    ordernum
1      0        0            0
2      1        1           64
______________________________
3      1        1           32    回复第1贴，取1、2基数的中值即(0+64)/2排序后结果为：
id   rootid    deep    ordernum
1      0        0            0
3      1        1           32
2      1        1           64
______________________________
4      1        2           48   回复第3贴，取3、2的基数中值即(32+64)/2排序后结果为:
id   rootid    deep    ordernum
1      0        0            0
3      1        1           32
4      1        2           48
2      1        1           64
______________________________
5      1        3           56  回复第4贴，取4、2的基数中值即(48+64)/2排序后的结果为：
id   rootid    deep    ordernum
1      0        0            0
3      1        1           32
4      1        2           48
5      1        3           56
2      1        1           64
______________________________
6      1        2           40  回复第3贴，取3、4的基数中值即(32+48)/2排序后的结果为：
id   rootid    deep    ordernum
1      0        0            0
3      1        1           32
6      1        2           40
4      1        2           48
5      1        3           56
2      1        1           64这样排序基数ordernum与回复深度deep一起就实现了如下的树状结构：
id
1
  3
     6
     4
       5
2
二、插入的实现(如何确定排序基数，下面所指贴子均为同一根下的子贴)
(一)根ordernum定为0
(二)第一条回复贴子基数定为2的整数次幂(如65536=2^16，可取更大的数)
(三)回复最后一条贴子时，基数取最后一贴的基数ordernum再加上2的整数次幂(同上)
(四)回复中间的贴子时，基数ordernum取前后贴子的基数中值三、删除的实现
    删除贴子(剪枝)时，只需找出下一个回复深度deep小于或等于要删贴子的回复深度(deep)的贴子，然后将基数ordernum位于两个贴子基数之间的贴子删除即可实现剪枝。
    如上例子中，要删除3贴(基数为32)下的子枝，由于3的深度为1，下一个深度小于或等于1的贴子为2贴(它的基数为64)，则只需删除基数在32至64间(64除外)的贴子就行了。也就是删除了3、6、4、5贴。要删其它亦然。四、显示的实现
    只需执行select * from forum order by rootid+id-sign(rootid)*id desc,ordernum，然后结合deep就可实现树状的显示。
五、具体实现方法(以存储过程为例)加贴存储过程：(省略注册用户检测以及积分部分内容)CREATE PROCEDURE [add] @keyid int,@message varchar(50) OUTPUT  ———keyid为回复的贴子id号，如果是新贴则为0，@message为出错信息
AS
  IF (@keyid=0)
    INSERT INTO forum (rootid,deep,ordernum,……) values(0,0,0,……)
  ELSE
    BEGIN
     DECLARE @rootid int,@id int,@deep int,@begnum float,@endnum float,@ordernum float
     SELECT @rootid=0,@id=0,@deep=0,@begnum=0,@endnum=0,@ordernum=0
     SELECT @rootid=rootid,@id=id,@begnum=ordernum,@deep=deep from forum where id=@keyid
     IF (@id=0)
       BEGIN
        SELECT @message='要回复的贴子已经被删除！'
        return
       END
     ELSE
       BEGIN
        IF (@rootid=0) SELECT @rootid=@id  ——回复的是根贴，取其id为新加贴的rootid
        SELECT @endnum=ordernum where rootid=@rootid and ordernum>@begnum order by ordernum
        IF (@endnum=0)
          SELECT @ordernum=@begnum+65536   ——回复的是最后一贴
        ELSE
          SELECT @ordernum=(@begnum+@endnum)/2  ——关键，取排序基数中值
        INSERT into forum (rootid,deep,ordernum,……) values(@rootid,@deep+1,@ordernum,……)
       END
    END
  Select @message='成功'
  return

Answer 17

剪枝存储过程：(省略注册用户检测以及积分部分内容)
CREATE PROCEDURE [del] @keyid int,@message varchar(50) OUTPUT  ———keyid为要删除的贴子id号，如果是新贴则为0，@message为出错信息
AS
DECLARE @rootid int,@id int,@deep int,@begnum float,@endnum float
SELECT @rootid=0,@deep=0,@begnum=0,@endnum=0,@id=0
SELECT @id=id,@begnum=ordernum,@rootid=rootid,@deep=deep from forum where id=@keyid
IF (@id=0)
  BEGIN
   SELECT @message='该贴子不存在！"
   return
  END
ELSE
  BEGIN
   SELECT @endnum=ordernum from forum where rootid=@rootid and deep<=@deep and ordernum>@begnum order by ordernum
   IF (@endnum=0)    ——要删除的是最后一个子枝
     DELETE FROM forum where ordernum>=@begnum and (rootid=@rootid or id=@rootid)
   ELSE
     DELETE FROM forum where ordernum>=@begnum and ordernum<@endnum and (rootid=@rootid or id=@rootid)
  END显示存储过程(略)总结：由于省去了childnum字段，因此如果想要知道根贴(或子贴)有多少个子贴，则需使用统计方法或增加对应的字段记录，该问题可不列为树状结构讨论之列。“中值排序基数法实现树状结构”的补充    由于一时疏忽，造成了此法“对于int类型的基数字段，对原始贴的回复只能有31个；numeric类型的基数字段，对原始贴的回复也不能超过120个”(实际上是对于int型字段，原始贴的回复第32个以上的树状结构显示开始紊乱，对于numeric型的基数字段，原始贴的回复从121个以上树状结构显示开始紊乱——回复并不会出问题)，这是由于计算机存储精度引起的。
    我们可以将加贴的存储过程修改一下(加进前面加上**号的行)以限制到了一定深度(在特定数据类型下，基数无法分辨)的时候不再以树状结构显示(而采用平显——平行显示，这样做虽然有点象折衷的做法，但在实际上由于浏览器等的限制——即使在深度100的时候能以树状结构显示，但从你的浏览器看来的树状结构的结果仍然不是清晰的——屏幕宽度不够，会折行呗)。加贴存储过程：CREATE PROCEDURE [add] @keyid int,@message varchar(50) OUTPUT  ———keyid为回复的贴子id号，如果是新贴则为0，@message为出错信息
AS
  IF (@keyid=0)
    INSERT INTO forum (rootid,deep,ordernum,……) values(0,0,0,……)
  ELSE
    BEGIN
     DECLARE @rootid int,@id int,@deep int,@begnum float,@endnum float,@ordernum float
     SELECT @rootid=0,@id=0,@deep=0,@begnum=0,@endnum=0,@ordernum=0
     SELECT @rootid=rootid,@id=id,@begnum=ordernum,@deep=deep from forum where id=@keyid
     IF (@id=0)
       BEGIN
        SELECT @message='要回复的贴子已经被删除！'
        return
       END
     ELSE
       BEGIN
        IF (@rootid=0) SELECT @rootid=@id  ——回复的是根贴，取其id为新加贴的rootid
        SELECT @endnum=ordernum where rootid=@rootid and ordernum>@begnum order by ordernum
        IF (@endnum=0)
          SELECT @ordernum=@begnum+65536   ——回复的是最后一贴，可以在此限制@ordernum的范围以防溢出
        ELSE
**          BEGIN
**            IF @endnum-@begnum>1           ——精度仍能分辨。此处的1为精度标记，适合于基数字段为int，如果基数字段为numeric字段，请酌情选娶(呸呸呸，错别字来了)，目的是使基数精度过小时限制深度增加，避免显示时的紊乱
**              SELECT @ordernum=(@begnum+@endnum)/2,@deep=@deep+1  ——关键，取排序基数中值
**            ELSE
**              SELECT @ordernum=@begnum     ——限制深度不能再增加，此贴与回复贴平行显示，如果存在parentid字段，则要取parentid和回复贴的parentid一样
**          END 
**        INSERT into forum (rootid,deep,ordernum,……) values(@rootid,@deep,@ordernum,……)
       END
    END
  Select @message='成功'
  return剪枝存储过程改为：CREATE PROCEDURE [del] @keyid int,@message varchar(50) OUTPUT  ———keyid为要删除的贴子id号，如果是新贴则为0，@message为出错信息
AS
DECLARE @rootid int,@id int,@deep int,@begnum float,@endnum float
SELECT @rootid=0,@deep=0,@begnum=0,@endnum=0,@id=0
SELECT @id=id,@begnum=ordernum,@rootid=rootid,@deep=deep from forum where id=@keyid
IF (@id=0)
  BEGIN
   SELECT @message='该贴子不存在！"
   return
  END
ELSE
  BEGIN
   SELECT @endnum=ordernum from forum where rootid=@rootid and deep<=@deep and ordernum>@begnum order by ordernum
   IF (@endnum=0)    ——要删除的是最后一个子枝或是根贴
     DELETE FROM forum where ordernum>=@begnum and (rootid=@rootid or id=@rootid)
   ELSE
**     BEGIN
**       IF @begnum=@endnum
**         DELETE FROM forum where id=@id and (rootid=@rootid or id=@rootid) ——已经受精度限制的枝，只删当前贴
**       ELSE
**         DELETE FROM forum where ordernum>=@begnum and ordernum<@endnum and (rootid=@rootid or id=@rootid)
**     END
  END
   虽然是限制，但此限制应该是必须的，因为实际上的回复深是不能太大的(就象我在这里灌到八九层的时候，讨饭猫就大叫“打住打住”了，呵呵)   欢迎访问我的个人主页http://swuse.yeah.net(原来bigeagle是说我这一句话“目的明显啊”)================
转贴一个给你看看，虽然是用asp实现的。但算法与实现语言是无关的。

Answer 18

本来想把我的代码贴上来，一看，光模型就有600多行，而且还是个派生类，算了。
给出核心吧
    /**  BEGIN function
    *
    *   作者：偶然
    *   功能：递归出下拉菜单
    *   时间：2003.7.5
    *   变量：
    *   返回：none
    *   示例：
    *
    */
    function select($fid,$num,$i,$lang_type)
    {
        global $nav;
        $num++;
        $sql="select fid,cid,c_name from category where fid='$fid' and lang_type='$lang_type' and c_is_moved=0 order by cid desc";
        $query=$this->query($sql);
        while($array=$this->fetch_array($query))
        {
            $i=count($nav);
            $nav[$i]["num"]=$num;
            $nav[$i]["fid"]=$array['fid'];
            $nav[$i]["navid"]=$array['cid'];
            $nav[$i]["navname"]=$array['c_name'];
            $this->select($nav[$i]["navid"],$num,$i,$lang_type);
            $i++;
        }
        Return $nav;
    }
加入节点很简单，只要找着父节点就行了。
删除节点和转移比较麻烦，我花了近两百行才写完，就不帖了。

Answer 19

数据表结构
CREATE TABLE `ewb_t_dept` (
  `BD_DEPTID` int(4) NOT NULL default '0',
  `BD_NAME` varchar(40) default NULL,
  `BD_SUPERID` int(4) default '0',
  `BD_DESC` varchar(200) default NULL,
  PRIMARY KEY  (`BD_DEPTID`),
  KEY `BD_DEPTID` (`BD_DEPTID`)
) TYPE=MyISAM;函数：
/*------------------------------------------------------------
    *   Function:       FetchChildDept
    *   Description:    取得所有下级分类列表
    *   Parameters:     $AoDB         - 数据库联接ID
    *          $AiDeptID     - 当前部门ID
*              $AsOrderby    - 返回时的排序方式数组，若为0按数据库返回的顺序。
    *   Return:         成功返回$aResult，否则返回false
    ------------------------------------------------------------*/
function FetchChildDept(&$AoDB, $AiDeptID, $AsOrderby="")
{
//获得下级部门记录数
$sCountSQL = "SELECT COUNT(*) FROM EWB_T_DEPT WHERE BD_SUPERID = " . $AiDeptID;
$rsCount = $AoDB->Execute($sCountSQL);
if ($rsCount)
{
$aResult[0]["COUNT"] = $rsCount->fields[0];
$rsCount->Close();
}
else return false;

//如果下级部门记录数等于0，则返回$aResult
if ($aResult[0]["COUNT"] == 0) return $aResult;

//否则查询获得下级部门ID、部门名称
$sSelSQL = "SELECT BD_DEPTID, BD_NAME FROM EWB_T_DEPT WHERE BD_SUPERID = " . $AiDeptID;
if ($AsOrderby != "0" && $AsOrderby != "")
$sSelSQL .=  " ORDER BY " . $AsOrderby;
$rsSel = $AoDB->Execute($sSelSQL);
if ($rsSel)
{
$i = 1;
while (!$rsSel->EOF)
{
$aResult[$i]["ID"]   = $rsSel->fields[0];
$aResult[$i]["NAME"] = $rsSel->fields[1];
$i++;
$rsSel->MoveNext();
}
$rsSel->Close();
return $aResult;
}
else return false;
}
/*------------------------------------------------------------
    *   Function:       FetchDeptTree
    *   Description:    返回所有部门信息列表
    *   Parameters:     $AoDB         - 数据库联接ID
*       $AiDeptID     - 最上级部门的上级部门ID，默认值为0。
    *   Return:         成功返回$aResult，否则返回false
    ------------------------------------------------------------*/
    function FetchDeptTree(&$AoDB,$AiDeptID=0)
    {
$aResult    = Array();
$aChildDept = Array();

//获得子部门ID、子部门名称、子部门数
$aChildDept = FetchChildDept(&$AoDB, $AiDeptID);
$aChildDeptNum = $aChildDept[0]["COUNT"];
$i = 0;
while($i < $aChildDeptNum)
{
$aResult[$i]["ID"]       = $aChildDept[$i+1]["ID"];
$aResult[$i]["NAME"]     = $aChildDept[$i+1]["NAME"];
$aResult[$i]["URL"]      = "../admin/ListDeptUser.php?deptid=".$aChildDept[$i+1]["ID"];
$aResult[$i]["CHILDREN"] = FetchDeptTree(&$AoDB, $aResult[$i]["ID"]);
$i++;
}
return $aResult;
    }