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

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); // 压入左子树
 }
}

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

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

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!