php:Baumstrukturalgorithmus

Autor：Eve Cole Aktualisierungszeit：2009-06-02 18:07:31

Neu gepostet von Joy Murakami, ich habe diesen Artikel schon einmal gelesen und er ist ziemlich klar erklärt.
Wir werden an vielen Stellen auf dieses Problem stoßen, z. B. bei der Produktklassifizierung, in Foren mit mehrstufiger Baumstruktur, in Mailinglisten usw.: 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:

das Adjazenzlistenmodell
Modifizierter Vorbestellungsbaum-Traversalalgorithmus
Da ich kein Computer-Student bin und nichts über Datenstrukturen gelernt habe, habe ich diese beiden Namen wörtlich übersetzt. Bitte lassen Sie mich wissen, wenn ich falsch liege.

Diese beiden Dinge mögen beängstigend klingen, sind aber eigentlich sehr leicht zu verstehen. Hier verwende ich ein einfaches Lebensmittelverzeichnis als Beispieldaten. Unsere Datenstruktur sieht folgendermaßen aus:

Essen
|
|---Obst
|. |
|. |---Rot
|. |
|. |--Cherry
|. |
|. |---Gelb
|. |
|. |--Banane
|
|---Fleisch
|
|--Rindfleisch
|
|--Schweinefleisch
Um sich um jene PHP-Enthusiasten zu kümmern, die ein Durcheinander mit englischem

Essen haben: Essen
Obst: Obst
Rot: rot
Kirsche: Kirsche
Gelb:gelb
Banane: Banane
Fleisch: Fleisch
Rindfleisch:Rindfleisch
Schweinefleisch: Das Pork-

Adjazenzlistenmodell

ist ein Modell, das wir häufig verwenden und das in vielen Tutorials und Büchern vorgestellt wurde. 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 lassen sich die Daten im Beispiel in die folgende Tabelle umwandeln:

Anzeigen eines mehrstufigen Baums Wenn wir eine solche mehrstufige Struktur anzeigen müssen, benötigen wir eine rekursive Funktion.

<?php
// $parent ist das übergeordnete Element der Kinder, die wir sehen möchten
// $level wird erhöht, wenn wir tiefer in den Baum vordringen,
// wird verwendet, um eine schöne eingerückte Baumfunktion anzuzeigen

display_children($parent, $level)
{
// Alle untergeordneten Knoten eines übergeordneten Knotens abrufen $parent
$result = mysql_query('SELECT name FROM tree '.
'WHERE parent="'.$parent.'";');

// Jeden untergeordneten Knoten anzeigen
while ($row = mysql_fetch_array($result))
{
//Den Knotennamen einrücken
echo str_repeat(' ',$level).$row['name']."n"

//Rufen Sie diese Funktion erneut auf, um die untergeordneten Knoten des untergeordneten Knotens anzuzeigen

display_children($row['name'], $level+ 1);
}
}
?>
Wenn Sie diese Funktion auf dem Wurzelknoten (Food) der gesamten Struktur verwenden, können Sie die gesamte mehrstufige Baumstruktur ausdrucken. Da Food der Wurzelknoten ist und sein übergeordneter Knoten leer ist, rufen Sie Folgendes auf: display_children('',0). zeigt den Inhalt des gesamten Baums an:

Essen
Obst
Rot
Kirsche
Gelb
Banane
Fleisch
Rindfleisch
Schweinefleisch
Wenn Sie nur einen Teil der gesamten Struktur anzeigen möchten, beispielsweise den Fruchtteil, können Sie ihn wie folgt aufrufen:

display_children('Fruit',0);

Mit fast derselben Methode können wir den Pfad vom Wurzelknoten aus ermitteln zu einem beliebigen Knoten. Der Pfad von Cherry ist beispielsweise „Essen > Obst > Rot“. Um einen solchen Pfad zu erhalten, müssen wir auf der tiefsten Ebene „Cherry“ beginnen, den übergeordneten Knoten „Red“ abfragen und ihn zum Pfad hinzufügen. Anschließend müssen wir den übergeordneten Knoten von Red abfragen und zum Pfad hinzufügen. , und so weiter bis zur obersten Ebene „Essen“

<?php
// $node ist der tiefste Knoten
Funktion get_path($node)
{
// Den übergeordneten Knoten dieses Knotens abfragen
$result = mysql_query('SELECT parent FROM tree '.
'WHERE name="'.$node.'";');
$row = mysql_fetch_array($result);

// Verwenden Sie ein Array, um den Pfad zu speichern
$path = array();

// Wenn es nicht der Wurzelknoten ist, fahren Sie mit der Abfrage nach oben fort
// (Der Wurzelknoten hat keinen übergeordneten Knoten)
if ($row['parent']!='')
{
// Der letzte Teil des Pfads zu $node ist der Name
// des übergeordneten Elements von $node
$path[] = $row['parent'];

// wir sollten den Pfad zum übergeordneten Knoten dieses Knotens hinzufügen
// zum Pfad
$path = array_merge(get_path($row['parent']), $path);
}

// den Pfad zurückgeben
return $path;
}
?>
Wenn Sie diese Funktion für „Cherry“ verwenden: print_r(get_path('Cherry')), erhalten Sie ein Array wie dieses:

Array
(
[0] => Essen
[1] => Obst
[2] => Rot
)
Wie Sie es im gewünschten Format ausdrucken, bleibt Ihnen überlassen.
Nachteile: Diese Methode ist sehr einfach, leicht zu verstehen und leicht anzuwenden. Aber es gibt einige Nachteile. Hauptsächlich, weil die Laufgeschwindigkeit sehr langsam ist, weil jeder Knoten eine Datenbankabfrage erfordert und bei großen Datenmengen viele Abfragen erforderlich sind, 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.

Schauen wir uns nun eine andere Methode an, die keine rekursiven Berechnungen verwendet und schneller ist. Dies ist der modifizierte Preorder-Tree-Traversal-Algorithmus. Sie sind möglicherweise weniger mit der oben genannten Methode vertraut Beim ersten Mal ist die Methode leicht zu verstehen, aber da diese Methode keine rekursiven Abfragealgorithmen verwendet, weist sie eine höhere Abfrageeffizienz auf.

Wir zeichnen zunächst die mehrstufigen Daten wie folgt auf Papier: Schreiben Sie 1 auf die linke Seite des Wurzelknotens Food, fahren Sie dann den Baum hinunter fort, schreiben Sie 2 auf die linke Seite von Fruit und bewegen Sie sich dann weiter entlang des gesamten Baums . Kanten beschriften jeden Knoten links und rechts mit Nummern. 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 darauf, Ihre Finger zu bewegen.)
Diese Zahlen geben die Beziehung zwischen den einzelnen Knoten an. Die Zahlen von „Rot“ sind 3 und 6, die die Nachkommenknoten von „Lebensmittel“ 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 Nachkommen von „Fruit“ 2-11 sind

1 Essen 18
|
+----------------+
|. |
2 Obst 11 12 Fleisch 17
|. |
+-------+ +-------+
|. |
3 Rot 6 7 Gelb 10 13 Rindfleisch 14 15 Schweinefleisch 16
|. |
4 Kirsche 5 8 Banane 9

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.

+--------+-----+-----+
|. parent |. lft |
+--------+-----+-----+
|. |. 18 |
|. Essen |. 2 |
|. Obst |. 3 |
|. Rot |. 4 |
|. Frucht |. 7 |
|. Gelb |. 8 |
|. Lebensmittel |. 12 |
|. Fleisch |. Rindfleisch 13 |
|. Fleisch |. Schweinefleisch 15 |
+--------+-----+-----+
Hinweis: Da „links“ und „rechts“ in SQL eine besondere Bedeutung haben, müssen wir „lft“ und „rgt“ verwenden, um die linken und rechten Felder darzustellen. Darüber hinaus wird das Feld „Parent“ in dieser Struktur nicht mehr zur Darstellung der Baumstruktur benötigt. Mit anderen Worten: Die folgende Tabellenstruktur ist ausreichend.

+------------+-----+-----+
|. name |. rgt |
+------------+-----+-----+
|. Essen |. 1 |
|. Obst |. 2 |
|. Rot |. 3 |
|. Kirsche |. 4 |
|. Gelb |. 7 |
|. Banane |. 8 |
|. Fleisch |. 12 |
|. Rindfleisch |. 13 |
|. Schweinefleisch |. 15 |
+------------+-----+-----+
Okay, wir können jetzt Daten aus der Datenbank abrufen. Wenn wir beispielsweise alle Knoten unter dem Element „Frucht“ abrufen müssen, können wir die Abfrageanweisung wie folgt schreiben: SELECT * FROM tree WHERE lft BETWEEN 2 AND 11; Die Abfrage ergab die folgenden Ergebnisse.

+------------+-----+-----+
|. name |. rgt |
+------------+-----+-----+
|. Obst |. 2 |
|. Rot |. 3 |
|. Kirsche |. 4 |
|. Gelb |. 7 |
|. Banane |. 8 |
+------------+-----+-----+
Sehen Sie, Sie können alle diese Knoten mit nur einer Abfrage abrufen. Um die gesamte Baumstruktur wie die rekursive Funktion oben anzeigen zu können, müssen wir eine solche Abfrage auch sortieren. Sortieren Sie nach dem L-Wert des Knotens:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
Die verbleibende Frage ist, wie hierarchische Einrückungen angezeigt werden.

<?php
Funktion display_tree($root)
{
//Erhalte die linken und rechten Werte des Wurzelknotens
$result = mysql_query('SELECT lft, rgt FROM tree '.'WHERE name="'.$root.'";');
$row = mysql_fetch_array($result);

// Bereiten Sie einen leeren Rvalue-Stack vor
$right = array();

// Alle Nachkommenknoten des Wurzelpunkts abrufen
$result = mysql_query('SELECT name, lft, rgt FROM tree '.
'WHERE lft BETWEEN '.$row['lft'].'
$row['rgt'].' ORDER BY lft ASC;');

// Jede Zeile anzeigen
while ($row = mysql_fetch_array($result))
{
// Stack nur prüfen, wenn es einen gibt
if (count($right)>0)
{
// Überprüfe, ob wir den Knoten vom Stapel entfernen sollen
while ($right[count($right)-1]<$row['rgt'])
{
array_pop($right);
}
}

// Den Namen des Knotens einrücken.
echo str_repeat(' ',count($right)).$row['name']."n"

// Diesen Knoten zum Stapel hinzufügen
$right[] = $row['rgt'];
}
}
?>
Wenn Sie die obige Funktion ausführen, erhalten Sie das gleiche Ergebnis wie die rekursive Funktion. Es ist nur so, dass unsere neue Funktion möglicherweise schneller ist, da es nur zwei Datenbankabfragen gibt. Es ist einfacher, den Pfad eines Knotens zu kennen. Wenn wir den Pfad von Cherry wissen möchten, verwenden wir seine linken und rechten Werte 4 und 5, um eine Abfrage durchzuführen.

SELECT name FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
Dadurch erhalten Sie folgendes Ergebnis:

+----------------+
|. Name |
+----------------+
|. Essen |
|. Obst |
|. Rot |
+----------------+
Wie viele Nachkommenknoten hat ein bestimmter Knoten? Es ist ganz einfach: Die Gesamtzahl der Nachkommen = (Wert - linker Wert - 1)/2 Nachkommen = (rechts - links - 1) / 2 Glauben Sie es nicht? Rechnen Sie selbst. Mit dieser einfachen Formel können wir schnell berechnen, dass der Knoten „Frucht 2-11“ 4 Nachkommenknoten hat, während der Knoten „Banane 8-9“ keine Nachkommenknoten hat, was bedeutet, dass es sich nicht um einen Elternknoten handelt.
Erstaunlich, oder? Obwohl ich diese Methode schon viele Male angewendet habe, fühlt es sich immer noch großartig an, wenn ich sie anwende.

Dies ist in der Tat eine gute Methode, aber gibt es eine Möglichkeit, uns bei der Erstellung einer solchen Datentabelle mit linken und rechten Werten zu helfen? Hier ist eine weitere Funktion, die wir Ihnen vorstellen möchten. Diese Funktion kann die Tabelle mit Namen und übergeordneten Strukturen automatisch in eine Datentabelle mit linken und rechten Werten konvertieren.

<?php
Funktion rebuild_tree($parent, $left) {
// Der rechte Wert dieses Knotens ist der linke Wert + 1
$right = $left+1;

// alle Kinder dieses Knotens abrufen
$result = mysql_query('SELECT name FROM tree '.
'WHERE parent="'.$parent.'";');
while ($row = mysql_fetch_array($result)) {
// rekursive Ausführung dieser Funktion für jeden
// Kind dieses Knotens
// $right ist der aktuelle rechte Wert
// durch die Funktion rebuild_tree inkrementiert
$right = rebuild_tree($row['name'], $right);
}

// Wir haben den linken Wert, und jetzt haben wir ihn verarbeitet
// Für die Kinder dieses Knotens kennen wir auch den richtigen Wert
mysql_query('UPDATE tree SET lft='.$left.', rgt='.
$right.' WHERE name="'.$parent.'";');

// den richtigen Wert dieses Knotens zurückgeben + 1
return $right+1;
}
?>
Natürlich ist diese Funktion eine rekursive Funktion. Wir müssen diese Funktion vom Wurzelknoten aus ausführen, um einen Baum mit den linken und rechten Werten

rebuild_tree('Food',1) neu aufzubauen.
Diese Funktion sieht etwas kompliziert aus, aber ihre Funktion ist dieselbe wie die manuelle Nummerierung der Tabelle, nämlich die Umwandlung der dreidimensionalen mehrschichtigen Struktur in eine Datentabelle mit linken und rechten Werten.

Wie können wir also einen Knoten für eine solche Struktur hinzufügen, aktualisieren und löschen? Es gibt im Allgemeinen zwei Möglichkeiten, einen Knoten hinzuzufügen:

Behalten Sie den ursprünglichen Namen und die übergeordnete Struktur bei, verwenden Sie die alte Methode, um Daten zu den Daten hinzuzufügen, und verwenden Sie die Funktion rebuild_tree, um die gesamte Struktur neu zu nummerieren, nachdem jedes Datenelement hinzugefügt wurde.
Ein effizienterer Ansatz besteht darin, alle Werte rechts vom neuen Knoten zu ändern. Beispiel: Wir möchten eine neue Frucht „Erdbeere“ hinzufügen, die zum letzten untergeordneten Knoten des Knotens „Rot“ wird. Zuerst müssen wir etwas Platz dafür schaffen. Der rechte Wert von „Rot“ sollte von 6 auf 8 geändert werden, und der linke und rechte Wert von „Gelb 7-10“ sollte auf 9-12 geändert werden. Analog dazu können wir wissen, dass, wenn Sie Platz für neue Werte schaffen möchten, Sie 2 zu allen Knoten hinzufügen müssen, deren linker und rechter Wert größer als 5 ist (5 ist der rechte Wert des letzten untergeordneten Knotens von „Rot“). ). Also führen wir Datenbankoperationen wie diese aus:

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE-Baum SET lft=lft+2 WHERE lft>5;
Dadurch wird Platz für den neu eingefügten Wert frei. Jetzt können Sie im freigewordenen Platz einen neuen Datenknoten erstellen. Seine linken und rechten Werte sind 6 und 7, bzw.

INSERT INTO tree SET lft=6, rgt=7, name = 'Erdbeere';

Machen wir noch eine Abfrage und sehen nach! Wie wäre es damit? Bald.
Okay, jetzt können Sie Ihre mehrstufige Datenbankstruktur auf zwei verschiedene Arten entwerfen. Welche Methode Sie verwenden, hängt ganz von Ihrem persönlichen Urteilsvermögen ab, aber für Strukturen mit vielen Ebenen und einer großen Anzahl bevorzuge ich die zweite Methode. Die erste Methode ist einfacher, wenn das Abfragevolumen klein ist, die Daten jedoch häufig hinzugefügt und aktualisiert werden müssen.

Wenn die Datenbank dies unterstützt, können Sie außerdem rebuild_tree () und den Speicherplatzfreigabevorgang als Triggerfunktion auf der Datenbankseite schreiben und beim Einfügen und Aktualisieren automatisch ausführen. Dadurch kann eine bessere Betriebseffizienz erzielt werden Das Hinzufügen neuer Knoten wird einfacher.
Klassenrekursive Methode
Gepostet von Gast am 31. Mai 2004, 9:18 Uhr.
Ich habe ein Programm mit einer quasi-rekursiven Methode geschrieben, die nicht genau mit der Rekursion im Artikel übereinstimmt, und bereite mich darauf vor, es auf xoops zu übertragen:
Bei http://dev.xoops.org/modules/xfmod/project/?ulink

ist ein Speicherüberlauf aufgetreten, aber ich habe vor, die rekursive Methode weiterhin zu verwenden.

Ich hoffe, dass ich Gelegenheit zur Diskussion habe cms mit dir.
» Auf diesen Kommentar antworten
Oder ein Vergleich der beiden Methoden?
Gepostet von einem Gast am 17. März 2004, 20:30 Uhr.
Ich habe diesen Artikel sorgfältig studiert und das Gefühl gehabt, dass er sehr nützlich ist, aber dann habe ich noch einmal darüber nachgedacht und festgestellt, dass es ein Problem gibt (aus Gründen der Erinnerung nenne ich den Modus für angrenzende Verzeichnisse die rekursive Methode und die Durchquerung vor der Sortierung). Der Baumalgorithmus, den ich die Methode „Vorsortierbaum“ nenne):

1. Der größte Unterschied zwischen den beiden Methoden besteht darin, dass die Rekursion die Verwendung eines Stapels beim Abfragen erfordert, während der Vorsortierungsbaum die Hälfte der Knoten erfordert (bezogen auf die zweite Hälfte von). der eingefügte Knoten) beim Aktualisieren der Knoten von Aktualisierungen. Obwohl Sie auch gesagt haben, dass bei vielen Knoten und häufigen Aktualisierungen die Effizienz des vorsortierten Baums verringert wird und die Rekursion besser ist. Wenn viele Knotenebenen vorhanden sind, führt die Rekursion zunächst zu einem Stapelüberlauf Darüber hinaus ist die Rekursion selbst nicht sehr effizient, und jede Rekursionsebene erfordert den Betrieb der Datenbank, sodass der Gesamteffekt nicht ideal ist. Mein aktueller Ansatz besteht darin, alle Daten auf einmal herauszunehmen und dann rekursive Operationen für das Array auszuführen. Dies ist besser, wenn es weiter verbessert werden kann. Ein ROOT-Wurzelknoten kann zu jeder Datensatzzeile hinzugefügt werden (derzeit nur). Benachbarte übergeordnete Knoten werden aufgezeichnet, sodass die Effizienz beim Durchsuchen des Zweigbaums höher ist und es auch sehr praktisch ist, den Baum zu aktualisieren, was eine bessere Möglichkeit sein sollte.

2. Verbessern Sie die rekursive Methode. Bei der Berechnung der linken und rechten Werte der vorsortierten Baumknoten wird tatsächlich eine Traversalmethode verwendet. Der Stapel wird durch Push und Pop ersetzt werden manuell implementiert; wenn diese Methode im rekursiven Algorithmus referenziert wird und Sie bei der Durchführung der Rekursion ein Array anstelle des Stapels verwenden, können Sie auch die Effizienz der Rekursion verbessern.

3. Wenn Parallelität berücksichtigt wird, insbesondere bei der Aktualisierung des Baums, erfordert die Methode zum Aktualisieren von Knoteninformationen in einem großen Bereich des vorsortierten Baums besondere Aufmerksamkeit, um die Verwendung von Sperr- und Transaktionsmechanismen sicherzustellen Datenkonsistenz.

4. Bei mehreren Wurzelknoten oder mehreren übergeordneten Knoten handelt es sich in diesem Fall offensichtlich nicht um einen Standard-Binärbaum oder einen Multi-Fork-Baum. Der vorsortierte Baumalgorithmus muss erheblich verbessert werden, um ihn anzupassen, und die rekursive Methode wird frei angewendet, daher ist die Rekursion in diesem Fall anpassbarer. Dies liegt natürlich daran, dass die rekursive Methode eine Form verknüpfter Listen ist. Bäume und Diagramme können durch verknüpfte Listen ausgedrückt werden und sind natürlich sehr anpassungsfähig.

5. Intuitiv. Wenn Sie die in der Datenbank gespeicherten Daten ohne Programmoperationen direkt beobachten, ist es offensichtlich, dass die im rekursiven Modus gespeicherten Daten intuitiver sind, während die Daten im vorsortierten Baum schwer direkt zu lesen sind (für hierarchische). Beziehungen). Dies ist wichtig für den Datenaustausch.

Im Allgemeinen bevorzuge ich die Verwendung rekursiver Methoden, aber ich habe mir immer Sorgen über die Auswirkungen der Rekursion auf die Effizienz gemacht. Glücklicherweise wäre die rekursive Verwendung von Arrays anstelle von Stapeln eine bessere Lösung Verfahren. Der vorsortierte Baum ist eine effiziente Methode zum Lösen einfacher Bäume. Sobald Sie sich daran gewöhnt haben, sollte er sehr gut sein, insbesondere die umgekehrte Suche vom Blattknoten zum Wurzelknoten.

Fwolf
www.fwolf.com
» Auf diesen Kommentar antworten
Ich freue mich sehr über Ihre Antwort
Gepostet von shuke am 18. März 2004, 5:47 Uhr.
Ich freue mich sehr, dass Sie diesen Artikel so aufmerksam gelesen haben. Dieser Artikel wurde ursprünglich auf sitepoint.com veröffentlicht. Ich habe ihn übersetzt, in der Hoffnung, Freunden, die anfangen möchten, einige Methoden vorzustellen. Ihre Methode ist auch sehr gut, ich werde sie bei Gelegenheit ausprobieren. (Wenn Sie interessiert sind, schreiben Sie Ihre Methode und Ihren spezifischen Implementierungscode als Tutorial basierend auf dem obigen Beispiel, damit jeder es anhand praktischerer Beispiele nachahmen kann.) Wenn Sie Fragen zum Speichern mehrstufiger Strukturen in der Datenbank haben. Wenn Sie Wenn Sie an Forschung interessiert sind, finden Sie hier zwei weitere gute Links, die als Referenz dienen können:
Wir stellen die vier gängigen Methoden für einmalige Abfragen und Array-Sortierung vor. Ich denke, Ihr Skript muss besser sein.
Darüber hinaus habe ich gesehen, dass Sie Drupal auch über eine erweiterte Funktion namens verteiltes Benutzerauthentifizierungssystem verfügen. Solange Sie sich auf einer Drupal-Site registrieren, können Sie sich anmelden, um auf andere Drupal-Sites zuzugreifen. Ziemlich interessant.
Beste Wünsche!
» Auf diesen Kommentar antworten
Der Aufbau von Bäumen mithilfe von Schleifen wurde implementiert
Gepostet von Gast am 25. März 2004, 22:10 Uhr.
Ich habe alle Informationen gelesen, die Sie letztes Mal bereitgestellt haben, aber um ehrlich zu sein, gibt es im ersten Artikel nicht viel Neues. Vielleicht habe ich ihn und die Programmstruktur tatsächlich nicht sehr gut verstanden wurde nicht detailliert beschrieben. Es werden zu viele Funktionsschnittpunkte verwendet.
Es ist einfach so, dass ich hierarchische Benutzerrollen in einem System verwenden musste, also habe ich die Durchquerung basierend auf der Idee eines Arrays aufgeschrieben. Ich hatte keine Zeit, es zu klären, also werde ich es hier einfügen Ich hoffe, dass die Datenbank ADODB direkt aus dem System extrahiert wird. Sie verwendet hauptsächlich die leistungsstarken Array-Operationen von PHP und verwendet Schleifen. Der Kommentar ist eine ähnliche Methode, der Zeitpunkt der Verarbeitung der Ergebnisse ist jedoch unterschiedlich.

<?php
/**
* Liste anzeigen
* @access public
*/
Funktion DispList()
{
//Anzeigemodus ohne Einrückung
// $this->mIsDispListIndex = true;
// echo('<a href="?action=new&part=role">Neue Rolle hinzufügen</a> '); ">Neue Rolle hinzufügen</a> ');"
//
// $this->mListTitle = 'Benutzerrollenliste';
// $this->SetDataOption('list');
//
// $this->SetQueryTable( array($this->mTableUserRole) );
//
// //Reihenfolge abfragen
// $this->SetQueryOrder( 'asc', $this->mTableUserRole, 'sequence' );
//
// $this->Query('list');
// parent::DispList();

// //Eine weitere Anzeigemethode, die ein Array als Stapel verwendet. A: Speichern Sie die Rolle beim Pushen auf dem Stapel und löschen Sie die Quelle nach dem Pushen.
// $this->CheckProperty('mrDb');
// $this->CheckProperty('mrSql');
// $this->mrSql->Select('role, title, parent');
// $this->mrSql->From($this->mTableUserRole);
// $this->mrSql->Orderby('parent, sequence');
// $this->mRs = $this->mrDb->Execute($this->mrSql->Sql());
// if (0 < count($this->mRs))
// {
// $source = & $this->mRs->GetArray(); //Numerischer Index
// $stack = array(''); //stack
// $stacki = array(-1); //Entspricht dem Stapel und zeichnet die Ebene der Daten im Stapel im Baum auf
// $target = array();
// while (0 < count($stack))
// {
// $item = array_shift($stack);
// $lev = array_shift($stacki);
// if (!empty($item))
// {
// //Fügen Sie die verarbeiteten Daten hier in das Zielarray ein
// array_push($target, str_repeat('', $lev) . $item);
// //$s1 = str_repeat('', $lev) .
// }
// $del = array(); //Knoten, der aus $source gelöscht werden soll
// $ar = array(); //Knoten, die dem Stapel hinzugefügt werden müssen
// foreach ($source as $key=>$val)
// {
// //Übereinstimmende untergeordnete Knoten finden
// if (empty($item))
// {
// $find = empty($source[$key]['parent']);
// }
//anders
// {
// $find = ($item == $source[$key]['parent']);
// }
// if ($find)
// {
// array_unshift($ar, $source[$key]['role']);
// $del[] = $key;
// }
// }
// foreach ($ar as $val)
// {
//array_unshift($stack, $val);
//array_unshift($stacki, $lev + 1);
// }
// foreach ($del as $val)
// {
// unset($source[$val]);
// }
// echo(implode(', ', $stack) . ' ' . implode(', ', $stacki) . ' ' . implode(', ', $target) . ' ');
// }
//debug_array();
// }
//anders
// {
// echo('<center>Keine Daten abgerufen</center>');
// }

// Eine weitere Anzeigemethode, bei der ein Array als Stapel verwendet wird. B: Speichern Sie den Array-Index, wenn Sie den Stapel verschieben, entfernen Sie ihn aus dem Stapel und löschen Sie die Quelle nach der Verwendung.
$this->CheckProperty('mrDb');
$this->CheckProperty('mrSql');
$this->mrSql->Select('role, title, parent');
$this->mrSql->From($this->mTableUserRole);
$this->mrSql->Orderby('parent, sequence');
$this->mRs = $this->mrDb->Execute($this->mrSql->Sql());
if (!empty($this->mRs) && !$this->mRs->EOF)
{
$source = & $this->mRs->GetArray(); //numerischer Index
$stack = array(-1); //stack
$stacki = array(-1); //Entspricht dem Stapel und zeichnet die Ebene der Daten im Stapel im Baum auf
$target = array();
while (0 < count($stack))
{
$item = array_shift($stack);
$lev = array_shift($stacki);
if (-1 != $item)
{
//Fügen Sie die verarbeiteten Daten hier in das Zielarray ein
$s1 = str_repeat(' ', $lev) '<a href="?action=disp&part=role&role=' . $source[$item]['role'] . '">' $source[$item] ['title'] . '</a>';
$s2 = '<a href="?action=edit&part=role&role=' . $source[$item]['role'] . '">Bearbeiten</a> <a href="?action=delete&part=role&role= ' . $source[$item]['role'] '">Löschen</a>';
array_push($target, array($s1, $s2));
}
$del = array(); //Knoten, der aus $source gelöscht werden soll
$ar = array(); //Knoten, die dem Stapel hinzugefügt werden müssen
foreach ($source as $key=>$val)
{
//Übereinstimmende untergeordnete Knoten finden
if (-1 == $item)
{
$find = empty($source[$key]['parent']);
}
anders
{
$find = ($source[$item]['role'] == $source[$key]['parent']);
}
if($find)
{
array_unshift($ar, $key);
}
}
foreach ($ar als $val)
{
array_unshift($stack, $val);
array_unshift($stacki, $lev + 1);
}
//Aus Quelle löschen
unset($source[$item]);
//echo(implode(', ', $stack) . ' ' . implode(', ', $stacki) . ' ' . implode(', ', $target) . ' ');
}
//Ausgabe
echo('<a href="?action=new&part=role">Neue Rolle hinzufügen</a> ');
array_unshift($target, array('role', 'operation'));
$this->CheckProperty('mrLt');
$this->mrLt->SetData($target);
$this->mrLt->mListTitle = 'Benutzerrollenliste';
$this->mrLt->mIsDispIndex = false;
$this->mrLt->Disp();
}
anders
{
echo('<center>Keine Daten abgerufen</center>');
}
} // Ende der Funktion DispList
?>