Beispiele für die Implementierung von Vorbestellungs-, In-Order- und Post-Order-Traversal-Binärbaumoperationen durch PHP basierend auf nicht-rekursiven Algorithmen

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. Für die Prinzipien und spezifischen Implementierungstechniken können sich Freunde mit Bedarf auf

beziehen. Dieser Artikel beschreibt das zu implementierende Beispiel von PHP, das auf einem nicht rekursiven Algorithmus basiert Vorbestellungs-, In-Order- und Post-Order-Traversal-Binärbaumoperationen. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Übersicht:

Das Prinzip der Binärbaumdurchquerung ist wie folgt:

Durchquerung des oben gezeigten Binärbaums:

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

ABDHECFG

2. Durchqueren der Reihenfolge : Durchqueren Sie zuerst den linken Teilbaum, dann den Wurzelknoten und schließlich den rechten Teilbaum.

HDBEAFCG

3. Durchquerung nach der Bestellung : Durchqueren Sie zuerst den linken Teilbaum, dann den rechten Teilbaum und schließlich den Wurzelknoten.

HDEBFGCA

Implementierungsmethode:

Vorbestellungsdurchlauf: Stack zuerst und zuletzt verwenden out Features: Besuchen Sie zuerst den Wurzelknoten, schieben Sie dann den rechten Teilbaum und 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); // 压入左子树
 }
}

In der Reihenfolge: muss von unten nach oben durchlaufen werden, also schieben Sie zuerst den linken Teilbaum auf den Stapel und dann Besuchen Sie nacheinander die Wurzelknoten und die Knoten des rechten Teilbaums.

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;
 }
}

Nachbestellung: Speichern Sie zuerst den Wurzelknoten und dann den linken Teilbaum und den rechten Teilbaum der Reihe nach. 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;
 }
}

Artikel, die Sie interessieren könnten:

PHP verwendet zwei Stacks, um die Warteschlangenfunktion zu implementieren Erläuterung der Methoden

Detaillierte Erläuterung der PHP-Serialisierungs- und Deserialisierungsprinzipien

WeChat-Code-Scanning basierend auf Swoole Erläuterung der Prozess der Implementierung des Codes für die Anmeldefunktion

Das obige ist der detaillierte Inhalt vonBeispiele für die Implementierung von Vorbestellungs-, In-Order- und Post-Order-Traversal-Binärbaumoperationen durch PHP basierend auf nicht-rekursiven Algorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!