|
使用“使用中值排序基数法”实现树状结构一 |
| 作者：ItWen收集整理 来源：www.itwen.com 更新时间：2006-10-27 |
|
|
[ 收藏此页到: 天天
| 和讯
| 博采
| ViVi
| 狐摘
| 我摘
]
|
|
在BBS的编写中，经常有人问怎样实现树状结构？一个比较不负责任的回答是：使用递归算法。当然，递归是一个可行的办法(二叉树的历遍也好象只能使用递归算法)，但对于BBS来说，这样做势必要进行大量的Sql查询(虽然可以使用存储过程来做，但要从根本上加快速度，则应该考虑更快的算法)。
下面给出一个可行的彻底屏弃递的实现树状结构的算法。
下面给出另一种使用“使用中值排序基数法”实现树状结构：
一、主要思想：增加一个排序基数字段ordernum，回复同一根贴的贴子中插入贴子时，排序基数ordernum取两者的中值。
为了叙述的简洁，在此只讨论与树状结构有关的字段。
在表中增加三个冗余字段，rootid——用于记录根id，deep——用于记录回复的深度(为0时表示根贴)，ordernum——排序基数(关键所在)。
表forum与(只列与树状结构有关的字段)：
id rootid deepordernum
其中id、rootid、deep均为int型(deep可为tinyint型)，ordernum为float型。
例：(在此为了简单，使用一个小的起始排序基数，在实际应用中，应使用较大的起始基数，且应取2的整数次幂，如65536=2^16，下面所说的排序均指按ordernum从小到大排序)。
id rootiddeepordernum
1000
211 64
______________________________
311 32回复第1贴，取1、2基数的中值即(0+64)/2
排序后结果为：
id rootiddeepordernum
1000
311 32
211 64
______________________________
412 48 回复第3贴，取3、2的基数中值即(32+64)/2
排序后结果为:
id rootiddeepordernum
1000
311 32
412 48
211 64
______________________________
513 56回复第4贴，取4、2的基数中值即(48+64)/2
排序后的结果为：
id rootiddeepordernum
1000
311 32
412 48
513 56
211 64
______________________________
612 40回复第3贴，取3、4的基数中值即(32+48)/2
排序后的结果为：
id rootiddeepordernum
1000
311 32
612 40
412 48
513 56
211 64
这样排序基数ordernum与回复深度deep一起就实现了如下的树状结构：
id
1
3
6
4
5
2
二、插入的实现(如何确定排序基数，下面所指贴子均为同一根下的子贴)
(一)根ordernum定为0
(二)第一条回复贴子基数定为2的整数次幂(如65536=2^16，可取更大的数)
(三)回复最后一条贴子时，基数取最后一贴的基数ordernum再加上2的整数次幂(同上)
(四)回复中间的贴子时，基数ordernum取前后贴子的基数中值
三、删除的实现
删除贴子(剪枝)时，只需找出下一个回复深度deep小于或等于要删贴子的回复深度(deep)的贴子，然后将基数ordernum位于两个贴子基数之间的贴子删除即可实现剪枝。
本篇文章共2页，此页为首页 下一页
|
引用提示：
内容页面：使用“使用中值排序基数法”实现树状结构一 --- ASP
作者：ItWen收集整理
来源：www.ITWEN.com 计算机基础教程网
|
版权申明：
本网站所有内容，未经注明的，版权一律属于计算机基础教程网(ＩＴＷＥＮ.com)制作署所有。转载引用本网站的原创文章，请务必注明信息来源，标明“计算机基础教程网(ＩＴＷＥＮ.com)”字样。
计算机基础教程网(ＩＴＷＥＮ.com)依法保护知识产权，如果我们的文章有涉及或侵犯您的有关权益，请即时与我们联系， 注明网址及文章，我们会即时处理或删除， 感谢您的合作！
|
【大 中 小】
【返回站点首页】【打印本页】【关闭本页】
|
最近更新 
设为主页 
将使用“使用中值排序基数法”实现树状结构一 加入收藏 
[投稿登
陆] [问题求解或论坛登 陆]
资料搜索