Rufen Sie alle Knoten in einem Baum, der Kinder eines anderen sind

StackOverflow https://stackoverflow.com/questions/79041

  •  09-06-2019
  •  | 
  •  

Frage

Ich habe ein Web-System, das ein klassisches Eltern-Kinder-Menü in einer Datenbank mit Feldern ID als PK und parent_id zu zeigen auf das besitzende Menü gespeichert hat. (Ja, ich weiß, das ist nicht sehr gut skalieren, aber das ist ein anderes Thema).

Also für diese Datensätze (id-parent_id Paare): 

0-7 0-4 4-9 4-14 4-16 9-6

Ich habe diesen Baum: 

0
├ 7
└ 4
  ├ 9
  | └ 6     
  ├ 14
  └ 16

Ich bin um einen Top-Knoten zu verbergen, so muss ich eine Liste aller Kinder dieser bestimmten Knoten machen, das heißt für 4, werden sie (9, 6, 14, 16) sein. Bestellen Sie macht die Sache nicht.

Ich bin verwirrt ... nicht passt dies in den klassischen Baum Probleme? oder ist es ein Diagramm, das ein?

Wie kann ich diese Struktur zusammensetzen und dieses Problem mit PHP lösen?

War es hilfreich?

Lösung

Dies ist die perfekte Möglichkeit, Rekursion zu verwenden!

Pseudo-Code: 

nodeList = {}
enumerateNodes(rootNode, nodeList);

function enumerateNodes(node, nodeList) {
   nodeList += node;
   foreach ( childnode in node.children ) {
       enumerateNodes(childnode, nodeList);
   }
}

Edit: Haben Sie nicht bemerken, dass Ihr Baum in der nebenstehenden Liste Format. Ich würde wahrscheinlich nur bauen, dass in eine tatsächlichen Baum Datenstruktur, bevor ich mit ihm zu arbeiten begann. Gerade Schleife durch alle Paare (Knoten das erste Mal, sie sehen zu schaffen) und deren Verknüpfung. I denken es sollte einfach ...

Andere Tipps

Neben Liste Modelle sind sehr schwer zu behandeln. Die Firma, die ich mit jetzt bin nutzt sie für Hierarchien und es verursacht große Kopfschmerzen. Ich habe erfolgreich Celko der verschachtelten Satz Modelle für frühere Arbeitgeber verwendet und sie arbeiten sehr für die Erstellung, Pflege und Verwendung von Hierarchien (Bäume).

ich diesen Link gefunden, die sie beschreibt: http://www.intelligententerprise.com/001020 /celko.jhtml

Aber ich würde auch das Buch „SQL für Smarties: Erweiterte SQL Programming“ empfehlen geschrieben von Joe Celko und deckt verschachtelte Sätze.

Joe Celko SQL für Smarties: Erweiterte SQL Programming

Joe Celko der Bäume und Hierarchien in SQL für Smarties

Dies ist ein Diagramm Problem. Schauen Sie sich BFS (Breitensuche) und DFS (Tiefensuche). . Sie können diese Begriffe google und Hunderte von Implementierungen im Web finden.

Dies ist trivial mit einer verschachtelten Satz Implementierung. Sehen Sie hier für weitere Informationen:

http://mikehillyer.com/articles/managing-hierarchical- data-in-mysql /

Ansonsten schreiben Sie etwas wie folgt aus: 

def get_subtree(node)
  if children.size > 0
    return children.collect { |n| get_subtree(n) }
  else
    return node
  end
end
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top