澳门正规赌博十大网站-澳门游戏网站
做最好的网站

解析PHP无限级分类方法及代码,预排序遍历树算

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

一、引言 产品分类,多级的树状结构的论坛,邮件列表等许多地方我们都会遇到这样的问题:如何存储多级结构的数据?在PHP的应用中,提供后台数据存储的通常是关系型数据库,它能够保存大量的数据,提供高效的数据检索和更新服务。然而关系型数据的基本形式是纵横交错的表,是一个平面的结构,如果要将多级树状结构存储在关系型数据库里就需要进行合理的翻译工作。接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下:
层级结构的数据保存在平面的数据库中基本上有两种常用设计方法:     * 毗邻目录模式(adjacency list model)
    *解析PHP无限级分类方法及代码,预排序遍历树算法。 预排序遍历树算法(modified preorder tree traversal algorithm)
我不是计算机专业的,也没有学过什么数据结构的东西,所以这两个名字都是我自己按照字面的意思翻的,如果说错了还请多多指教。这两个东西听着好像很吓人,其实非常容易理解。

预排序遍历树算法

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

二、模型 这里我用一个简单食品目录作为我们的示例数据。
我们的数据结构是这样的,以下是代码:

现在让我们看一看另外一种不使用递归计算,更加快速的方法,这就是预排序遍历树算法(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本文包含了一些代码的例子来演示如何保存和获取数据。我选择PHP来写例子,因为我常用这个语言,而且很多人也都使用或者知道这个语言。你可以很方便地把它们翻译成你自己用的语言。

Food

以下是代码:                          1 Food 18

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

|---Fruit

                             |

图片 2

|    |---Red

            ------------------------------

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

|    |    |--Cherry

            |                              |

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

|    ---Yellow

        2 Fruit 11                     12 Meat 17

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

|          --Banana

            |                              |

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

---Meat
      |--Beef
      --Pork

    -------------                  ------------

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

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

    |             |                 |            |

图片 4

复制代码 代码如下:

3 Red 6      7 Yellow 10       13 Beef 14   15 Pork 16

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

Food  : 食物
Fruit : 水果
解析PHP无限级分类方法及代码,预排序遍历树算法。Red   : 红色
Cherry: 樱桃
Yellow: 黄色
解析PHP无限级分类方法及代码,预排序遍历树算法。Banana: 香蕉
Meat  : 肉类
Beef  : 牛肉
Pork  : 猪肉

    |             |

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

三、实现
1、毗邻目录模式(adjacency list model)
这种模式我们经常用到,很多的教程和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则,例子中的数据可以转化成如下的表:
以下是代码:

4 Cherry 5    8 Banana 9
复制代码这样整个树状结构可以通过左右值来存储到数据库中。继续之前,我们看一看下面整理过的数据表。

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

复制代码 代码如下:

以下是代码: ---------- ------------ ----- -----

改进前序遍历树
解析PHP无限级分类方法及代码,预排序遍历树算法。现在,让我们看另一种存储树的方法。递归可能会很慢,所以我们就尽量不使用递归函数。我们也想尽量减少数据库查询的次数。最好是每次只需要查询一次。

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

|  parent  |    name    | lft | rgt |

解析PHP无限级分类方法及代码,预排序遍历树算法。我们先把树按照水平方式摆开。从根节点开始(“Food”),然后他的左边写上1。然后按照树的顺序(从上到下)给“Fruit”的左边写上2。这 样,你沿着树的边界走啊走(这就是“遍历”),然后同时在每个节点的左边和右边写上数字。最后,我们回到了根节点“Food”在右边写上18。下面是标上 了数字的树,同时把遍历的顺序用箭头标出来了。

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

---------- ------------ ----- -----

图片 5

解析PHP无限级分类方法及代码,预排序遍历树算法。复制代码 代码如下:

|          |    Food    | 1   | 18  |

 

<?php
// $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 tree
function display_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   |   Fruit    | 2   | 11  |

我们称这些数字为左值和右值(如,“Food”的左值是1,右值是18)。正如你所见,这些数字按时了每个节点之间的关系。因为“Red”有3和6 两个值,所以,它是有拥有1-18值的“Food”节点的后续。同样的,我们可以推断所有左值大于2并且右值小于11的节点,都是有2-11的 “Food”节点的后续。这样,树的结构就通过左值和右值储存下来了。这种数遍整棵树算节点的方法叫做“改进前序遍历树”算法。

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

|   Fruit  |    Red     | 3   |  6  |

在继续前,我们先看看我们的表格里的这些值:

复制代码 代码如下:

|   Red    |    Cherry  | 4   |  5  |

图片 6

Food
    Fruit
        Red
            Cherry
        Yellow
            Banana
    Meat
        Beef
        Pork

|   Fruit  |    Yellow  | 7   | 10  |

注意单词“left”和“right”在SQL中有特殊的含义。因此,我们只能用“lft”和“rgt”来表示这两个列。(译注——其实Mysql 中可以用“`”来表示,如“`left`”,MSSQL中可以用“[]”括出,如“[left]”,这样就不会和关键词冲突了。)同样注意这里我们已经不需要“parent”列了。我们只需要使用lft和rgt就可以存储树的结构。

如果你只想显示整个结构中的一部分,比如说水果部分,就可以这样调用:display_children('Fruit',0);
几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是 "Food >; Fruit >; Red"。 为了得到这样的一个路径我们需要从最深的一级"Cherry"开始, 查询得到它的父节点"Red"把它添加到路径中,然后我们再查询Red的父节点并把它也添加到路径中,以此类推直到最高层的"Food",以下是代码:

|   Yellow |    Banana  | 8   |  9  |

获取树 如果你要通过左值和右值来显示这个树的话,你要首先标识出你要获取的那些节点。例如,如果你想获得“Fruit”子树,你要选择那些左值在2到11的节点。用SQL语句表达:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
这个会返回:

复制代码 代码如下:

|   Food   |    Meat    | 12  | 17  |

图片 7

<?php
// $node 是那个最深的节点
function get_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 path
    return $path;
}
?>;

|   Meat   |    Beef    | 13  | 14  |

好吧,现在整个树都在一个查询中了。现在就要像前面的递归函数那样显示这个树,我们要加入一个ORDER BY子句在这个查询中。如果你从表中添加和删除行,你的表可能就顺序不对了,我们因此需要按照他们的左值来进行排序。
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
就只剩下缩进的问题了。

如果对"Cherry"使用这个函数:print_r(get_path('Cherry')),就会得到这样的一个数组了:

|   Meat   |    Pork    | 15  | 16  |

要显示树状结构,子节点应该比他们的父节点稍微缩进一些。我们可以通过保存一个右值的一个栈。每次你从一个节点的子节点开始时,你把这个节点的右值 添加到栈中。你也知道子节点的右值都比父节点的右值小,这样通过比较当前节点和栈中的前一个节点的右值,你可以判断你是不是在显示这个父节点的子节点。当 你显示完这个节点,你就要把他的右值从栈中删除。要获得当前节点的层数,只要数一下栈中的元素。

复制代码 代码如下:

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

图片 8

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

以下是代码: ------------ ----- -----

如果运行这段代码,你可以获得和上一部分讨论的递归函数一样的结果。而这个函数可能会更快一点:他不采用递归而且只是用了两个查询

接下来如何把它打印成你希望的格式,就是你的事情了。
缺点: 这种方法很简单,容易理解,好上手。但是也有一些缺点。主要是因为运行速度很慢,由于得到每个节点都需要进行数据库查询,数据量大的时候要进行很多查询才能完成一个树。另外由于要进行递归运算,递归的每一级都需要占用一些内存所以在空间利用上效率也比较低。

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

|    name    | lft | rgt |

节点的路径 有了新的算法,我们还要另找一种新的方法来获得指定节点的路径。这样,我们就需要这个节点的祖先的一个列表。

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

------------ ----- -----

由于新的表结构,这不需要花太多功夫。你可以看一下,例如,4-5的“Cherry”节点,你会发现祖先的左值都小于4,同时右值都大于5。这样,我们就可以使用下面这个查询:
SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
注意,就像前面的查询一样,我们必须使用一个ORDER BY子句来对节点排序。这个查询将返回:

复制代码 代码如下:

|    Food    | 1   | 18  |

-------
| title |
-------
| Food  |
| Fruit |
| Red   |
-------

                         1 Food 18

|    Fruit   | 2   | 11  |

我们现在只要把各行连起来,就可以得到“Cherry”的路径了。
有多少个后续节点?How Many Descendants 如果你给我一个节点的左值和右值,我就可以告诉你他有多少个后续节点,只要利用一点点数学知识。
因为每个后续节点依次会对这个节点的右值增加2,所以后续节点的数量可以这样计算:
descendants = (right – left - 1) / 2
利用这个简单的公式,我可以立刻告诉你2-11的“Fruit”节点有4个后续节点,8-9的“Banana”节点只是1个子节点,而不是父节点。

            ------------------------------

|    Red     | 3   |  6  |

自动化树遍历 现在你对这个表做一些事情,我们应该学习如何自动的建立表了。这是一个不错的练习,首先用一个小的树,我们也需要一个脚本来帮我们完成对节点的计数。
让我们先写一个脚本用来把一个邻接列表转换成前序遍历树表格。

        2 Fruit 11                     12 Meat 17

|    Cherry  | 4   |  5  |

图片 9

    -------------                  ------------

|    Yellow  | 7   | 10  |

这是一个递归函数。你要从rebuild_tree('Food',1); 开始,这个函数就会获取所有的“Food”节点的子节点。

3 Red 6      7 Yellow 10       13 Beef 14   15 Pork 16

|    Banana  | 8   |  9  |

如果没有子节点,他就直接设置它的左值和右值。左值已经给出了,1,右值则是左值加1。如果有子节点,函数重复并且返回最后一个右值。这个右值用来作为“Food”的右值。

4 Cherry 5    8 Banana 9

|    Meat    | 12  | 17  |

递归让这个函数有点复杂难于理解。然而,这个函数确实得到了同样的结果。他沿着树走,添加每一个他看见的节点。你运行了这个函数之后,你会发现左值和右值和预期的是一样的(一个快速检验的方法:根节点的右值应该是节点数量的两倍)。

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

|    Beef    | 13  | 14  |

添加一个节点 我们如何给这棵树添加一个节点?有两种方式:在表中保留“parent”列并且重新运行rebuild_tree() 函数——一个很简单但却不是很优雅的函数;或者你可以更新所有新节点右边的节点的左值和右值。

复制代码 代码如下:

|    Pork    | 15  | 16  |

第一个想法比较简单。你使用邻接列表方法来更新,同时使用改进前序遍历树来查询。如果你想添加一个新的节点,你只需要把节点插入表格,并且设置好parent列。然后,你只需要重新运行rebuild_tree() 函数。这做起来很简单,但是对大的树效率不高。

---------- ------------ ----- -----
|  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  |
---------- ------------ ----- -----

------------ ----- -----
复制代码好了我们现在可以从数据库中获取数据了,例如我们需要得到"Fruit"项下的所有所有节点就可以这样写查询语句: SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
复制代码这个查询得到了以下的结果。

第二种添加和删除节点的方法是更新新节点右边的所有节点。让我们看一下例子。我们要添加一种新的水果——“Strawberry”,作为“Red” 的最后一个子节点。首先,我们要腾出一个空间。“Red”的右值要从6变成8,7-10的“Yellow”节点要变成9-12,如此类推。更新“Red” 节点意味着我们要把所有左值和右值大于5的节点加上2。

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

以下是代码: ------------ ----- -----

我们用一下查询: UPDATE tree SET rgt=rgt 2 WHERE rgt>5;
UPDATE tree SET lft=lft 2 WHERE lft>5;
现在我们可以添加一个新的节点“Strawberry”来填补这个新的空间。这个节点左值为6右值为7。
INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';
如果我们运行display_tree() 函数,我们将发现我们新的“Strawberry”节点已经成功地插入了树中:Food
 Fruit
   Red
     Cherry
     Strawberry
   Yellow
     Banana
 Meat
   Beef
   Pork

复制代码 代码如下:

|    name    | lft | rgt |

缺点 首先,改进前序遍历树算法看上去很难理解。它当然没有邻接列表方法简单。然而,一旦你习惯了左值和右值这两个属性,他就会变得清晰起来,你可以用这个技术来完成临街列表能完成的所有事情,同时改进前序遍历树算法更快。当然,更新树需要很多查询,要慢一点,但是取得节点却可以只用一个查询。

------------ ----- -----
|    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  |
------------ ----- -----

------------ ----- -----

本文由澳门正规赌博十大网站发布于澳门游戏网站,转载请注明出处:解析PHP无限级分类方法及代码,预排序遍历树算