ITPub博客

首页 > 应用开发 > IT综合 > 用中值排序基数法实现树状结构 (转)

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

原创 IT综合 作者:gugu99 时间:2007-11-01 08:32:32 0 删除 编辑
用中值排序基数法实现树状结构 (转)[@more@]

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


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10748419/viewspace-980299/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    3122
  • 访问量
    2223611