PHP implementiert Beispiele für Vorbestellungs-, In-Order- und Post-Order-Traversal-Binärbaumoperationen

小云云
Freigeben: 2023-03-19 14:30:01
Original
2133 Leute haben es durchsucht

In diesem Artikel wird hauptsächlich PHP zur Implementierung von Vorbestellungs-, In-Order- und Post-Order-Traversal-Operationen auf Binärbäumen basierend auf nicht rekursiven Algorithmen vorgestellt. Er analysiert das Prinzip von PHP unter Verwendung nicht rekursiver Algorithmen zur Durchführung von Vorbestellungen. In-Order- und Post-Order-Traversal-Operationen an Binärbäumen anhand von Beispielen. Freunde, die es benötigen, können sich auf die spezifischen Implementierungstechniken beziehen.

Übersicht:

Das Prinzip der Binärbaumdurchquerung lautet wie folgt:

Für die in der obigen Abbildung gezeigte Binärbaumdurchquerung:

1. Durchquerung vorbestellen: Durchqueren Sie zuerst den Wurzelknoten, durchqueren Sie dann den linken Teilbaum und durchqueren Sie schließlich den rechten Teilbaum.

ABDHECFG

2. Durchlaufen der Reihenfolge: Zuerst den linken Teilbaum durchqueren, dann den Wurzelknoten durchqueren und schließlich den rechten Teilbaum durchqueren.

HDBEAFCG

3. Durchqueren Sie zuerst den linken Teilbaum, dann den rechten Teilbaum und schließlich den Wurzelknoten.

HDEBFGCA

Implementierungsmethode:

Vorbestellungsdurchquerung: Verwenden Sie die First-In-Last-Out-Funktion des Stapels, besuchen Sie zuerst den Wurzelknoten und drücken Sie dann den rechten Teilbaum und schieben Sie dann den linken Teilbaum. Bei dieser Methode wird der linke Teilbaum zuerst und der rechte Teilbaum zuletzt entfernt.


function preorder($root){
 $stack = array();
 array_push($stack, $root);
 while(!empty($stack)){
  $center_node = array_pop($stack);
  echo $center_node->value; // 根节点
  if($center_node->right != null)
   array_push($stack, $center_node->right); // 压入右子树
  if($center_node->left != null)
   array_push($stack, $center_node->left); // 压入左子树
 }
}
Nach dem Login kopieren


In der richtigen Reihenfolge: Es muss von unten nach oben durchlaufen werden, also schieben Sie zuerst den linken Teilbaum auf den Stapel Besuchen Sie dann nacheinander den Stammknoten und den rechten Teilbaum.


function inorder($root){
 $stack = array();
 $center_node = $root;
 while(!empty($stack) || $center_node != null){
  while($center_node != null){
   array_push($stack, $center_node);
   $center_node = $center_node->left;
  }
  $center_node = array_pop($stack);
  echo $center_node->value;
  $center_node = $center_node->right;
 }
}
Nach dem Login kopieren


Nachbestellung: Speichern Sie zuerst den Wurzelknoten und dann den linken Teilbaum und den rechten Teilbaum nacheinander. Dann Ausgabe.


function tailorder($root){
 $stack = array();
 $outstack = array();
 array_push($$stack, $root);
 while($empty($stack)){
  $center_node = array_pop($stack);
  array_push($outstack, $center_node);
  if($center_node->right != null)
   array_push($stack, $center_node->right);
  if($center_node->left != null)
   array_push($stack, $center_node->left);
 }
 while($empty($outstack)){
  $center_node = array_pop($outstack);
  echo $center_node->value;
 }
}
Nach dem Login kopieren

Verwandte Empfehlungen:

So ermitteln Sie, ob ein Binärbaum in PHP symmetrisch ist

JavaScript implementiert Pre-Order-, In-Order- und Post-Order-Traversal-Methoden von Binärbäumen

Detaillierte Erläuterung des Beispielcodes des in PHP implementierten Binärbaum-Traversal-Algorithmus

Das obige ist der detaillierte Inhalt vonPHP implementiert Beispiele für Vorbestellungs-, In-Order- und Post-Order-Traversal-Binärbaumoperationen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:php.cn
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
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage
Über uns Haftungsausschluss Sitemap
Chinesische PHP-Website:Online-PHP-Schulung für das Gemeinwohl,Helfen Sie PHP-Lernenden, sich schnell weiterzuentwickeln!