解析PHP无限级分类方法及代码

无论你要构建自己的论坛，在你的网站上发布消息还是书写自己的CMS程序，你都会遇到要在数据库中存储层次数据的情况。同时，除非你使用一种像XML的数据库，否则关系数据库中的表都不是层次结构的，他们只是一个平坦的列表。所以你必须找到一种把层次数据库转化的方法。

存储树形结构是一个很常见的问题，他有好几种解决方案。主要有两种方法：邻接列表模型和改进前序遍历树算法

在本文中，我们将探讨这两种保存层次数据的方法。我将举一个在线食品店树形图的例子。这个食品店通过类别、颜色和品种来组织食品。树形图如下：

本文包含了一些代码的例子来演示如何保存和获取数据。我选择PHP来写例子，因为我常用这个语言，而且很多人也都使用或者知道这个语言。你可以很方便地把它们翻译成你自己用的语言。

邻接列表模型(The Adjacency List Model)
我们要尝试的第一个——也是最优美的——方法称为“邻接列表模型”或称为“递归方法”。它是一个很优雅的方法因为你只需要一个简单的方法来在你的树中进行迭代。在我们的食品店中，邻接列表的表格如下：

如你所见，对每个节点保存一个“父”节点。我们可以看到“Pear”是“Green”的一个子节点，而后者又是“Fruit”的子节点，如此类推。 根节点，“Food”，则他的父节点没有值。为了简单，我只用了“title”值来标识每个节点。当然，在实际的数据库中，你要使用数字的ID。

显示树
现在我们已经把树放入数据库中了，得写一个显示函数了。这个函数将从根节点开始——没有父节点的节点——同时要显示这个节点所有的子节点。对于这些子节点，函数也要获取并显示这个子节点的子节点。然后，对于他们的子节点，函数还要再显示所有的子节点，然后依次类推。

也许你已经注意到了，这种函数的描述，有一种普遍的模式。我们可以简单地只写一个函数，用来获得特定节点的子节点。这个函数然后要对每个子节点调用自身来再次显示他们的子节点。这就是“递归”机制，因此称这种方法叫“递归方法”。

要实现整个树，我们只要调用函数时用一个空字符串作为 $parent 和 $level = 0: display_children('',0); 函数返回了我们的食品店的树状图如下：
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork

注意如果你只想看一个子树，你可以告诉函数从另一个节点开始。例如，要显示“Fruit”子树，你只要display_children('Fruit',0);
The Path to a Node节点的路径
利用差不多的函数，我们也可以查询某个节点的路径如果你只知道这个节点的名字或者ID。例如，“Cherry”的路径是“Food”> “Fruit”>“Red”。要获得这个路径，我们的函数要获得这个路径，这个函数必须从最深的层次开始：“Cheery”。但后查找这个节点的父 节点，并添加到路径中。在我们的例子中，这个父节点是“Red”。如果我们知道“Red”是“Cherry”的父节点。

这个函数现在返回了指定节点的路径。他把路径作为数组返回，这样我们可以使用print_r(get_path('Cherry')); 来显示，其结果是：
Array
(
   [0] => Food
   [1] => Fruit
   [2] => Red)
不足
正如我们所见，这确实是一个很好的方法。他很容易理解，同时代码也很简单。但是邻接列表模型的缺点在哪里呢？在大多数编程语言中，他运行很慢，效率很差。这主要是“递归”造成的。我们每次查询节点都要访问数据库。

每次数据库查询都要花费一些时间，这让函数处理庞大的树时会十分慢。

造成这个函数不是太快的第二个原因可能是你使用的语言。不像Lisp这类语言，大多数语言不是针对递归函数设计的。对于每个节点，函数都要调用他自 己，产生新的实例。这样，对于一个4层的树，你可能同时要运行4个函数副本。对于每个函数都要占用一块内存并且需要一定的时间初始化，这样处理大树时递归 就很慢了。

改进前序遍历树
现在，让我们看另一种存储树的方法。递归可能会很慢，所以我们就尽量不使用递归函数。我们也想尽量减少数据库查询的次数。最好是每次只需要查询一次。