无限分类左右值实现算法

一、引言

产品分类，多级的树状结构的论坛，邮件列表等许多地方我们都会遇到这样的问题：如何存储多级结构的数据？在PHP的应用中，提供后台数据存储的通常是关系型数据库，它能够保存大量的数据，提供高效的数据检索和更新服务。然而关系型数据的基本形式是纵横交错的表，是一个平面的结构，如果要将多级树状结构存储在关系型数据库里就需要进行合理的翻译工作。接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下：
层级结构的数据保存在平面的数据库中基本上有两种常用设计方法：
* 毗邻目录模式(adjacency list model)
* 预排序遍历树算法(modified preorder tree traversal algorithm)

二、模型

这里我用一个简单食品目录作为我们的示例数据。
我们的数据结构是这样的，以下是代码：

Food
||---Fruit|    ||    |---Red|    |    ||    |    |--Cherry|    ||    +---Yellow|          ||          +--Banana|
+---Meat
      |--Beef
      +--Pork

为了照顾那些英文一塌糊涂的PHP爱好者

Food  : 食物
Fruit : 水果
Red   : 红色
Cherry: 樱桃
Yellow: 黄色
Banana: 香蕉
Meat  : 肉类
Beef  : 牛肉
Pork  : 猪肉

三、实现

1、毗邻目录模式(adjacency list model)

这种模式我们经常用到，很多的教程和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则，例子中的数据可以转化成如下的表：
以下是代码：

+-----------------------+|   parent |    name    |
+-----------------------+
|          |    Food    |
|   Food   |   Fruit    |
|   Fruit  |    Green   |
|   Green  |    Pear    |
|   Fruit  |    Red     |
|   Red    |    Cherry  |
|   Fruit  |    Yellow  |
|   Yellow |    Banana  |
|   Food   |    Meat    |
|   Meat   |    Beef    |
|   Meat   |    Pork    |
+-----------------------+

我们看到 Pear 是Green的一个子节点，Green是Fruit的一个子节点。而根节点’Food’没有父节点。 为了简单地描述这个问题，这个例子中只用了name来表示一个记录。 在实际的数据库中，你需要用数字的id来标示每个节点，数据库的表结构大概应该像这样：id, parent_id, name, descrīption。
有了这样的表我们就可以通过数据库保存整个多级树状结构了。

显示多级树，如果我们需要显示这样的一个多级结构需要一个递归函数。
以下是代码：

// $parent is the parent of the children we want to see// $level is increased when we go deeper into the tree,//        used to display a nice indented treefunctiondisplay_children($parent, $level) {// 获得一个 父节点 $parent 的所有子节点$result = mysql_query("
        SELECT name
        FROM tree
        WHERE parent = '" . $parent . "'
        ;"
    );
    // 显示每个子节点while ($row = mysql_fetch_array($result)) {
        // 缩进显示节点名称echo str_repeat('  ', $level) . $row['name'] . "\n";
        //再次调用这个函数显示子节点的子节点
        display_children($row['name'], $level+1);
    }
}
?>

对整个结构的根节点（Food）使用这个函数就可以打印出整个多级树结构，由于Food是根节点它的父节点是空的，所以这样调用: display_children(”,0)。将显示整个树的内容：

Food
    Fruit
        Red
            Cherry
        Yellow
            Banana
    Meat
        Beef
        Pork

如果你只想显示整个结构中的一部分，比如说水果部分，就可以这样调用：display_children(‘Fruit’,0);

几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是　“Food >; Fruit >; Red”。 为了得到这样的一个路径我们需要从最深的一级”Cherry”开始， 查询得到它的父节点”Red”把它添加到路径中，然后我们再查询Red的父节点并把它也添加到路径中，以此类推直到最高层的”Food”,以下是代码：

// $node 是那个最深的节点functionget_path($node) {// 查询这个节点的父节点$result = mysql_query("
        SELECT parent
        FROM tree
        WHERE name = '" . $node ."'
        ;"
    );
    $row = mysql_fetch_array($result);
    // 用一个数组保存路径$path = array();
    // 如果不是根节点则继续向上查询// (根节点没有父节点)if ($row['parent'] != '') {
        // the last part of the path to $node, is the name// of the parent of $node$path[] = $row['parent'];
        // we should add the path to the parent of this node// to the path$path = array_merge(get_path($row['parent']), $path);
    }
    // return the pathreturn$path;
}
?>

如果对”Cherry”使用这个函数：print_r(get_path(‘Cherry’))，就会得到这样的一个数组了：

Array (
    [0] => Food
    [1] => Fruit
    [2] => Red
)

接下来如何把它打印成你希望的格式，就是你的事情了。

缺点：
这种方法很简单，容易理解，好上手。但是也有一些缺点。主要是因为运行速度很慢，由于得到每个节点都需要进行数据库查询，数据量大的时候要进行很多查询才能完成一个树。另外由于要进行递归运算，递归的每一级都需要占用一些内存所以在空间利用上效率也比较低。

2、预排序遍历树算法

现在让我们看一看另外一种不使用递归计算，更加快速的方法，这就是预排序遍历树算法(modified preorder tree traversal algorithm)
这种方法大家可能接触的比较少，初次使用也不像上面的方法容易理解，但是由于这种方法不使用递归查询算法，有更高的查询效率。

我们首先将多级数据按照下面的方式画在纸上，在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进，沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。在下面的这张图中你可以看到整个标好了数字的多级结构。（没有看懂？用你的手指指着数字从1数到18就明白怎么回事了。还不明白，再数一遍，注意移动你的手指）。
这些数字标明了各个节点之间的关系，”Red”的号是3和6，它是 “Food” 1-18 的子孙节点。 同样，我们可以看到 所有左值大于2和右值小于11的节点 都是”Fruit” 2-11 的子孙节点。
以下是代码：

1 Food 18|
            +------------------------------+
            |                              |2 Fruit 1112 Meat 17|                              |
    +-------------+                 +------------+
    |             |                 |            |3 Red 67 Yellow 1013 Beef 1415 Pork 16|             |4 Cherry 58 Banana 9

这样整个树状结构可以通过左右值来存储到数据库中。继续之前，我们看一看下面整理过的数据表。
以下是代码：

+----------+------------+-----+-----+
|  parent  |    name    | lft | rgt |
+----------+------------+-----+-----+
|          |    Food    | 1   | 18  |
|   Food   |   Fruit    | 2   | 11  |
|   Fruit  |    Red     | 3   |  6  |
|   Red    |    Cherry  | 4   |  5  |
|   Fruit  |    Yellow  | 7   | 10  |
|   Yellow |    Banana  | 8   |  9  |
|   Food   |    Meat    | 12  | 17  |
|   Meat   |    Beef    | 13  | 14  |
|   Meat   |    Pork    | 15  | 16  |
+----------+------------+-----+-----+

注意：由于”left”和”right”在 SQL中有特殊的意义，所以我们需要用”lft”和”rgt”来表示左右字段。 另外这种结构中不再需要”parent”字段来表示树状结构。也就是 说下面这样的表结构就足够了。
以下是代码：

+------------+-----+-----+|    name    | lft | rgt |
+------------+-----+-----+
|    Food    | 1   | 18  |
|    Fruit   | 2   | 11  |
|    Red     | 3   |  6  |
|    Cherry  | 4   |  5  |
|    Yellow  | 7   | 10  |
|    Banana  | 8   |  9  |
|    Meat    | 12  | 17  |
|    Beef    | 13  | 14  |
|    Pork    | 15  | 16  |
+------------+-----+-----+

好了我们现在可以从数据库中获取数据了，例如我们需要得到”Fruit”项下的所有所有节点就可以这样写查询语句：

SELECT * FROM tree WHERE lft BETWEEN 2AND11;

这个查询得到了以下的结果。
以下是代码：

+------------+-----+-----+|    name    | lft | rgt |
+------------+-----+-----+
|    Fruit   | 2   | 11  |
|    Red     | 3   |  6  |
|    Cherry  | 4   |  5  |
|    Yellow  | 7   | 10  |
|    Banana  | 8   |  9  |
+------------+-----+-----+

看到了吧，只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构，我们还需要对这样的查询进行排序。用节点的左值进行排序：

SELECT * FROM tree WHERE lft BETWEEN 2AND11ORDERBY lft ASC;

剩下的问题如何显示层级的缩进了。
以下是代码：

functiondisplay_tree($root) {// 得到根节点的左右值$result = mysql_query("
        SELECT lft, rgt
        FROM tree
        WHERE name = '" . $root . "'
        ;"
    );
    $row = mysql_fetch_array($result);
    // 准备一个空的右值堆栈$right = array();
    // 获得根基点的所有子孙节点$result = mysql_query("
        SELECT name, lft, rgt
        FROM tree
        WHERE lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] ."'
        ORDER BY lft ASC
        ;"
    );
    // 显示每一行while ($row = mysql_fetch_array($result)) {
        // only check stack if there is oneif (count($right) > 0) {
            // 检查我们是否应该将节点移出堆栈while ($right[count($right) - 1] $row['rgt']) {
                array_pop($right);
            }
        }
        // 缩进显示节点的名称echo str_repeat('  ',count($right)) . $row['name'] . "\n";
        // 将这个节点加入到堆栈中$right[] = $row['rgt'];
    }
}
?>

如果你运行一下以上的函数就会得到和递归函数一样的结果。只是我们的这个新的函数可能会更快一些，因为只有2次数据库查询。
要获知一个节点的路径就更简单了，如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。

SELECT name FROM tree WHERE lft 4