Heim php教程 php手册 php:树形结构的算法 2

php:树形结构的算法 2

Jun 21, 2016 am 08:57 AM
name nbsp right tree

  1 Food 18
  |
  +---------------------------------------+
  | |
  2 Fruit 11 12 Meat 17
  | |
  +------------------------+ +---------------------+
  | | | |
  3 Red 6 7 Yellow 10 13 Beef 14 15 Pork 16
  | |
  4 Cherry 5 8 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 2 AND 11; 这个查询得到了以下的结果。
  
  
  +------------+-----+-----+
  | name | lft | rgt |
  +------------+-----+-----+
  | Fruit | 2 | 11 |
  | Red | 3 | 6 |
  | Cherry | 4 | 5 |
  | Yellow | 7 | 10 |
  | Banana | 8 | 9 |
  +------------+-----+-----+
  看到了吧,只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构,我们还需要对这样的查询进行排序。用节点的左值进行排序:
  
  SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
  剩下的问题如何显示层级的缩进了。
  
    function display_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 one
  if (count($right)>0)
  {
  // 检查我们是否应该将节点移出堆栈
  while ($right[count($right)-1]  {
  array_pop($right);
  }
  }
  
  // 缩进显示节点的名称
  echo str_repeat(' ',count($right)).$row['name']."n";
  
  // 将这个节点加入到堆栈中
  $right[] = $row['rgt'];
  }
  }
  ?>
  如果你运行一下以上的函数就会得到和递归函数一样的结果。只是我们的这个新的函数可能会更快一些,因为只有2次数据库查询。 要获知一个节点的路径就更简单了,如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。
  
  SELECT name FROM tree WHERE lft 5 ORDER BY lft ASC;
  这样就会得到以下的结果:
  
  +------------+
  | name |
  +------------+
  | Food |
  | Fruit |
  | Red |
  +------------+
  那么某个节点到底有多少子孙节点呢?很简单,子孙总数=(右值-左值-1)/2 descendants = (right – left - 1) / 2 不相信?自己算一算啦。用这个简单的公式,我们可以很快的算出"Fruit 2-11"节点有4个子孙节点,而"Banana 8-9"节点没有子孙节点,也就是说它不是一个父节点了。
  很神奇吧?虽然我已经多次用过这个方法,但是每次这样做的时候还是感到很神奇。
  
  这的确是个很好的办法,但是有什么办法能够帮我们建立这样有左右值的数据表呢?这里再介绍一个函数给大家,这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。
  
  
    function rebuild_tree($parent, $left) {
  // the right value of this node is the left value + 1
  $right = $left+1;
  
  // get all children of this node
  $result = mysql_query('SELECT name FROM tree '.
  'WHERE parent="'.$parent.'";');
  while ($row = mysql_fetch_array($result)) {
  // recursive execution of this function for each
  // child of this node
  // $right is the current right value, which is
  // incremented by the rebuild_tree function
  $right = rebuild_tree($row['name'], $right);
  }
  
  // we've got the left value, and now that we've processed
  // the children of this node we also know the right value
  mysql_query('UPDATE tree SET lft='.$left.', rgt='.
  $right.' WHERE name="'.$parent.'";');
  
  // return the right value of this node + 1
  return $right+1;
  }
  ?>
  当然这个函数是一个递归函数,我们需要从根节点开始运行这个函数来重建一个带有左右值的树
  
  rebuild_tree('Food',1);
  这个函数看上去有些复杂,但是它的作用和手工对表进行编号一样,就是将立体多层结构的转换成一个带有左右值的数据表。



Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Beste grafische Einstellungen
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. So reparieren Sie Audio, wenn Sie niemanden hören können
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Lösung: Ihre Organisation verlangt von Ihnen, dass Sie Ihre PIN ändern Lösung: Ihre Organisation verlangt von Ihnen, dass Sie Ihre PIN ändern Oct 04, 2023 pm 05:45 PM

Auf dem Anmeldebildschirm wird die Meldung „Ihre Organisation hat Sie gebeten, Ihre PIN zu ändern“ angezeigt. Dies geschieht, wenn das PIN-Ablauflimit auf einem Computer erreicht wird, der organisationsbasierte Kontoeinstellungen verwendet und die Kontrolle über persönliche Geräte hat. Wenn Sie Windows jedoch über ein persönliches Konto einrichten, sollte die Fehlermeldung im Idealfall nicht erscheinen. Obwohl dies nicht immer der Fall ist. Die meisten Benutzer, die auf Fehler stoßen, melden dies über ihre persönlichen Konten. Warum fordert mich meine Organisation auf, meine PIN unter Windows 11 zu ändern? Es ist möglich, dass Ihr Konto mit einer Organisation verknüpft ist. Ihr primärer Ansatz sollte darin bestehen, dies zu überprüfen. Die Kontaktaufnahme mit Ihrem Domain-Administrator kann hilfreich sein! Darüber hinaus können falsch konfigurierte lokale Richtlinieneinstellungen oder falsche Registrierungsschlüssel Fehler verursachen. Im Augenblick

So passen Sie die Fensterrahmeneinstellungen unter Windows 11 an: Farbe und Größe ändern So passen Sie die Fensterrahmeneinstellungen unter Windows 11 an: Farbe und Größe ändern Sep 22, 2023 am 11:37 AM

Windows 11 bringt frisches und elegantes Design in den Vordergrund; die moderne Benutzeroberfläche ermöglicht es Ihnen, feinste Details, wie zum Beispiel Fensterränder, zu personalisieren und zu ändern. In diesem Leitfaden besprechen wir Schritt-für-Schritt-Anleitungen, die Ihnen dabei helfen, eine Umgebung zu erstellen, die Ihrem Stil im Windows-Betriebssystem entspricht. Wie ändere ich die Fensterrahmeneinstellungen? Drücken Sie +, um die Einstellungen-App zu öffnen. WindowsIch gehe zu Personalisierung und klicke auf Farbeinstellungen. Farbänderung Fensterränder Einstellungen Fenster 11" Breite="643" Höhe="500" > Suchen Sie die Option Akzentfarbe auf Titelleiste und Fensterrändern anzeigen und schalten Sie den Schalter daneben um. Um Akzentfarben im Startmenü und in der Taskleiste anzuzeigen Um die Designfarbe im Startmenü und in der Taskleiste anzuzeigen, aktivieren Sie „Design im Startmenü und in der Taskleiste anzeigen“.

Wie ändere ich die Farbe der Titelleiste unter Windows 11? Wie ändere ich die Farbe der Titelleiste unter Windows 11? Sep 14, 2023 pm 03:33 PM

Standardmäßig hängt die Farbe der Titelleiste unter Windows 11 vom gewählten Dunkel-/Hell-Design ab. Sie können es jedoch in jede gewünschte Farbe ändern. In diesem Leitfaden besprechen wir Schritt-für-Schritt-Anleitungen für drei Möglichkeiten, wie Sie Ihr Desktop-Erlebnis ändern und personalisieren können, um es optisch ansprechend zu gestalten. Ist es möglich, die Farbe der Titelleiste von aktiven und inaktiven Fenstern zu ändern? Ja, Sie können die Farbe der Titelleiste aktiver Fenster mit der App „Einstellungen“ ändern, oder Sie können die Farbe der Titelleiste inaktiver Fenster mit dem Registrierungseditor ändern. Um diese Schritte zu lernen, fahren Sie mit dem nächsten Abschnitt fort. Wie ändere ich die Farbe der Titelleiste in Windows 11? 1. Drücken Sie in der App „Einstellungen“ +, um das Einstellungsfenster zu öffnen. WindowsIch gehe zu „Personalisierung“ und dann

OOBELANGUAGE-Fehlerprobleme bei der Reparatur von Windows 11/10 OOBELANGUAGE-Fehlerprobleme bei der Reparatur von Windows 11/10 Jul 16, 2023 pm 03:29 PM

Wird auf der Windows Installer-Seite „Ein Problem ist aufgetreten“ zusammen mit der Anweisung „OOBELANGUAGE“ angezeigt? Aufgrund solcher Fehler bricht die Installation von Windows manchmal ab. OOBE bedeutet Out-of-the-Box-Erlebnis. Wie aus der Fehlermeldung hervorgeht, handelt es sich hierbei um ein Problem im Zusammenhang mit der OOBE-Sprachauswahl. Sie müssen sich keine Sorgen machen, Sie können dieses Problem durch eine geschickte Bearbeitung der Registrierung über den OOBE-Bildschirm selbst lösen. Schnelllösung – 1. Klicken Sie unten in der OOBE-App auf die Schaltfläche „Wiederholen“. Dadurch wird der Prozess ohne weitere Probleme fortgesetzt. 2. Verwenden Sie den Netzschalter, um das Herunterfahren des Systems zu erzwingen. Nach dem Neustart des Systems sollte OOBE fortgesetzt werden. 3. Trennen Sie das System vom Internet. Schließen Sie alle Aspekte von OOBE im Offline-Modus ab

So aktivieren oder deaktivieren Sie die Vorschau von Miniaturansichten in der Taskleiste unter Windows 11 So aktivieren oder deaktivieren Sie die Vorschau von Miniaturansichten in der Taskleiste unter Windows 11 Sep 15, 2023 pm 03:57 PM

Miniaturansichten in der Taskleiste können Spaß machen, aber auch ablenken oder stören. Wenn man bedenkt, wie oft Sie mit der Maus über diesen Bereich fahren, haben Sie möglicherweise ein paar Mal versehentlich wichtige Fenster geschlossen. Ein weiterer Nachteil besteht darin, dass es mehr Systemressourcen verbraucht. Wenn Sie also nach einer Möglichkeit suchen, ressourceneffizienter zu arbeiten, zeigen wir Ihnen, wie Sie es deaktivieren können. Wenn Ihre Hardware-Spezifikationen jedoch dafür geeignet sind und Ihnen die Vorschau gefällt, können Sie sie aktivieren. Wie aktiviere ich die Miniaturvorschau der Taskleiste in Windows 11? 1. Tippen Sie in der App „Einstellungen“ auf die Taste und klicken Sie auf „Einstellungen“. Klicken Sie unter Windows auf „System“ und wählen Sie „Info“. Klicken Sie auf Erweiterte Systemeinstellungen. Navigieren Sie zur Registerkarte „Erweitert“ und wählen Sie unter „Leistung“ die Option „Einstellungen“ aus. Wählen Sie „Visuelle Effekte“

Anleitung zur Anzeigeskalierung unter Windows 11 Anleitung zur Anzeigeskalierung unter Windows 11 Sep 19, 2023 pm 06:45 PM

Wir alle haben unterschiedliche Vorlieben, wenn es um die Anzeigeskalierung unter Windows 11 geht. Manche Leute mögen große Symbole, andere mögen kleine Symbole. Wir sind uns jedoch alle einig, dass die richtige Skalierung wichtig ist. Eine schlechte Schriftartenskalierung oder eine Überskalierung von Bildern kann bei der Arbeit ein echter Produktivitätskiller sein. Sie müssen daher wissen, wie Sie sie anpassen können, um die Fähigkeiten Ihres Systems optimal zu nutzen. Vorteile des benutzerdefinierten Zooms: Dies ist eine nützliche Funktion für Personen, die Schwierigkeiten haben, Text auf dem Bildschirm zu lesen. Es hilft Ihnen, mehr gleichzeitig auf dem Bildschirm zu sehen. Sie können benutzerdefinierte Erweiterungsprofile erstellen, die nur für bestimmte Monitore und Anwendungen gelten. Kann dazu beitragen, die Leistung von Low-End-Hardware zu verbessern. Dadurch haben Sie mehr Kontrolle darüber, was auf Ihrem Bildschirm angezeigt wird. So verwenden Sie Windows 11

10 Möglichkeiten, die Helligkeit unter Windows 11 anzupassen 10 Möglichkeiten, die Helligkeit unter Windows 11 anzupassen Dec 18, 2023 pm 02:21 PM

Die Bildschirmhelligkeit ist ein wesentlicher Bestandteil der Nutzung moderner Computergeräte, insbesondere wenn Sie über einen längeren Zeitraum auf den Bildschirm schauen. Es hilft Ihnen, die Belastung Ihrer Augen zu reduzieren, die Lesbarkeit zu verbessern und Inhalte einfach und effizient anzuzeigen. Abhängig von Ihren Einstellungen kann es jedoch manchmal schwierig sein, die Helligkeit zu verwalten, insbesondere unter Windows 11 mit den neuen Änderungen an der Benutzeroberfläche. Wenn Sie Probleme beim Anpassen der Helligkeit haben, finden Sie hier alle Möglichkeiten, die Helligkeit unter Windows 11 zu verwalten. So ändern Sie die Helligkeit unter Windows 11 [10 Möglichkeiten erklärt] Benutzer eines einzelnen Monitors können die folgenden Methoden verwenden, um die Helligkeit unter Windows 11 anzupassen. Hierzu zählen sowohl Desktop-Systeme mit einem einzelnen Monitor als auch Laptops. Lasst uns beginnen. Methode 1: Verwenden Sie das Action Center. Das Action Center ist zugänglich

So beheben Sie den Aktivierungsfehlercode 0xc004f069 in Windows Server So beheben Sie den Aktivierungsfehlercode 0xc004f069 in Windows Server Jul 22, 2023 am 09:49 AM

Der Aktivierungsprozess unter Windows nimmt manchmal eine plötzliche Wendung und zeigt eine Fehlermeldung mit diesem Fehlercode 0xc004f069 an. Obwohl der Aktivierungsprozess online erfolgt, kann dieses Problem bei einigen älteren Systemen mit Windows Server auftreten. Führen Sie diese ersten Prüfungen durch. Wenn sie Ihnen bei der Aktivierung Ihres Systems nicht weiterhelfen, fahren Sie mit der Hauptlösung fort, um das Problem zu beheben. Problemumgehung – Schließen Sie die Fehlermeldung und das Aktivierungsfenster. Starten Sie dann Ihren Computer neu. Wiederholen Sie den Windows-Aktivierungsprozess noch einmal von Grund auf. Fix 1 – Aktivierung über das Terminal. Aktivieren Sie das Windows Server Edition-System über das CMD-Terminal. Stufe – 1 Überprüfen Sie die Windows Server-Version. Sie müssen überprüfen, welchen W-Typ Sie verwenden

See all articles