日期:2008-09-30  浏览次数:21380 次

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

    在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     &n