介绍一种效率极高的分类算法
需积分: 10 182 浏览量
2008-05-05
21:09:26
上传
评论 1
收藏 47KB DOC 举报
介绍一种效率极高的分类算法
我常常面试一些程序员，而且我几乎毫无例外地要问他们一些关于分类算法的问题。下面
的举几个我常常询问的问题。你认为你可以很轻松地回答么
分类算法常常表现为树的表示和遍历问题。那么，请问：如果用数据库中的一个
来表达树型分类，应该有几个字段？
如何快速地从这个 恢复出一棵树；
如何判断某个分类是否是另一个分类的子类；
如何查找某个分类的所有产品；
如何生成分类所在的路径。
如何新增分类；
在不限制分类的级数和每级分类的个数时，这些问题并不是可以轻松回答的。本文试
图解决这些问题。
分类的数据结构
我们知道：分类的数据结构实际上是一棵树。在《数据结构》课程中，大家可能学过
的算法。由于在网站建设中我们大量使用数据库，所以我们将从 在数据库中的存储
谈起。
为简化问题，我们假设每个节点只需要保留 这一个信息。我们需要为每个节点编号。
编号的方法有很多种。在数据库中常用的就是自动编号。这在 、
、 中都是这样。假设编号字段为 。
为了表示某个节点 是另外一个节点 的父节点，我们需要在数据库中再保留一个字
段，说明这个分类是属于哪个节点的儿子。把这个字段取名为 。如这里的 ，
其 就是 。
这样，我们就得到了分类 !" 的数据表定义：
# !"$%
&&&&#$#'($&&)*
&&&&#$#($%+,)*
&&&&#$&&#'($)
,-
约定：我们约定用. 作为最上面一层分类的父亲编码。编号为. 的分类。这是一个虚拟的
分类。它在数据库中没有记录。
评论0