-
在网站建设中，分类算法的应用非常普遍，在设计电子商店时，涉及到商品的分类。在设计和发布系统时，它涉及到列或通道的分类。在设计下载这样一个程序的软件时，涉及到软件的分类等问题，可以说分类是一个常见的问题。
我经常采访一些程序员，我几乎毫不例外地问他们关于分类算法的一些问题，这里有几个问题我经常问，你认为你能回答^ _ ^。容易地
1。分类算法通常被表示为树表示和遍历问题，那么，请问：如果您使用数据库中的一个表来表示树的分类，应该有多少字段
2，如何快速从表中恢复树；
三.如何判断某一范畴是另一类的子类；
4。如何找到某一品类的所有产品；
5，如何生成分类路径。
6。如何添加新的分类；
这些问题在不限制分类级数和每类数的情况下不易回答，本文试图解决这些问题。
分类的数据结构
我们知道分类的数据结构实际上是一棵树，在数据结构课程中，你可能已经学习了树的算法，因为我们在网站建设中使用了大量的数据库，我们将讨论数据库中树的存储。
为了简化问题，我们假设每个节点只需要保留名称的信息。我们需要为每个节点编号。有许多方法可以编号。数据库中常用的是自动编号。这是访问、SQL Server和Oracle中的情况。假设数字字段是ID.。
为了表明一个节点是另一个父节点的Id1，Id2，我们需要在数据库中显示哪些节点是这个分类的儿子住另一个领域。这个领域的FatherID。在这里的不同，其fatherid是1。
这样，我们得到了分类目录的数据表定义：
创建表{目录}（
{ }不为null，
{姓名} { nvarchar }（50）不为空，
{ } { }不空fatherid int
）；
会议：我们同意用1作为顶层父代码。分类编号-1.this是一个虚拟的分类。它是没有记录在数据库中。
如何恢复树
上述目录定义的最大好处在于利用它能够很容易地恢复树-树。为了显示算法更清晰，我们首先考虑一个简单的问题：如何显示某一类一类分类。我们知道，查询分类FID下分类的SQL语句是很简单的：
选择名字的目录，fatherid = FID
当显示这些类别时，我们只做它：
REM oconn ---已经打开的数据库连接，当调用getChildren
当前REM分类的数量
函数方法（oconn，FID）
如何为选择ID，名字从目录里fatherid =FID
集rscatalog = oconn执行（如何）。
%>
而不是rscatalog EOF。
%>
环
%>
rscatalog。关闭
端功能
%>
现在让我们看看如何显示在FID所有分类。这需要一个递归算法。我们只需要在方法调用的所有函数简单的ID：getChildren（oconn，目录（ID））是好的。
REM oconn ---数据库连接已经打开了
当前REM分类的数量
函数方法（oconn，FID）
如何为选择名称目录，fatherid =FID
集rscatalog = oconn执行（如何）。
%>
而不是rscatalog EOF。
%>
环
%>
rscatalog。关闭
端功能
%>
改进的方法可以完整显示所有子类别的FID分类任务。显示所有分类，这是调用它的唯一方法。
REM strconn --连接数据库的字符串，请改变它根据情况
集oconn = server.createobject（数据连接）
OConn打开strconn。
= getChildren（oconn，- 1）
接近OConn。
%>
如何找到某一品类的所有产品；
现在来解决我们提出的第四个问题，剩下第三个问题作为练习，我们假设产品的数据表定义如下：
创建表产品（
{ }不为null，
{姓名} { nvchar }不空，
{ } { }不空fatherid int
）；
其中，ID是产品编号，名称是产品的名字，而FatherID是产品的分类。
最容易想到的第四个问题是先找出分类的所有子类，然后查询所有子类下的所有产品，这个算法的实现非常复杂：
功能getallid（oconn，FID）
昏暗的strtemp
如果FID = 1，那么
strtemp =
其他的
strtemp =
最后如果
如何为选择名称目录，fatherid =FID
集rscatalog = oconn执行（如何）。
而不是rscatalog EOF。
strtemp = strtemprscatalog（ID）getallid（oconn，目录（ID））REM递归调用
环
rscatalog。关闭
getallid = strtemp
端功能
REM strconn --连接数据库的字符串，请改变它根据情况
集oconn = server.createobject（数据连接）
OConn打开strconn。
FID = request.querystring（FID）
如何为选择前100的产品，fatherid在（getallid（oconn，FID））
集rsproduct = oconn.execute（如何）
%>
而不是rsproduct.eof
%>
环
%>
接近OConn。
%>
该算法有很多不足之处：
1，因为我们需要查询所有FID的分类，在分类算法非常大，很不经济，但是，由于大量的建设如何，如果有1000个分类，该如何将是很大的，是否执行的问题。
2。我们知道在sql中使用子句的效率很低，这种算法不可避免地使用子句，效率很低。
我发现有超过80%的程序员喜欢这种算法，并在很多系统中使用它们，细心的程序员会发现他们编写了非常慢的程序，但是他们找不到原因，他们反复检查SQL的效率和提高机器的质量，但效率却没有提高。
最根本的问题是算法本身，算法是固定的，重新优化的机会不多。我们来介绍一个比上面的算法效率高10倍的算法。
分类编码算法
问题是在序列编码的前面，这是编码的最简单的方法。你知道，简单并不意味着效率。事实上，编码科学是程序员的必修课。下面，我们设计了一种编码算法进行分类编号ID包含其父亲的信息，五分类举例如下：
在这种情况下，以32（4 + 7 + 7 + 7 + 7）的整数编码，其中，4的第一级分类，可以表达16种分类，有7种等级二到第五、128小类可以表示。
显然，如果我们得到一个代码1092787200的类别，我们知道因为它的代码，
010000010010001010 01110000000000
所以这是一个第四级的父类的二进制代码是010000010010001010和00000000000000的十进制数是1092780032，反过来，我们也可以知道父类的父类是010000010010000000，00000000000000，和父类的父类的父类是010000000000000000 00000000000000。（我不是太冗长，但这是非常重要的。回首第五个问题我们前面提到的。哈哈，这是分类1092787200分类路径）。
现在我们讨论了一般情况下的类编码问题，类的级别是k，i层的编码数字是NI，编码数字的总数是n（N1 + n2 + + + NK）：
2（n -（n2 + +）+ ni））* +父类编码
在此，我表示i层，j代表当前层的j分类。
这样，我们将任何分类的编码分为两个部分，一个是它的层编码，另一个是它的父代码。
下面公式所设定的K码称为特征码：（因为我可以取K值，所以有k）
2 ^ N-2 ^（N（N1 + N2 +…）+ Ni））
对于任何给定的类id，如果我们将id与K特性代码相结合，则非0编码就是其父类的所有编码！
位编码算法
对于任何序列编码目录表，我们可以设计一种比特编码算法，将所有类别编码标准化为位编码，在具体实现时，首先创建一个临时表：
创建TempCatalog（
{ } { }不空oldid int，
{ } { }不空NEWID int，
{ } { }不空oldfatherid int，
{ } { }不空newfatherid int
）；
在这张表中，我们把所有的原始类别数oldid及其母数oldfatherid，并重新计算相应数量的newfatherid NEWID和满足要求的点编码。
下列程序如下：
REM oconn ---数据库连接已经打开了
REM oldfather ---原父类数
REM newfather ---新的父类数
数字编码的总数
在每一级的雷姆上编码的数字数组——
当前的REM级系列——
子formatallid（oconn，oldfather，newfather、N、Nm、Ni byref、水平）
如何为选择catalogid，FatherID从目录里fatherid =oldfather
集rscatalog = oconn.execute（如何）
J = 1
而不是rscatalog.eof
i＝2（n - Nm）* j
如果水平然后我=我+ newfather
oldcatalog = rscatalog（catalogid ）
newcatalog =我
临时表写入
如何=插入tempcatalog（oldcatalogid，newcatalogid，oldfatherid，newfatherid）
如何=如何值（oldcatalog
康涅狄格州执行如何
REM递归地调用formatallid
nm＋ni＋ni（能级＋1）
formatallid oconn，oldcatalog，newcatalog，N，Nm，Ni，等级+ 1
rscatalog.movenext
j = j + 1
环
rscatalog。关闭
端子
%>
调用此算法的一个例子如下：
REM定义了编码参数，其中n是总的数字，而NI是每个级别上的位数。
暗N，ni（5）
倪（1）＝4
N＝ni（1）
对于我= 2比5
倪（一）＝7
n＝ni（ni）
下一个
REM打开数据库并创建一个临时表。
如何为创造tempcatalog oldid } { }（{ int不空，{ } { }不是int NEWID空
设置conn = server.createobject（数据连接）
康涅狄格州开放应用（strconn ）
康涅狄格州执行如何
呼叫规范化例程
formatallid Conn、- 1、- 1、N，Ni（1），倪，0
REM ------------------------------------------------------------------------
REM是在这里为新编码的所有相关表更新类代码。
REM ------------------------------------------------------------------------
关闭数据库
如何为表tempcatalog；
康涅狄格州执行如何
康涅狄格州接近
%>
第四个问题
现在让我们来看看第四个问题：如何让所有的产品一定的类别下。因为比特编码的使用，现在的问题是很简单的，很容易计算出一个产品属于某一类product.fatherid（目录ID的特征码）=比特和算法catalog.id.the表示。这是直接在SQL服务器支持。
例如，产品的种类：1092787200、与当前类是1092780032，当前类别的特征值对应的：4294950912、由于10927872004294950912 = 8537400，所以该产品属于分类8537400。
我们已经给出了特征码的计算公式，特征码不多，计算简单。它可以计算出在Global.asa当application_onstart时间触发，它是存储在应用程序（标记）阵列。
当然，随着特征码，我们也可以得到更有效的算法。我们知道，虽然我们使用比特编码，它实际上是一个连续的编码方法。结果表明，I类分类代码肯定是小于代码为我+ 1类。根据这个特点，我们也可以从FID两特征码，其中一个是当地的一些特征码fid0，一是优越的点特征码fid1，产品属于一个分类的FID的充要条件是：
产品。fatherid > fid0和product.fatherid
下面的程序显示所有产品分类FID下。由于数据表产品已编入索引的fatherid，查询速度非常快：
REM oconn ---数据库连接已经打开了
快速眼动分类法
REM fidmark ---特征值的数组，通常在应用案例（标志）
REM -数组的元素数目和分类系列
Sub GetAllProduct（oconn，FID，fidmark ByRef，K）
REM计算特征值fid0，fid1基于FID
我要K到1
如果（FID和fidmark = FID）然后退出
下一个
如何为选择名称从产品fatherid >fidmark（我）和FatherID
集rsproduct = oconn.execute（如何）%>
而不是rsproduct。EOF %>
环%>
rsproduct。关闭
端子
%>
至于第五和第六个问题，把它作为练习。