在网站建设中，分类算法的应用非常的普遍。在设计一个电子商店时，要涉及到商品分类；在设计发布系统时，要涉 及到栏目或者频道分类；在设计软件下载这样的程序时，要涉及到软件的分类；如此等等。可以说，分类是一个很普遍的 问题。 我常常面试一些程序员，而且我几乎毫无例外地要问他们一些关于分类算法的问题。下面的举几个我常常询问的问 题。你认为你可以很轻松地回答么^_^. 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 %>
位编码算法 对任何顺序编码的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 定义编码参数，其中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 %>
