用中值排序基数法实现树状构造[MSSQL防范]

    在BBS的编写中,常常有人问怎样实现树状构造?一个对比不负责任的答复是:利用递归算法.当然,递归是一个可行的办法

(二叉树的历遍也好象只能利用递归算法),但关于BBS来说,这样做势必要举行大量的Sql查询(固然可以利用存储历程来做,但要从根本上加快速度,则应当考虑更快的算法).

下面给出一个可行的完好摒弃递的实现树状构造的算法.

    下面给出另一种利用"利用中值排序基数法"实现树状构造:

1、主要思惟:增添一个排序基数字段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

2、插入的实现(若何肯定排序基数,下面所指贴子均为同一根下的子贴)

(一)根ordernum定为0

(二)第一条答复贴子基数定为2的整数次幂(如65536=2^16,可取更大的数)

(三)答复最后一条贴子时,基数取最后一贴的基数ordernum再加上2的整数次幂(同上)

(四)答复中间的贴子时,基数ordernum取前后贴子的基数中值

3、删除的实现

    删除贴子(剪枝)时,只需找出下一个答复深度deep小于或等于要删贴子的答复深度(deep)的贴子,然后将基数ordernum位于两个贴子基数之间的贴子删除便可实现剪枝.

    如上例子中,要删除3贴(基数为32)下的子枝,由于3的深度为1,下一个深度小于或等于1的贴子为2贴(它的基数为64),则只需删除基数在32至64间(64除外)的贴子就行了.也就是删除了3、6、4、5贴.要删别的亦然.

4、显示的实现

    只需履行select * from forum order by rootid+id-sign(rootid)*id desc,ordernum,然后结合deep便可实现树状的显示.

5、具体实现办法(以存储历程为例)

加贴存储历程:(省略注册用户检测以及积分部份内容)

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字段,因此假如想要知道根贴(或子贴)有多少个子贴,则需利用统计办法或增添对应的字段记录,该问题可不列为树状构造谈论之列.