Unendlicher Klassifizierungsalgorithmus zur Implementierung von linken und rechten Werten-PHP-Tutorial-php.cn

1. Einleitung

Solche Probleme werden bei der Produktklassifizierung, in mehrstufigen Baumstrukturforen, in Mailinglisten und an vielen anderen Orten auftreten: Wie werden mehrstufige strukturierte Daten gespeichert? In PHP-Anwendungen ist der Backend-Datenspeicher normalerweise eine relationale Datenbank, die große Datenmengen speichern und effiziente Datenabruf- und Aktualisierungsdienste bereitstellen kann. Die Grundform relationaler Daten ist jedoch eine kreuz und quer verlaufende Tabelle, bei der es sich um eine flache Struktur handelt. Wenn Sie eine mehrstufige Baumstruktur in einer relationalen Datenbank speichern möchten, müssen Sie angemessene Übersetzungsarbeiten durchführen. Als nächstes bespreche ich mit Ihnen, was ich gesehen und gehört habe und einige praktische Erfahrungen:
Grundsätzlich gibt es zwei gängige Entwurfsmethoden zum Speichern hierarchischer Daten in flachen Datenbanken:
* Adjazenzlistenmodell
* Modifizierter Preorder-Tree-Traversal-Algorithmus

2. Modell

Hier verwende ich ein einfaches Lebensmittelverzeichnis als unsere Beispieldaten.
Unsere Datenstruktur ist wie folgt, das Folgende ist der Code:

<code>Food
<span>|</span><span>|---Fruit</span><span>|    |</span><span>|    |---Red</span><span>|    |    |</span><span>|    |    |--Cherry</span><span>|    |</span><span>|    +---Yellow</span><span>|          |</span><span>|          +--Banana</span><span>|</span>
+---Meat
      <span>|--Beef</span>
      +--Pork</code>

Nach dem Login kopieren

Um sich um diejenigen PHP-Enthusiasten zu kümmern, die ein Durcheinander in Englisch haben

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

Nach dem Login kopieren

3 🎜>

1. Adjazenzlistenmodell

Dieses Modell wird häufig verwendet und wurde in vielen Tutorials und Büchern vorgestellt. Wir beschreiben die gesamte Baumstruktur durch eine flache Tabelle, indem wir jedem Knoten ein übergeordnetes Attribut hinzufügen, um den übergeordneten Knoten dieses Knotens darzustellen. Nach diesem Prinzip können die Daten im Beispiel in die folgende Tabelle umgewandelt werden:

Das Folgende ist der Code:

<code><span>+-----------------------+</span><span>|   parent |    name    |
+-----------------------+</span>
|          |    Food    |
|   Food   |   Fruit    |
|   Fruit  |    Green   |
|   Green  |    Pear    |
|   Fruit  |    Red     |
|   Red    |    Cherry  |
|   Fruit  |    Yellow  |
|   Yellow |    Banana  |
|   Food   |    Meat    |
|   Meat   |    Beef    |
<span>|   Meat   |    Pork    |
+-----------------------+</span></code>

Nach dem Login kopieren

Wir sehen, dass Pear ein untergeordneter Knoten von Green und Green ein untergeordneter Knoten von Fruit ist. Der Wurzelknoten „Food“ hat keinen übergeordneten Knoten. Um dieses Problem einfach zu beschreiben, wird in diesem Beispiel nur der Name zur Darstellung eines Datensatzes verwendet. In einer tatsächlichen Datenbank müssen Sie eine numerische ID verwenden, um jeden Knoten zu identifizieren. Die Datenbanktabellenstruktur sollte wahrscheinlich wie folgt aussehen: ID, Eltern-ID, Name, Beschreibung.

Mit einer solchen Tabelle können wir die gesamte mehrstufige Baumstruktur über die Datenbank speichern.

Zeigen Sie einen mehrstufigen Baum an. Wenn wir eine solche mehrstufige Struktur anzeigen müssen, benötigen wir eine

rekursive Funktion. Das Folgende ist der Code:

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

Nach dem Login kopieren

Die Verwendung dieser Funktion auf dem Wurzelknoten (Food) der gesamten Struktur kann die gesamte mehrstufige Baumstruktur ausdrucken, da Food der Wurzelknoten und sein übergeordneter Knoten ist ist leer, also so Rufen Sie auf: display_children(",0). Der Inhalt des gesamten Baums wird angezeigt:

<code>Food
    Fruit
        <span>Red</span>
            Cherry
        <span>Yellow</span>
            Banana
    Meat
        Beef
        Pork</code>

Nach dem Login kopieren

Wenn Sie nur einen Teil der gesamten Struktur anzeigen möchten, z. B. die Fruchtteil können Sie aufrufen: display_children('Fruit ',0);

Mit fast der gleichen Methode können wir den Pfad vom Wurzelknoten zu jedem Knoten ermitteln. Beispielsweise ist Cherrys Pfad „Food > ;; Fruit >; Red". Für den Pfad müssen wir auf der tiefsten Ebene „Cherry" beginnen, den übergeordneten Knoten „Red“ abfragen und ihn zum Pfad hinzufügen zum Pfad und so weiter bis zur obersten Ebene „Essen“, der folgende Code lautet:

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

Nach dem Login kopieren

Wenn Sie diese Funktion für „Cherry“ verwenden: print_r(get_path('Cherry')) , erhalten Sie ein Array wie dieses:

<code><span>Array</span> (
    [<span>0</span>] => Food
    [<span>1</span>] => Fruit
    [<span>2</span>] => Red
)</code>

Nach dem Login kopieren

Wie Sie es in das gewünschte Format drucken, bleibt Ihnen überlassen

Nachteile:

Diese Methode ist einfach, leicht zu verstehen und leicht anzuwenden. Aber es gibt einige Nachteile. Der Hauptgrund dafür ist, dass die Laufgeschwindigkeit sehr langsam ist und jeder Knoten eine Datenbankabfrage erfordert. Wenn die Datenmenge groß ist, sind viele Abfragen erforderlich, um einen Baum zu vervollständigen. Darüber hinaus muss jede Rekursionsebene aufgrund der Notwendigkeit rekursiver Operationen etwas Speicher belegen, sodass die Raumnutzungseffizienz relativ gering ist.

2. Vorbestellungsbaum-Durchlaufalgorithmus

Lassen Sie uns nun einen Blick auf eine andere schnellere Methode werfen, die keine rekursiven Berechnungen verwendet.

Möglicherweise sind Sie mit dieser Methode weniger vertraut und sie ist bei der ersten Verwendung nicht so einfach zu verstehen wie die obige Methode. Da diese Methode jedoch keinen rekursiven Abfragealgorithmus verwendet, weist sie eine höhere Abfrageeffizienz auf.

Wir zeichnen zunächst die mehrstufigen Daten wie folgt auf Papier: Schreiben Sie 1 links vom Wurzelknoten Essen, fahren Sie dann den Baum hinunter fort, schreiben Sie 2 links von Obst und bewegen Sie sich weiter vorwärts. Beschriften Sie jeden Knoten links und rechts am Rand des gesamten Baums mit Zahlen. Die letzte Zahl ist 18, rechts neben „Essen“ markiert. Im Bild unten sehen Sie die gesamte mehrstufige Struktur markiert mit Zahlen. (Verstehen Sie es nicht? Zeigen Sie mit den Fingern auf die Zahlen und zählen Sie von 1 bis 18, dann werden Sie es verstehen. Wenn Sie es immer noch nicht verstehen, zählen Sie noch einmal und achten Sie auf die Bewegung Ihrer Finger.)

Diese Zahlen geben die Beziehung zwischen den einzelnen Knoten an. Die Zahlen von „Rot“ sind 3 und 6, die die Nachkommenknoten von „Food“ 1-18 sind. Ebenso können wir sehen, dass alle Knoten mit einem linken Wert größer als 2 und einem rechten Wert kleiner als 11 Nachkommenknoten von „Fruit“ 2-11 sind.
Das Folgende ist der Code:

<code><span>1</span> Food <span>18</span><span>|</span>
            +------------------------------+
            <span>|                              |</span><span>2</span> Fruit <span>11</span><span>12</span> Meat <span>17</span><span>|                              |</span>
    +-------------+                 +------------+
    <span>|             |                 |            |</span><span>3</span> Red <span>6</span><span>7</span> Yellow <span>10</span><span>13</span> Beef <span>14</span><span>15</span> Pork <span>16</span><span>|             |</span><span>4</span> Cherry <span>5</span><span>8</span> Banana <span>9</span></code>

Nach dem Login kopieren

Auf diese Weise kann die gesamte Baumstruktur über die linken und rechten Werte in der Datenbank gespeichert werden. Bevor wir fortfahren, werfen wir einen Blick auf die untenstehende zusammengestellte Datentabelle.

Hier ist der Code:

<code><span>+----------+</span>------------<span>+-----+</span>-----+
<span>|  parent  |    name    | lft | rgt |
+----------+------------+-----+-----+</span>
|          |    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  |
<span>|   Meat   |    Pork    | 15  | 16  |
+----------+------------+-----+-----+</span></code>

Nach dem Login kopieren

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

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

Nach dem Login kopieren

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

<code><span><span>SELECT</span> * <span>FROM</span> tree <span>WHERE</span> lft BETWEEN <span>2</span><span>AND</span><span>11</span>;</span></code>

Nach dem Login kopieren

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

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

Nach dem Login kopieren

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

<code><span><span>SELECT</span> * <span>FROM</span> tree <span>WHERE</span> lft BETWEEN <span>2</span><span>AND</span><span>11</span><span>ORDER</span><span>BY</span> lft <span>ASC</span>;</span></code>

Nach dem Login kopieren

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

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

Nach dem Login kopieren

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

<code><span>SELECT</span> name <span>FROM</span> tree <span>WHERE</span> lft < <span>4</span><span>AND</span> rgt >; <span>5</span><span>ORDER</span><span>BY</span> lft <span>ASC</span>;</code>

Nach dem Login kopieren

这样就会得到以下的结果：
以下是代码：

<code><span>+------------+</span><span>|    name    |
+------------+</span>
|    Food    |
|    Fruit   |
<span>|    Red     |
+------------+</span></code>

Nach dem Login kopieren

那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右值-左值-1)/2

<code>descendants = (<span>right</span> – <span>left</span> - <span>1</span>) / <span>2</span></code>

Nach dem Login kopieren

不相信？自己算一算啦。
用这个简单的公式，我们可以很快的算出”Fruit 2-11”节点有4个子孙节点，而”Banana 8-9”节点没有子孙节点，也就是说它不是一个父节点了。
很神奇吧？虽然我已经多次用过这个方法，但是每次这样做的时候还是感到很神奇。
这的确是个很好的办法，但是有什么办法能够帮我们建立这样有左右值的数据表呢？这里再介绍一个函数给大家，这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。
以下是代码：

<code><span><?php</span><span><span>function</span><span>rebuild_tree</span><span>(<span>$parent</span>, <span>$left</span>)</span> {</span><span>// the right value of this node is the left value + 1</span><span>$right</span> = <span>$left</span>+<span>1</span>;
    <span>// get all children of this node</span><span>$result</span> = mysql_query(<span>"
        SELECT name
        FROM tree
        WHERE parent = '"</span> . <span>$parent</span> . <span>"'
        ;"</span>
    );
    <span>while</span> (<span>$row</span> = mysql_fetch_array(<span>$result</span>)) {
        <span>// recursive execution of this function for each</span><span>// child of this node</span><span>// $right is the current right value, which is</span><span>// incremented by the rebuild_tree function</span><span>$right</span> = rebuild_tree(<span>$row</span>[<span>'name'</span>], <span>$right</span>);
    }
    <span>// we've got the left value, and now that we've processed</span><span>// the children of this node we also know the right value</span>
    mysql_query(<span>"
        UPDATE tree
        SET
            lft = '"</span> . <span>$left</span> . <span>"',
            rgt= '"</span> . <span>$right</span> . <span>"'
        WHERE name = '"</span> . <span>$parent</span> . <span>"'
        ;"</span>
    );
    <span>// return the right value of this node + 1</span><span>return</span><span>$right</span> + <span>1</span>;
}
<span>?></span></code>

Nach dem Login kopieren

当然这个函数是一个递归函数，我们需要从根节点开始运行这个函数来重建一个带有左右值的树

<code><span>rebuild_tree(<span>'Food'</span>,<span>1</span>)</span>;</code>

Nach dem Login kopieren

这个函数看上去有些复杂，但是它的作用和手工对表进行编号一样，就是将立体多层结构的转换成一个带有左右值的数据表。

那么对于这样的结构我们该如何增加，更新和删除一个节点呢？
增加一个节点一般有两种方法：
第一种，保留原有的name 和parent结构，用老方法向数据中添加数据，每增加一条数据以后使用rebuild_tree函数对整个结构重新进行一次编号。
第二种，效率更高的办法是改变所有位于新节点右侧的数值。举例来说：我们想增加一种新的水果”Strawberry”（草莓）它将成为”Red”节点的最后一个子节点。首先我们需要为它腾出一些空间。”Red”的右值应当从6改成8，”Yellow 7-10 “的左右值则应当改成 9-12。依次类推我们可以得知，如果要给新的值腾出空间需要给所有左右值大于5的节点（5 是”Red”最后一个子节点的右值）加上2。所以我们这样进行数据库操作：

<code><span><span>UPDATE</span> tree <span>SET</span> rgt = rgt + <span>2</span><span>WHERE</span> rgt > <span>5</span>;</span><span><span>UPDATE</span> tree <span>SET</span> lft = lft + <span>2</span><span>WHERE</span> lft > <span>5</span>;</span></code>

Nach dem Login kopieren

这样就为新插入的值腾出了空间，现在可以在腾出的空间里建立一个新的数据节点了，它的左右值分别是6和7

<code><span><span>INSERT</span><span>INTO</span> tree <span>SET</span> lft=<span>6</span>, rgt=<span>7</span>, name=<span>'Strawberry'</span>;</span></code>

Nach dem Login kopieren

再做一次查询看看吧！怎么样？很快吧。

四、结语

好了，现在你可以用两种不同的方法设计你的多级数据库结构了，采用何种方式完全取决于你个人的判断，但是对于层次多数量大的结构我更喜欢第二种方法。如果查询量较小但是需要频繁添加和更新的数据，则第一种方法更为简便。
另外，如果数据库支持的话你还可以将rebuild_tree()和腾出空间的操作写成数据库端的触发器函数，在插入和更新的时候自动执行，这样可以得到更好的运行效率，而且你添加新节点的SQL语句会变得更加简单。

http://www.cnblogs.com/guowei1027/archive/2009/12/14/1623507.html

以上就介绍了无限分类左右值实现算法，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。