網站運營seo文章大全提供全面的站長運營經驗及seo技術!
在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 [email protected]
if (@id=0)
begin
select @message='要回復的帖子已經被刪除！'
return
end
else
begin
if (@rootid=0) select @[email protected] ——回復的是根貼，取其id為新加貼的rootid
select @endnum=ordernum where [email protected] and ordernum>@begnum order by ordernum
if (@endnum=0)
select @[email protected]+65536 ——回復的是最后一貼
else
select @ordernum=(@[email protected])/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 [email protected]
if (@id=0)
begin
select @message='該帖子不存在！"
return
end
else
begin
select @endnum=ordernum from forum where [email protected] and deep<[email protected] and ordernum>@begnum order by ordernum
if (@endnum=0) ——要刪除的是最后一個子枝
delete from forum where ordernum>[email protected] and ([email protected] or [email protected])
else
delete from forum where ordernum>[email protected] and ordernum<@endnum and ([email protected] or [email protected])
end
顯示存儲過程(略)
總結：由于省去了childnum字段，因此如果想要知道根貼(或子貼)有多少個子貼，則需使用統計方法或增加對應的字段記錄，該問題可不列為樹狀結構討論之列。
