用中值排序基数法实现树状结构

核心提示： 在BBS的编写中，经常有人问怎样实现树状结构？一个比较不负责任的回答是：使用递归算法，用中值排序基数法实现树状结构，当然，递归是一个可行的办法(二叉树的历遍也好象只能使用递归算法)，因此如果想要知道根贴(或子贴)有多少个子贴，则需使用统计方法或增加对应的字段记录，但对于BBS来说，这样做势必要进行大量的Sql查询(

　  在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

剪枝存储过程：(省略注册用户检测以及积分部分内容)

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字段，因此如果想要知道根贴(或子贴)有多少个子贴，则需使用统计方法或增加对应的字段记录，该问题可不列为树状结构讨论之列。