今天偶尔找出了大学毕业的论文，又看了一下，虽然页数不多，但感觉写的还不错，确实用心了

摘要

在网站建设中，分类算法的应用非常的普遍。在设计一个论坛时，要涉及到版块的分类，帖子的树状结构显示；在设计一个电子商店时，要涉及到商品分类；在设计发布系统时，要涉及到栏目或者频道分类；在设计软件下载这样的程序时，要涉及到软件的分类；如此等等。

由于这样的结构存在无限子类、无限级别、信息多变的特点。无法由一开始就设计好一种结构，而往往这种结构是随时都可能改变的。这样，就需要有一种可以根据一批信息自动构造一棵结构树的算法。

当今绝大多数信息是以数据库的形式保存起来的，本文中就以数据库为操作源，介绍一种根据数据库表中记录自动构造一棵结构树的一种分类算法。

 

 

 

关键字
分类算法 目录树 C# 数据库 无限级别

 

 

第一章    引言    1

1.    引言    1

2.    分类算法概述    1

第二章    传统分类算法的实现    1

1.    数据库设计    1

2.    恢复目录树    2

3.    如何判断某个分类是否是另一个分类的子类    3

4.    如何查找某个分类的所有产品    4

5.    如何生成分类所在的路径    5

6.    如何新增分类    5

7.    如何删除分类    6

第三章    算法改进及实现    7

1.    数据库设计    7

2.    恢复目录树    7

3.    如何判断某个分类是否是另一个分类的子类    8

4.    如何查找某个分类的所有产品    9

5.    如何生成分类所在的路径。    10

6.    如何新增分类    10

7.    如何删除分类    13

第四章    算法性能分析    13

结论    14

致谢    15

参考文献    16

 

 

  1.  

  2. 引言

  1. 引言

在网站建设中，分类算法的应用非常的普遍。在设计一个论坛时，要涉及到版块的分类，帖子的树状结构显示；在设计一个电子商店时，要涉及到商品分类；在设计发布系统时，要涉及到栏目或者频道分类；在设计软件下载这样的程序时，要涉及到软件的分类；如此等等。

由于这样的结构存在无限子类、无限级别、信息多变的特点。无法由一开始就设计好一种结构，而往往这种结构是随时都可能改变的。这样，就需要有一种可以根据一批信息自动构造一棵结构树的算法。

当今绝大多数信息是以数据库的形式保存起来的，下面我们就以数据库为操作源，介绍一种根据数据库表中记录自动构造一棵结构树的一种高效算法。

 

  1. 分类算法概述

分类算法常常表现为树的表示和遍历问题。归结到底主要也就是以下6个问题。

1、如何快速地从数据库恢复出一棵树；

2、如何判断某个分类是否是另一个分类的子类；

3、如何查找某个分类的所有产品；

4、如何生成分类所在的路径。

5、如何新增分类

6、如何删除分类

 

80%以上的程序员钟爱传统分类算法，即通过递归调用恢复目录树结构，并在很多系统中大量地使用。分类大量增多的情况下，用户很快会发现程序运行速度很慢，程序员却苦于找不到原因。他们反复地检查SQL的执行效率，提高机器的档次，但效率的增加很少。
最根本的问题就出在这个算法本身。算法定了，能够再优化的机会就不多了

 

此文，将对比传统算法的实现方式，从程序实现和运行效率等方面说明优化算法的优势。

 

  1. 传统分类算法的实现

  1. 数据库设计

无论哪种分类算法，都需要有存储方式，在这里我选择的是数据库的存储方式。

数据库表的结构设计关系到构造树的难易程序与速度，所以数据库表结构一定要设计合理，巧妙！在传统算法中，数据库表结构关系到构造树的有三个字段，

为简化问题，我们假设每个节点只需要保留TypeTitle这一个信息。我们需要为每个节点编号。编号的方法有很多种。在数据库中常用的就是自动编号。这在Access、SQL Server、Oracle中都是这样。假设编号字段为ID。

 

为了表示某个节点ID1是另外一个节点ID2的父节点，我们需要在数据库中再保留一个字段，说明这个分类是属于哪个节点的儿子。把这个字段取名为ParentID。如这里的ID2，其ParentID就是ID1。

 

这样，我们就得到了分类TypeList的数据表定义：

 

CREATE TABLE TypeList (

[TypeID] [int] IDENTITY(1, 1)NOT NULL, /* 类别内部编号 */

[ParentID] [int] NOT NULL, /* 父级类别编号 */

[TypeTitle] [varchar] (80) NOT NULL /* 类别名称/标题 */

)

上面的TypeList定义的最大优势，就在于用它可以轻松地恢复出一棵树—分类树。

  1. 恢复目录树

为了更清楚地展示算法，我们先考虑一个简单的问题：怎样显示某个分类的下一级分类。我们知道，要查询某个分类FID的下一级分类，SQL语句非常简单：

SELECT * FROM TypeList WHERE ParentID = FID

 

程序实现显示这些类别时，我们可以通过下面的程序来做到：（部分函数为实现效果所用，特此省略，实际程序请看源码）

    /// <summary>

    /// 显示树的单层节点

    /// </summary>

    /// <param name="iTypeId">分类ID</param>

    private void WriteTree(System.Int64 iTypeId)

    {

         string cSql="SELECT * FROM TypeList Where ParentID ="+iTypeId+" Order By [TypeID]";

DataView dv = SqlHelper.ExecuteDataView(cSql);

m_sbmenu.Append("<UL>");

        for (int i=0;i<dv.Count;i++)

        {

         //生成子节点

        m_sbmenu.Append("<li>");

        m_sbmenu.Append(dv[i]["TypeTitle"].ToString());

        m_sbmenu.Append("</li>");

        }

m_sbmenu.Append("</UL>");

dv.Dispose();

}

如果要显示FID下的所有分类。这就需要用到递归算法。我们只需要对所有ID进行调用：WriteChildren(iTypeId)就可以了。

 

下面是使用C#实现的递归函数

        /// <summary>

        /// 递归遍历整个树

        /// </summary>

        /// <param name="iTypeId">分类ID</param>

        private void WriteChildren(System.Int64 iTypeId)

        {

            string cSql="SELECT * FROM TypeList Where ParentID ="+iTypeId+" Order By [TypeID]";             DataView dv = SqlHelper.ExecuteDataView(cSql);

            m_sbmenu.Append("<UL>");

            for (int i=0;i<dv.Count;i++)

            {

                m_sbmenu.Append("<li>");

                m_sbmenu.Append(dv[i]["TypeTitle"].ToString());

     //递归调用

                WriteChildren(System.Convert.ToInt64(dv[i]["TypeID"]));

                m_sbmenu.Append("</li>");

            }

            m_sbmenu.Append("</UL>");

dv. Dispose();

}

 

这是通常使用的方法，如果分类个数，层数比较多，每次递归都会进行数据库操作，效率是很低的。安共100个分类，需操作数据库100次

 

  1. 如何判断某个分类是否是另一个分类的子类

由于分类层数不定，SQL不能实现递归算法。所以必须使用前台程序进行递归处理。

这两种操作基本要求都是根据parentid反向向上追溯到根目录。这种常用操作，却需要多次连接数据库，效率很低。见程序

 

        /// <summary>

        /// 判断某个分类是否是另一个分类的子类

        /// </summary>

        /// <param name="iChildrenTypeId">子分类</param>

        /// <param name="iParentTypeId">目标分类</param>

        /// <returns>是否存在子树关系</returns>

    private bool CheckChildrenType(System.Int64 iChildrenTypeId,System.Int64 iParentTypeId)

        {

            string cSql="SELECT ParentID FROM TypeList Where TypeID ="+iChildrenTypeId;

            DataView dv = SqlHelper.ExecuteDataView(cSql);

            System.Int64 iTempId;

            if (dv.Count>0)

            {

                iTempId=System.Convert.ToInt64(dv[0][0].ToString());

                //约定，如果到根目录则返回

                if(iTempId==-1) return false;

                if(iTempId==iParentTypeId)

                {

                    return true;

                }

                else

                {

                    //递归向上

                    CheckChildrenType(iTempId,iParentTypeId);

                }

            }

            return false;

 

        }

  1. 如何查找某个分类的所有产品

这也是非常常用的功能之一，分两种需求，一种是只列出当前分类下的产品，这个根据产品表，很容易实现

CREATE TABLE Commodity (

CommID [int] IDENTITY(1, 1) NOT NULL, /* 商品内部编号(自动加一) */

CommTitle [varchar] (80) NULL, /* 商品名称/标题 */

TypeID [int] NOT NULL /* 商品类别:外键 */

)

 

SELECT CommTitle From Commodity WHERE TypeID=123

 

 

 

另一种是所有子分类的产品，这个比较复杂，首先要递归获取所有子类的TYPEID。然后根据这个结果集获取所有属于这个分类的产品。

 

 

 

  1. 如何生成分类所在的路径

这里操作可以有两种方式，由于它是由下至上，所以使用循环递归都可以实现，但是查询复杂度不能减小。

 

        /// <summary>

        /// 获取指定分类的路径

        /// </summary>

        /// <param name="iTypeId">分类ID</param>

        /// <returns>完整路径</returns>

        private string GetPath(System.Int64 iTypeId)

        {

            string cSql="SELECT ParentID,TypeTitle FROM TypeList Where TypeID ="+iTypeId;

            DataView dv = SqlHelper.ExecuteDataView(cSql);

            System.Int64 iTempId;

            if (dv.Count>0)

            {

                iTempId=System.Convert.ToInt64(dv[0]["ParentID"].ToString());

                //约定，如果到根目录则返回

                if(iTempId==-1)

                {

                    return dv[0]["TypeTitle"].ToString();

                }

                else

                {

                    //递归向上

                    return GetPath(iTempId)+"-"+dv[0]["TypeTitle"].ToString();

                }

            }

            return "";

        }

 

  1. 如何新增分类

数据库设计的简单，带来了新增修改删除的简单，只需简单的一条Sql语句就可以实现相应功能。

INSERT INTO TypeList (ParentID, TypeTitle) VALUES (1,'名称')

 

  1. 如何删除分类

这里的删除，按照数据结构里对树的操作应该存在两种情况，一是删除叶子节点，也就是没有子分类的节点，另一种是删除分支节点。第一种相对简单，语句如下

DELETE FROM TypeList WHERE TypeId= 1

 

第二种情况，为了保证树的完整性，需要将待删节点B的子节点C，D的父节点设为B的父节点A

 101309_1407_1

程序实现需要通过中间变量实现，通过存储过程实现

DECLARE @iParentTypeId int, @iTypeId int SELECT @iParentTypeId=ParentID FROM TypeList WHERE TypeId=@iTypeId

UPDATE TypeList SET ParentID=@iParentTypeId WHERE ParentID=@iTypeId

DELETE TypeList WHERE TypeId=@iTypeId

 

 

  1. 算法改进及实现

上面递归算法的大量应用，这样做势必要进行大量的Sql查询(虽然可以使用存储过程来做，但要从根本上加快速度，则应该考虑更快的算法)。下面给出一个可行的彻底屏弃递归的实现树状结构的算法。

相对于以上六种常用操作，我改进了算法，为了不使改进后的算法反而减弱了实现效率，尝试新的改进也应该实现以下几种情况

  • 在几个常用操作中，应该减少库操作。
  • 实现的简单性

 

  1. 数据库设计

 

原算法中，恢复树操作，由于不知道各个分类之间的先后顺序关系以及层次关系，必须使用递归方式，遍历树才可以实现。我的算法假设如果将这两个字段通过某种方式实现并存入数据库，那么这个操作，将非常简单。按照这个思路，将TypeList表增加lever和order字段，Lever表示类别所在层，根目录表示第一层。ORDER表示排序字段，此顺序为要恢复显示的目录树的自然排序数

如下图。

 

CREATE TABLE TypeList (

[TypeID] [int] IDENTITY(1, 1)NOT NULL,/* 类别内部编号 */

[ParentID] [int] NOT NULL,/* 父级类别编号 */

[TypeTitle] [varchar] (80) NOT NULL,/* 类别名称/标题 */

[Level] [int] NOT NULL,/* 类别 等级 */

[Order] [int] NOT NULL,/* 排序 */

)

 

 

 

 

 

 

 

 

 

  1. 恢复目录树

 

通过对表的改造。对树的恢复，只要一条SQL即可，我们的程序改造如下

        /// <summary>

        /// 恢复树

        /// </summary>

        private void WriteTree()

        {

            string cSql="SELECT TypeID, [Level], TypeTitle FROM TypeList ORDER BY [Order] ";

            DataView dv = SqlHelper.ExecuteDataView(cSql);

            int iCurrLevel=0;

            for (int i=0;i<dv.Count;i++)

            {

                if ((int)dv[i]["Level"]>iCurrLevel)

                {//显示下一级

                    m_sbmenu.Append("<ul>");

                    m_sbmenu.Append("<li>");

                    m_sbmenu.Append(dv[i]["TypeTitle"]);

                    m_sbmenu.Append("</li>");

                    iCurrLevel=(int)dv[i]["Level"];

                }

                else if ((int)dv[i]["Level"]<iCurrLevel)

                {//显示上一级

                    m_sbmenu.Append("</ul>");

                    m_sbmenu.Append("<li>");

                    m_sbmenu.Append(dv[i]["TypeTitle"]);

                    m_sbmenu.Append("</li>");

                    iCurrLevel=(int)dv[i]["Level"];

                }

                else

                {

                    m_sbmenu.Append("<li>");

                    m_sbmenu.Append(dv[i]["TypeTitle"]);

                    m_sbmenu.Append("</li>");

                }

            }

            for (int j=iCurrLevel;j>0;j--)

            {

                m_sbmenu.Append("</ul>");

            }

            dv.Dispose();

        }

 

  1. 如何判断某个分类是否是另一个分类的子类

为解决这个问题，我是这样考虑的，如果某个分类在另一个分类的树路径上，那么就可以直接判断出结果，此节点到根节点的路径（也就是第4个问题）我们可以通过某种方法获得后，记录在此节点属性上，这样就可以完成我们的设想。由此我们对数据库改造如下

增加ParentStr字段记录此节点的路径

CREATE TABLE TypeList (

[TypeID] [int] IDENTITY(1, 1)NOT NULL,/* 类别内部编号 */

[ParentID] [int] NOT NULL, /* 父级类别编号 */

[TypeTitle] [varchar] (80) NOT NULL, /* 类别名称/标题 */

[Level] [int] NOT NULL, /* 类别 等级 */

[Order] [int] NOT NULL, /* 排序 */

[ParentStr] [varchar](1000) NOT NULL /* 父级类别，多个用逗号隔开 */

)

经过此番改造后，这个问题就变得非常简单了，我们仅进行了一次数据库操作，然后用字符串的indexof函数判断即可获得结果。

/// <summary>

/// 判断某个分类是否是另一个分类的子类

/// </summary>

/// <param name="iChildrenTypeId">子分类</param>

/// <param name="iParentTypeId">目标分类</param>

/// <returns>是否存在子树关系</returns>

private bool CheckChildrenType(System.Int64 iChildrenTypeId,System.Int64 iParentTypeId)

{

    string cSql="SELECT ParentStr FROM TypeList Where TypeID ="+iChildrenTypeId;

    DataView dv = SqlHelper.ExecuteDataView(cSql);

    if (dv.Count>0)

    {

    if(dv[0][0].ToString().IndexOf(iParentTypeId.ToString())>-1)

    {

        return true;

    }

    else

    {

        return false;                

    }

    }

    dv.Dispose();

    return false;

}   

 

  1. 如何查找某个分类的所有产品

同样是先获取一个TYPEID结果集，但获取方式是不同的，只要获取parentstr中存在指定类型，并且lever小于指定类型的即可

  1. 如何生成分类所在的路径。

增加的ParentStr字段即可直接获取路径信息。，

  1. 如何新增分类

新增操作一般是在系统正常使用前，进行的维护性工作，相对于以上几种频繁使用的操作，

使用率明显要少，我们可以把对parentstr,order,level几个字段的维护放到这里来操作。

我先通过简单的示意图来演示进行的树操作（为了叙述的简洁，在此只讨论与树状结构有关的字段。）

源数据

TypeID Level Order ParentStr

11 1 1

22 2 1,2

______________________________

32 21,3

1增加子类，直接设置排序为2，原来的2以后的一律加1

 

排序后结果为：

TypeID Level Order ParentStr

11 1 1

32 2 1,3

22 3 1,2

______________________________

43 3 1,3,4

3增加子类，取3的排序加1为3，其他都加1

 

排序后结果为:

TypeID Level Order ParentStr

11 1 1

32 2 1,3

43 3 1,3,4

22 4 1,2

______________________________

54 4 1,3,4,5

4增加子类，取4的排序加1为4，其他都加1

 

排序后的结果为：

TypeID Level Order ParentStr

11 1 1

32 2 1,3

43 3 1,3,4

54 4 1,3,4,5

22 5 1,2

______________________________

63 3 1,3,6

3增加子类，取3的排序加1为3，其他都加1

 

排序后的结果为：

TypeID Level Order ParentStr

11 1 1

32 2 1,3

63 3 1,3,6

43 4 1,3,4

54 5 1,3,4,5

22 6 1,2

 

 

这样排序联合基数order与层数level一起就实现了如下的树状结构：

TypeId

1

3

 6

 4

 5

2

 

总结一下思路，在分类A下添加分类B，那么B.Level=A.Level+1, B.ParentStr=A.ParentStr+B.TypeId, B.Order=A.Order+1,同时所有大于A.Order的Order+1

 

具体程序如下

IF EXISTS (select * from dbo.sysobjects where id = object_id(N'[dbo].[Type_Add]') and OBJECTPROPERTY(id, N'IsProcedure') = 1)

DROP procedure [dbo].[Type_Add]

GO

 

CREATE PROCEDURE Type_Add

    @iParentId int, --父级id

    @cTypeTitle varchar(80), --分类名

    @cMessage varchar(100) OUTPUT --返回信息

AS

 

DECLARE @iLevel int,@cParentStr varchar(1000)

DECLARE @iReturn int,@iOrder int,@iType int

 

 

SET @iReturn = 1

SET @cMessage = '添加分类成功'

 

BEGIN TRANSACTION

--1判断是否存在父级ID

    IF NOT EXISTS(SELECT * FROM [TypeList] WHERE [TypeID]=@iParentId)

    BEGIN

     SET @cMessage = '该父级ID不存在！'

     GOTO ERROR_RETURN

    END

    --2获得父级的Order，Level，ParentStr

    SELECT @iLevel=Level+1,@cParentStr=ParentStr,@iOrder=[order] FROM [TypeList] WHERE [TypeID]=@iParentId

    

    --3更新其他排序

UPDATE [TypeList] SET [Order]=[Order]+1 WHERE [Order]>@iOrder

    IF @@Error != 0 GOTO ERROR_HANDLER --捕获错误

 

    --4.插入新类

    INSERT INTO TypeList

     (ParentID,ParentStr, [Level], [Order], TypeTitle)

    VALUES (@iParentId,@cParentStr,@iLevel,@iOrder+1,@cTypeTitle)

    IF @@Error != 0 GOTO ERROR_HANDLER --捕获错误

 

--5 更新新增类型的ParentStr

UPDATE [TypeList] SET ParentStr=ParentStr+','+convert(varchar,TypeID) WHERE [TypeID]=@@IDENTITY

    IF @@Error != 0 GOTO ERROR_HANDLER --捕获错误

 

 

COMMIT TRANSACTION

RETURN @iReturn

 

ERROR_HANDLER:

ROLLBACK TRANSACTION

SET @cMessage = '执行[Type_Add]存储过程中出现异常错误，事务已回滚！'

return 0

ERROR_RETURN:

ROLLBACK TRANSACTION

return 0

 

GO

 

  1. 如何删除分类

这里的删除子分类，也有了明显的效率提升，只要删除路径中含有指定分类的记录即可，程序如下

delete [TypeList] WHERE ParentStr LIKE '%'++convert(varchar,@TypeId)+'%'

 

  1. 算法性能分析

本文共涉及到6种基本操作，现对这6种操作在新旧算法中的效率，程序复杂度作个比较。数据库操作通过SQL的事件探查器进行分析。

设数据库有N个分类

 

旧算法

新算法

SQL操作T

程序复杂

SQL操作

程序复杂

从数据库恢复树；

N+1 

递归操作

1 

单SELECT

判断某个分类是否是另一个分类的子类

1<T< N

递归或循环

1 

单语句比较EXISTS

查找某个分类的所有产品

1< T <N+1 

递归
SQL IN操作

1 

SQL IN操作

生成分类所在的路径。

1<T< N 

递归或循环

2 

查询，更新

新增分类

1 

添加

5 

树维护

何删除分类

1(删除叶子节点)<T< N（删除根目录）

递归删除

1

单DELETE

 

结论

由于分类算法是软件开发过程中必不可少的实际应用，它的应用和研究遍及计算机软件和硬件的各个领域，近年来越来越多的程序员开始重视此类算法的优化，用此文描述的优化的分类算法，配合数据库存储过程的应用，能够提高软件的开发效率。当功能需求变化时，无须重新创建工程，只须在原有的数据库设计基础上作一些增加、删除或修改即可，这样就可以减少不必要的工作量。

本次设计还有一些不足之处，比方说一些树的不常用操作，例如判断分类有无子类，同代之间的排序等等。这些操作在此算法基础上都可以经过改造加以实现。总的思路就是将频繁使用的操作，通过对结构及算法的改进，对资源占用降到最低。适当对创建目录树的操作增加工作量，以达到高效的目的。