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

jacklove
Freigeben: 2023-04-02 08:02:02
Original
2824 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. 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); // 压入左子树
 }
}
Nach dem Login kopieren

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;
 }
}
Nach dem Login kopieren

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;
 }
}
Nach dem Login kopieren

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!

Verwandte Etiketten:
php
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