整理一个树型问题的解决方法

我的问题：

1.一个销售系统,设有各级代理商,每个代理商的表是这样设计的

数据库结构
表1: 代理商资料表
[id] 自动编号 编号
[lishu] 长整型 隶属字段
[xiaoshoue] 长整型 销售额
[ticheng] 长整型 提成
[add_date] 日期/时间 代理商添加时间

要求
1.让代理商分级,指出某个代理商可以算出他的上级代理商和下级代理商.

2.提成的比例按照销售额的多少来定,销售额2000以下的提成比例是20%,销售额在2000到6000之间的提成比例是25%,销售额在6000到18000之间的提成比例是30%,销售额在18000到30000之间的提成比例是35%,销售额在30000到60000之间的提成比例是40%,销售额在60000以上的提成比例是45%.

3.提成是这样算的,比如说第一个月的销售额是2000,那么他的提成是2000*20%=400,然后如果第二个月的销售额又是2000,那么他的总销售额就是第一个月加第二个月的2000+2000=4000,因为4000界于2000到6000之间,所以他这个月的提成比例应该是25%,那么他这个月的提成是本月的销售额乘以25%,就是2000*25%=500

4.下级代理商新增的销售额要添加到他上级代理商的销售额里面,比如说A为一级代理商,B为A的下级代理商,也就是二级代理商,B这个月的销售额是2000,A这个月的销售额也是3000,但因为B是A的下级代理商,所以A本月的销售额就是B本月的的销售额加上他自己本月的销售额.2000+3000=4000
但是A本月的提成不应该是5000乘以25%,应该是他本月自己的销售额3000*25%然后加上他的下级代理商给他增加的提成差额2000*25%-2000*20%整个算下来A这个月的应得提成就是3000*25%+2000*25%-2000*20%=5000*25%-2000*20%=850,但是A不可能只有B一个代理商,他和它其它所有的下级代理商的提成差额都是这样计算的.如果A这个月自己的销售额为0,B的销售额是2000那么A这个月的应得提成就是2000*20%-2000*20%=0,也就是如果A和B同一销售额段的话A就不会从B那里得到差额提成.但A不可能就B一个下级代理,所以A的就算自己这个月本身销售额为0,他有2个下级代理商,并且每个下级代理商销售额为2000,他这个月的应得提成就是4000*25%-2000*20%-2000*20%=200

5.如果某代理商的下级代理商有1个销售额在6000以上的,那么他们属于同一个提成比例段的,所以他们之间没有差额提成,但是如果有3个下级代理商的销售额在60000以上的,那么他可以从这3个下级代理商各自的多余60000的部分的5%的提成.

还有一些其它详细的要求,我先不说了,其中1.2.3.5和4的部分功能我已经实现了.主要是4的算法太难,感觉又要重新设计数据结构似的,要不就算我一点一点做出来,效率一定会很慢的,大家看看要求4的具体实现有没有比较经典的算法和解决方案,谢谢指点了,如果实在是太麻烦偶短时间学不会的话,这个工程偶就不做了,就算以前编的部分是自己锻炼自己了.

烦劳各位老大都费一些心思,真是太感谢了.

我知道是用递归，可是打开每个下代理商的数据库要打开好多次呀，这样性能非常差的，应该先把本身的记录集存储到数组里，然后以后调用，再分别打开每个下级代理商的记录集，经过计算和第一次的记录集比较和计算

我都乱了，想不出来到底建立多少个RECORDSET，递归多少次，怎么让一个数据同时更新到两个记录集中，好多麻烦的东西，没有头绪了。

个功能是不是很好的实现呀,我感觉怎么也得用存储过程或者数组之类的解决.我现在的作法是同时打开两个数据库链接，但是这样操作的同错几率很大,最好这样来，先打开一个链接，取出所需数据，存进数组.再打开第二个链接，循环上面的数组，进行操作.如果需要更新第一个链接，在最后进行更新,原理知道了,就是写不出来.复杂的递归算法我真的弄不出来,尤其是什么FOR循环里面还弄着几个IF嵌套,我看一段就不知道数据到底是哪个状态了,请问一下这样的情况又没有什么分析上的技巧呀 .

下面是江一在线的回复。



这是一个多级的树（TREE）罢了，其实原理是类似于俺们这个论坛的结构，俺们是这样来实现的

主要数据结构
[ id ] 长整型
[ num_replied ] 双精度型
[ num_followed ] 双精度型
[ num_lasttime ] 双精度型


当一个客户是最上层的：一级客户时，应该是
num_replied=num_followed

如果是二级的客户应该是：
num_replied=新的时间码
num_followed=上一级的num_replied
也就是说呢，二级或者并非一级分类的客户应该是num_replied<>num_followed的

而新增加一个客户或者一个下级客户时
更新num_lasttime的时间码，通过这个来保证整个客户树的完整
也就是说，只要num_lasttime相同的，必定是同一个主分类的客户

这样来得出一个完整的客户树是很容易的
第一步，得到该分类的num_lasttime
第二步，根据两个时间码，整理出整个树形结构

但问题是：
假如我们要得出某一个客户的所有上级或者所有下级怎么办？

根据上面的数据结构，一个客户是可以存在并列关系的同级客户的，只要他不是一级分类
也就是说，所有num_replied相同，并且num_lasttime相同的客户都是一个级别的；但他们可能并不属于同一个上级客户，所有，上面的结构不能直接来完成你的要求，进行如下改动：

改动后的数据结构
[ id ] 长整型
[ mark ] 长整型
[ num_replied ] 双精度型
[ num_followed ] 双精度型
[ num_lasttime ] 双精度型


增加了一个MARK字段，用于表示这个客户的级数，一级客户用0表示，二级用1表示，依此类推……
那么，得出一个客户的所有下级可能这样来
1.num_lasttime相同，表示同一个一级客户
2.mark>该客户的mark
3.num_replied>该客户的num_replied

到这里，得出一个客户的所有上级你也应该知道怎么做了吧

如果你觉得太麻烦，希望像你的数据结构那样，用一个字段来表示隶属关系
我上次已经说过了，那你得学习如何科学高效的进行编码
我们可以来32位的二进制串来表示一个客户代号
比如：
0111 0010 0001 0100 0111 0001 0101 0111
前四位用来表示一级的客户
如果是一级的客户，那他的后面应该都是0
也就是类似：0001 0000 0000 0000 0000 0000 0000 0000
如果是二级的客户，第二段应该有数字，比如：
0001 0000 0010 0000 0000 0000 0000 0000
如果是再下一级的，就还有：
0001 0000 0010 0000 0100 0000 0000 0000
似次类推，可惜这种算法要用到：位与计算，而这在VBS和ACCESS中都不支持，可惜。

另附上2则经典树型算法

在网站建设中，经常需要处理商品分类、栏目分类、论坛主题等具有树型数据结构的情况。如果不对这些分类进行编码，程序的效率很低。那么，如何设计一种高效的编码算法？
这里介绍一种效率极高的分类算法。我在我们公司的许多Web应用，包括电子商务、下载站点、新闻发布系统，都应用了这样的编码算法，效果很好。
分类算法要解决的问题
在网站建设中，分类算法的应用非常的普遍。在设计一个电子商店时，要涉及到商品分类；在设计发布系统时，要涉及到栏目或者频道分类；在设计软件下载这样的程序时，要涉及到软件的分类；如此等等。可以说，分类是一个很普遍的问题。
我常常面试一些程序员，而且我几乎毫无例外地要问他们一些关于分类算法的问题。下面的举几个我常常询问的问题。你认为你可以很轻松地回答么^_^.
1、分类算法常常表现为树的表示和遍历问题。那么，请问：如果用数据库中的一个Table来表达树型分类，应该有几个字段？
2、如何快速地从这个Table恢复出一棵树；
3、如何判断某个分类是否是另一个分类的子类；
4、如何查找某个分类的所有产品；
5、如何生成分类所在的路径。
6、如何新增分类；

在不限制分类的级数和每级分类的个数时，这些问题并不是可以轻松回答的。本文试图解决这些问题。
分类的数据结构
我们知道：分类的数据结构实际上是一棵树。在《数据结构》课程中，大家可能学过Tree的算法。由于在网站建设中我们大量使用数据库，所以我们将从Tree在数据库中的存储谈起。
为简化问题，我们假设每个节点只需要保留Name这一个信息。我们需要为每个节点编号。编号的方法有很多种。在数据库中常用的就是自动编号。这在Access、SQL Server、Oracle中都是这样。假设编号字段为ID。
为了表示某个节点ID1是另外一个节点ID2的父节点，我们需要在数据库中再保留一个字段，说明这个分类是属于哪个节点的儿子。把这个字段取名为FatherID。如这里的ID2，其FatherID就是ID1。
这样，我们就得到了分类Catalog的数据表定义：

Create Table [Catalog](
[ID] [int] NOT NULL,
[Name] [nvarchar](50) NOT NULL,
[FatherID] [int] NOT NULL
);


约定：我们约定用-1作为最上面一层分类的父亲编码。编号为-1的分类。这是一个虚拟的分类。它在数据库中没有记录。
如何恢复出一棵树
上面的Catalog定义的最大优势，就在于用它可以轻松地恢复出一棵树-分类树。为了更清楚地展示算法，我们先考虑一个简单的问题：怎样显示某个分类的下一级分类。我们知道，要查询某个分类FID的下一级分类，SQL语句非常简单：
select Name from catalog where FatherID=FID
显示这些类别时，我们简单地用<LI>来做到：

<%
REM oConn---数据库连接，调用GetChildren时已经打开
REM FID-----当前分类的编号

Function GetChildren(oConn,FID)
strSQL = "select ID,Name from catalog where FatherID="&FID
set rsCatalog = oConn.Execute(strSQL)
%>
<UL>
<%
Do while not rsCatalog.Eof
%>
<LI><%=rsCatalog("Name")%>
<%
Loop
%>
</UL>
<%
rsCatalog.Close
End Function
%>


现在我们来看看如何显示FID下的所有分类。这需要用到递归算法。我们只需要在GetChildren函数中简单地对所有ID进行调用：GetChildren(oConn,Catalog("ID"))就可以了。

<%
REM oConn---数据库连接，已经打开
REM FID-----当前分类的编号

Function GetChildren(oConn,FID)
strSQL = "select Name from catalog where FatherID="&FID
set rsCatalog = oConn.Execute(strSQL)
%>
<UL>
<%
Do while not rsCatalog.Eof
%>
<LI><%=rsCatalog("Name")%>
<%=GetChildren(oConn,Catalog("ID"))%>

<%
Loop
%>
</UL>
<%
rsCatalog.Close
End Function
%>


修改后的GetChildren就可以完成显示FID分类的所有子分类的任务。要显示所有的分类，只需要如此调用就可以了：

<%
REM strConn--连接数据库的字符串，请根据情况修改
set oConn = Server.CreateObject("ADODB.Connection")
oConn.Open strConn
=GetChildren(oConn,-1)
oConn.Close
%>


如何查找某个分类的所有产品；
现在来解决我们在前面提出的第四个问题。我们假设产品的数据表如下定义：

Create Table Product(
[ID] [int] NOT NULL,
[Name] [nvchar] NOT NULL,
[FatherID] [int] NOT NULL
);


其中，ID是产品的编号，Name是产品的名称，而FatherID是产品所属的分类。
对第四个问题，很容易想到的办法是：先找到这个分类FID的所有子类，然后查询所有子类下的所有产品。实现这个算法实际上很复杂。代码大致如下：

<%
Function GetAllID(oConn,FID)
Dim strTemp

If FID=-1 then
strTemp = ""
else
strTemp =","
end if

strSQL = "select Name from catalog where FatherID="&FID
set rsCatalog = oConn.Execute(strSQL)
Do while not rsCatalog.Eof
strTemp=strTemp&rsCatalog("ID")&GetAllID(oConn,Catalog("ID")) REM 递归调用
Loop
rsCatalog.Close

GetAllID = strTemp
End Function

REM strConn--连接数据库的字符串，请根据情况修改
set oConn = Server.CreateObject("ADODB.Connection")
oConn.Open strConn

FID = Request.QueryString("FID")

strSQL = "select top 100 * from Product where FatherID in ("&GetAllID(oConn,FID)&")"
set rsProduct=oConn.Execute(strSQL)
%>
<UL><%
Do while not rsProduct.EOF
%>
<LI><%=rsProduct("Name")%>
<%
Loop
%>
</UL>
<%rsProduct.Close
oConn.Close
%>


这个算法有很多缺点。试列举几个如下：
1、由于我们需要查询FID下的所有分类，当分类非常多时，算法将非常地不经济，而且，由于要构造一个很大的strSQL，试想如果有1000个分类，这个strSQL将很大，能否执行就是一个问题。
2、我们知道，在SQL中使用In子句的效率是非常低的。这个算法不可避免地要使用In子句，效率很低。

我发现80%以上的程序员钟爱这样的算法，并在很多系统中大量地使用。细心的程序员会发现他们写出了很慢的程序，但苦于找不到原因。他们反复地检查SQL的执行效率，提高机器的档次，但效率的增加很少。
最根本的问题就出在这个算法本身。算法定了，能够再优化的机会就不多了。我们下面来介绍一种算法，效率将是上面算法的10倍以上。

分类编码算法
问题就出在前面我们采用了顺序编码，这是一种最简单的编码方法。大家知道，简单并不意味着效率。实际上，编码科学是程序员必修的课程。下面，我们通过设计一种编码算法，使分类的编号ID中同时包含了其父类的信息。一个五级分类的例子如下：

此例中，用32(4+7+7+7+7)位整数来编码，其中，第一级分类有4位，可以表达16种分类。第二级到第五级分类分别有7位，可以表达128个子分类。
显然，如果我们得到一个编码为 1092787200 的分类，我们就知道：由于其编码为
0100 0001001 0001010 0111000 0000000
所以它是第四级分类。其父类的二进制编码是0100 0001001 0001010 0000000 0000000，十进制编号为1092780032。依次我们还可以知道，其父类的父类编码是0100 0001001 0000000 0000000 0000000，其父类的父类的父类编码是0100 0000000 0000000 0000000 0000000。(我是不是太罗嗦了:，但这一点很重要。再回头看看我们前面提到的第五个问题。哈哈，这不就已经得到了分类1092787200所在的分类路径了吗？)。
现在我们在一般的情况下来讨论类别编码问题。设类别的层次为k，第i层的编码位数为Ni， 那么总的编码位数为N(N1+N2+..+Nk)。我们就得到任何一个类别的编码形式如下：
2^(N-(N1+N2+…+Ni))*j + 父类编码
其中，i表示第i层，j表示当前层的第j个分类。
这样我们就把任何分类的编码分成了两个部分，其中一部分是它的层编码，一部分是它的父类编码。
由下面公式定一的k个编码我们称为特征码：（因为i可以取k个值，所以有k个）
2^N-2^(N-(N1+N2+…+Ni))
对于任何给定的类别ID，如果我们把ID和k个特征码"相与"，得到的非0编码，就是其所有父类的编码！




接上面：

位编码算法
对任何顺序编码的Catalog表，我们可以设计一个位编码算法，将所有的类别编码规格化为位编码。在具体实现时，我们先创建一个临时表：

Create TempCatalog(
[OldID] [int] NOT NULL,
[NewID] [int] NOT NULL,
[OldFatherID] [int] NOT NULL,
[NewFatherID] [int] NOT NULL
);


在这个表中，我们保留所有原来的类别编号OldID和其父类编号OldFatherID，以及重新计算的满足位编码要求的相应编号NewID、NewFatherID。
程序如下：

<%
REM oConn---数据库连接，已经打开
REM OldFather---原来的父类编号
REM NewFather---新的父类编号
REM N---编码总位数
REM Ni--每一级的编码位数数组
REM Level--当前的级数

sub FormatAllID(oConn,OldFather,NewFather,N,Nm,Ni byref,Level)
strSQL = "select CatalogID , FatherID from Catalog where FatherID=" & OldFather
set rsCatalog=oConn.Execute( strSQL )

j = 1
do while not rsCatalog.EOF
i = 2 ^(N - Nm) * j
if Level then i= i + NewFather


OldCatalog = rsCatalog("CatalogID")
NewCatalog = i

REM 写入临时表
strSQL = "Insert into TempCatalog (OldCatalogID , NewCatalogID , OldFatherID , NewFatherID)"
strSQL = strSQL & " values(" & OldCatalog & " , " & NewCatalog & " , " & OldFather & " , " & NewFather & ")"

Conn.Execute strSQL

REM 递归调用FormatAllID
Nm = Nm + Ni(Level+1)
FormatAllID oConn,OldCatalog , NewCatalog ,N,Nm,Ni,Level + 1

rsCatalog.MoveNext

j = j+1
loop

rsCatalog.Close
end sub
%>


调用这个算法的一个例子如下：

<%
REM 定义编码参数，其中N为总位数，Ni为每一级的位数。
Dim N,Ni(5)

Ni(1) = 4

N = Ni(1)

for i=2 to 5
Ni(i) = 7
N = N + Ni(i)
next

REM 打开数据库，创建临时表
strSQL = "Create TempCatalog( [OldID] [int] NOT NULL, [NewID] [int] NOT NULL, [OldFatherID] [int] NOT NULL, [NewFatherID] [int] NOT NULL);"
Set Conn = Server.CreateObject("ADODB.Connection")
Conn.Open Application("strConn")
Conn.Execute strSQL

REM 调用规格化例程
FormatAllID Conn,-1,-1,N,Ni(1),Ni,0

REM ------------------------------------------------------------------------
REM 在此处更新所有相关表的类别编码为新的编码即可。
REM ------------------------------------------------------------------------

REM 关闭数据库
strSQL= "drop table TempCatalog;"
Conn.Execute strSQL
Conn.Close
%>


第四个问题
现在我们回头看看第四个问题：怎样得到某个分类下的所有产品。由于采用了位编码，现在问题变得很简单。我们很容易推算：某个产品属于某个类别的条件是Product.FatherID&（Catalog.ID的特征码）=Catalog.ID。其中"&"代表位与算法。这在SQL Server中是直接支持的。
举例来说：产品所属的类别为：1092787200，而当前类别为1092780032。当前类别对应的特征值为：4294950912，由于1092787200&4294950912=8537400，所以这个产品属于分类8537400。
我们前面已经给出了计算特征码的公式。特征码并不多，而且很容易计算，可以考虑在Global.asa中Application_OnStart时间触发时计算出来，存放在Application("Mark")数组中。
当然，有了特征码，我们还可以得到更加有效率的算法。我们知道，虽然我们采用了位编码，实际上还是一种顺序编码的方法。表现出第I级的分类编码肯定比第I+1级分类的编码要小。根据这个特点，我们还可以由FID得到两个特征码，其中一个是本级位特征码FID0，一个是上级位特征码FID1。而产品属于某个分类FID的充分必要条件是：
Product.FatherID>FID0 and Product.FatherID<FID1
下面的程序显示分类FID下的所有产品。由于数据表Product已经对FatherID进行索引，故查询速度极快：

<%
REM oConn---数据库连接，已经打开
REM FID---当前分类
REM FIDMark---特征值数组，典型的情况下为Application("Mark")
REM k---数组元素个数，也是分类的级数
Sub GetAllProduct(oConn,FID,FIDMark byref,k)
REM 根据FID计算出特征值FID0,FID1
for i=k to 1
if (FID and FIDMark = FID ) then exit
next

strSQL = "select Name from Product where FatherID>"FIDMark(i)&" and FatherID<"FIDMark(i-1)
set rsProduct=oConn.Execute(strSQL)%>
<UL><%
Do While Not rsProduct.Eof%>
<LI><%=rsProduct("Name")
Loop%>
</UL><%
rsProduct.Close
End Sub
%>


关于第5个问题、第6个问题，就留作习题吧。有了上面的位编码，一切都应该迎刃而解。
感谢 21DIV 开发组供稿，本文版权（电子版及文字版）都归 21DIV 所有
其它站点转载请自行联系 21DIV
请支持原创站点

这是天极论坛的树型解决方案，是坛主烈云写的。

sub MainList()显示主题帖
ON ERROR RESUME NEXT

set rs=Server.CreateObject("ADODB.Recordset")
sql="select * from "&bbs_id&" where lanp_level=1 order by lanp_subdate DESC"
rs.Open sql,conn,1,1
Set rs= conn.Execute("bbs_level1 "&bbs_id&"")

if not rs.eof then
rs.pagesize=15
rs.AbsolutePage =1
if Request("page")<>"" then rs.AbsolutePage =Request("page")
RowCount =rs.pagesize
session("pageccu")=rs.pagecount

Response.Write "<ul>"
For i= 0 To 15
If rs.eof Then exit for
Do While Not rs.Eof and RowCount>0
Response.Write "<li class=tds>"
If rs("bbs_zt")="1" Then
Response.Write "<img src=http://www.jz123.cn/Article/10/130/2005/img/jh.gif> "
Else
if rs("lanp_icon")<>"" then Response.Write "<img src=images/" &rs("lanp_icon")&".gif> "
End If
Response.Write "<a href=disp.asp?uid="&nowid&"&lanp_id="&rs("lanp_id")&"&bbsid="&Request("bbsid")&">"&Replace(rs("lanp_title")," "," ")&"</a>"
if rs("lanp_size")=0 then
Response.Write "(空)"
else
Response.Write "("&rs("lanp_size")&"字)"
end if
lanu_nickn=rs("lanu_nickn")
Response.Write "(<a href=userinfo.asp?uid=lan122545&target="&lanu_nickn&" target=_b>"&lanu_nickn&"</a> "
Response.Write "<font size=1>"&rs("lanp_date")&"" &"</font>"
Response.Write "<font color=226699> 阅读:"&rs("lanp_reads") &")</font>"
If DateDiff( "d",rs("lanp_date"),DateAdd("d",-1,Now()))<0 Then
Response.Write "<img src=http://www.jz123.cn/Article/10/130/2005/images/new.gif width=31 height=12>"
End If
Response.Write "</li>"
If rs("lanp_reply")<>"" And rs("lanp_reply")<>"0" Then

SubList rs("lanp_reply"),rs("lanp_id")
ccc=0
End If
Response.Write "<hr style=height:1pt>"
RowCount=RowCount-1
rs.MoveNext
Next
Loop
Response.Write "</ul>"
Response.Write("分页显示"&dd)
else
response.write "<p><CENTER>还没有帖子呢,没有的看喽！</CENTER></p>"
end if
rs.close
set rs=nothing
conn.close
set conn=nothing
end sub

Sub SubList(lanp_reply,lanp_id)分级显示子帖
dim lanrs
set lanrs=Server.CreateObject("ADODB.Recordset")
sql2="select * from "&bbs_id&" where lanp_id in ("&lanp_reply&")"
lanrs.Open sql2,conn,1,1
Set lanrs= conn.Execute("bbs_levelN "&bbs_id&","&lanp_reply&"")
response.write "<ul>"
Do While Not lanrs.Eof
lanp_date = lanrs("lanp_date")
lanp_size=lanrs("lanp_size")
lanp_reply1=lanrs("lanp_reply")
lanp_reads1=lanrs("lanp_reads")
ccc=ccc+1
If ccc>15 Then exit do
If ccc > 16 Then
Response.Write("<BR><a href=disp.asp?lanp_id="&lanp_id&"&bbsid="&Request("bbsid")&">更多内容>>>>>></a>")
exit do
End If
response.write "<li class=tds>"规则段落显示符
if lanrs("lanp_icon")<>"" then如果表情图标字段不为空则显示
response.write "<img src=images/" &lanrs("lanp_icon")&".gif> "
end if
response.write "<a href=disp.asp?uid="&nowid&"&lanp_id="&lanrs("lanp_id")&"&bbsid="&Request("bbsid") &">"&Replace(lanrs("lanp_title")," "," ")&"</a>"以帖子主题为链接名，指向帖子编号，显示帖子内容
if lanp_size=0 then显示帖子内容大小
response.write "<空>"
else
response.write "("&lanp_size&"字)"
end if
llanu=lanrs("lanu_nickn")
response.write "(<a href=userinfo.asp?uid=lan122545&target="&llanu&" target=_b>"&llanu&"</a> "粗体显示帖子作者
response.write "<font size=1>"&lanp_date&" "&"</font>"显示帖子发表时间
response.write "<font color=226699>阅读:"&lanp_reads1&")</font>"显示帖子点击数
If DateDiff( "d",lanp_date,DateAdd("d",-1,Now()))<0 Then 如果是在2两天之内，则标注“新”的图片
response.write "<img src=http://www.jz123.cn/Article/10/130/2005/images/new.gif width=31 height=12>"
End If
response.write "</li>"规则段落显示符结束
If lanp_reply1<>"" And lanp_reply1<>"0" Then如果该帖仍有响应（子帖号），则再次调用本子程序（sub）
SubList lanrs("lanp_reply"),lanp_id
Else
End If
lanrs.MoveNext移向下一记录
Loop

response.write "</ul>"

lanrs.close
set lanrs=Nothing

End Sub
这是开发者俱乐部提供的一个比较简单的树型实现方案

树型结构在我们应用程序中还是很常见的，比如文件目录，BBS，权限设置，部门设置等。这些数

据信息都采用层次型结构，而在我们现在的关系型数据库中很难清淅表达。那么要在程序中遇到树型

结构问题该如何处理呢？

　　最近笔者通过一个ASP权限管理的程序轻松解决了一这问题，现在将其整理出来以飨读者。

　　首先，要将层次型数据模型转化为关系型数据模型。也就是说如何在我们的ACCESS，SQL SERVER

，ORACLE等关系型数据库中设计这个数据结构。
　　拿个实例来讲吧，譬如下面一个数据：

文档管理 1
|----新建文档 2
|----文档修改 3
|----文档归档 4
| |----查看归档信息 5
| |----删除归档信息 6
| | |----删除历史文档 7
| | |----删除正式文档 8
|----系统管理 9
|----用户管理 10
人事管理 11
行政管理 12
财务管理 13

　　这是一个很典型的层次型结构数据，那么大家想一想，如何将其通过二维表的形式来表达呢？初

看上去很难，是吧。可是仔细推敲一番还是有门路可钻的。

　　可以这样，将上面所有的权限视为一个权限字段，那么这个权限字段肯定是要有一个ID值的。我

们再给这个关系型数据表再强行加一个字段——隶属ID字段，也就是表明这个权限是属于哪一级权限

之下的，即这个ID值隶属于哪一个ID值。比如：“查看归档信息”权限ID值为“5”,它是隶属于“文

档归档”权限之下的，那么它的隶属ID字段的值就应该是“4”。OK，如果这一点能理解的话，那么我

们的关系转化工作也就算基本完成了。

　　下面我们就开始设计这张关系型数据表（以Sql Server 7.0 为例）：

+-----------+-----------+-----------+-----------+----------+
　　|　字段名 | 字段含义 |　字段类型　| 字段大小 　| 字段属性　|
+-----------+-----------+-----------+-----------+----------+
| SelfID　　| 权限ID 　 | Int　　　　| 4 　　　　 | PK 　　　|
| PowerName | 权限名　　| Varchar 　| 50 　　　　| Not Null |
| PowerInfo | 权限信息　| Varchar 　| 500 　　　 | 　　　　　|
| BelongID　| 隶属ID　　| Int 　　　 | 4 　　　　 | 　　　　 |
+-----------+-----------+-----------+-----------+----------+

　　好了，结构设计好你就可以轻松输入你的测试数据了。

　　然后，我们就针对如何在网页中模仿层次结构显示这功能的ASP程序，这也是最关键的一步了。

程序清单：powerlist.asp

<%
数据库连接
set conn=Server.CreateObject("ADODB.Connection")
conn.open "driver={SQL Server};server=chaiwei;DATABASE=chaiwei;UID=sa;PWD="

打开所有父层数据
set rs=Server.CreateObject("ADODB.Recordset")
rs.Open "select * from powers where belongid is null order by powerid",conn,1,3

层次数表态变量赋初值
format_i=1

列表主程序段
do while not rs.eof

打印父层数据信息
response.write "<a href=powerlist.asp?SelfID=" & rs("powerid") & "&BelongID=" & rs("belongid") & ">" & rs("powername") & "</a>"
response.write "<br>"

子程序调用，子层数据处理
Call ListSubPower(rs("powerid"))

rs.movenext

loop

关闭父层数据集
rs.close
set rs=nothing

子层数据处理子程序
Sub ListSubPower(id)

打开隶属于上层 powerid 的所有子层数据信息
set rs_sub=Server.CreateObject("ADODB.Recordset")
rs_sub.Open "select * from powers where belongid=" & id & " order by powerid",conn,1,3

列子层数据
do while not rs_sub.eof

层次数表态变量递进累加
format_i=format_i+1

循环缩进格式控制，因为顶层与二层不需要缩进，所以从第三层开始引用此程序段
for i=format_i to 3 step -1
response.write " |"
response.write " "
next

打印子层数据信息
response.write " |----"
response.write "<a href=powerlist.asp?SelfID=" & rs_sub("powerid") & "&BelongID=" & rs_sub("belongid") &">" & rs_sub("powername") & "</a>"
response.write "<br>"

递归调用子程序本身，对子层数据进行逐渐处理
ListSubPower(rs_sub("powerid"))

rs_sub.movenext

loop

层次数表态变量递退累减
format_i=format_i-1

关闭子层数据集
rs_sub.close
set rs_sub=nothing
End Sub
%>

　　powerlist.asp程序中，我们先打开顶层数据，在循环中显示出来；然后又设计一个子程序ListSubPower，通过递归算法在循环中调用，以此来打开子层数据信息，并且在子程序内部循环中又反复调用自己，以此来逐层展开深层数据。
　　另外，在程序中还用了一个静态变量format_i来控制缩进显示格式。

　　本文就树型结构在数据设计、程序控制方面做简单尝试，目的在于抛砖引玉，希望读者通过本文得到更多启示
这是CSDN的双规干部写的关于树型的存储和维护

树型结构数据的存储采用:

Tree(ID,ParentID,Remark)

如果仅对于存储来讲,无疑是最经济!

但是利用这样的结构,来提供一些基于稍微复杂点的查询的应用表现形式

效率应该说相当低下!

如: 查询某节点的路径等!

如要高效的查询,我们可以在维护数据时下点功夫!

我们以一个树型结构论坛的实现为例:

Tree(ID,ParentID,RootID,OrderID,MaxID,Indent,Title,Content,Remark)

ID: Integer 帖子ID

ParentID: Integer 父贴ID

RootID: Integer 根帖ID

OrderID: Integer 同一个根帖中,帖子顺序ID

MaxID: Integer 用于使新贴在顶部

Indent: Integer 缩进量

Title: Varchar 帖子标题

Content: Varchar 帖子内容

Remark: Varchar 除 ID,ParentID 外的贴子线索

这样的设计只要维护好每一个字段都为查询显示提高了效率!

请看下面的维护程序:

--==========================================

alter procedure AppSP_AddNew

@ID integer

,@Title varchar(8000) =null

,@Content varchar(8000)=null

as

--declare @id int

--set @id=0

if @ID=0

begin

insert into Tree (ParentID,OrderID,Indent,Title,Content)

values (0,0,0,@Title,@Content)

--把帖子顶到上面:

update Tree

set RootID = ID

,MaxId = (select max(id) from Tree)

where RootID is null

end

else

begin

--调整同一个"根帖"中,帖子的内部顺序:

update Tree

set OrderID = OrderID + 1

where RootID = (select rootid

from tree

where ID = @id)

and OrderID > (select OrderID

from Tree

where ID = @id

)

--插入回复的帖子,同时维护 RootID,ParentID,OrderID,Indent,remark,Title,Content

insert into Tree (RootID,ParentID,OrderID,Indent,remark,Title,Content)

select RootID,@ID,OrderID+1,Indent + 1

,case when remark is null then cast(parentid as varchar)

else remark + - + cast(parentid as varchar)

end

,isnull(@Title,Re: + Title),@Content

from Tree

where id=@id

--把帖子顶到上面:

update Tree

set maxid = (select max(id)

from Tree

)

where rootid = (select rootid

from tree

where id=@id

)

end

--========================================

该程序用于

1.增加新贴:

AppSP_AddNew 0,第一个问题,地球是圆的吗?

2.回复帖子:

AppSP_AddNew 1,Re: 第一个问题,地球是圆的!

这样,只需简单查询:

select *, remark + - + cast(parentid as varchar) + - + cast(id as varchar) , space(indent) + [

from tree

order by MaxID desc,orderid

就可高效的实现帖子列表及其线索,级别等!

虽然维护时增加了一些工作量!

--相关DDL脚本:

CREATE TABLE [Tree] (

[ID] [int] IDENTITY (1, 1) NOT NULL ,

[ParentID] [int] NULL ,

[RootID] [int] NULL ,

[OrderID] [int] NULL ,

[MaxID] [int] NULL ,

[Indent] [int] NULL ,

[Title] [varchar] (50),

[Content] [varchar] (200) ,

[Remark] [varchar] (250) ,

CONSTRAINT [PK_Tree] PRIMARY KEY CLUSTERED

(

[ID]

) ON [PRIMARY]

) ON [PRIMARY]