PHP implementiert die Tiefendurchquerung (Pre-Order, Mid-Order, Post-Order) und die Breiten-First-Durchquerung (Ebene) von Binärbäumen

In diesem Artikel wird hauptsächlich die Implementierung der Tiefendurchquerung (Vorbestellung, In-Reihenfolge, Nachbestellung) und der Breitendurchquerung (Ebene) von Binärbäumen vorgestellt. Er analysiert detailliert die Tiefendurchquerung von PHP und Breiten-First-Durchquerung von Binärbäumen in Form von Beispielen. Freunde in Not können sich auf

beziehen. Dieser Artikel beschreibt die Implementierung der Tiefen-First-Durchquerung (Vorbestellung, Mitte). Reihenfolge, Nachbestellung) und Breiten-zuerst-Traversierung (Ebene) eines Binärbaums in PHP. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Vorwort:

Tiefendurchquerung : für jede Möglichkeit Der Verzweigungspfad geht so tief, dass er nicht weiter gehen kann, und jeder Knoten kann nur einmal besucht werden. Es ist wichtig zu beachten, dass die Tiefendurchquerung von Binärbäumen etwas Besonderes ist und in Durchquerung vor der Bestellung, Durchquerung in der Reihenfolge und Durchquerung nach der Bestellung unterteilt werden kann. Die spezifischen Anweisungen lauten wie folgt:

Durchquerung vor der Bestellung: Wurzelknoten->linker Teilbaum->rechter Teilbaum
Durchquerung in der Reihenfolge: linker Teilbaum->Wurzelknoten->rechter Teilbaum
Post-Order-Durchquerung: linker Teilbaum->rechter Teilbaum->Wurzelknoten

Breite-zuerst-Durchquerung: Auch hierarchische Durchquerung genannt, jede Ebene wird von oben nach unten sequenziert Greifen Sie in jeder Ebene auf Knoten von links nach rechts (oder von rechts nach links) zu. Gehen Sie nach dem Zugriff auf eine Ebene zur nächsten Ebene, bis keine Knoten mehr erreichbar sind.

Zum Beispiel für diesen Baum:

Tiefendurchquerung:

Vorbestellungsdurchquerung: 10 8 7 9 12 11 13
Durchquerung in der Reihenfolge: 7 8 9 10 11 12 13
Durchquerung nach der Reihenfolge: 7 9 8 11 13 12 10

Durchquerung in der Breite zuerst:

Ebenendurchquerung: 10 8 12 7 9 11 13

Die übliche nichtrekursive Methode für die Tiefendurchquerung eines Binärbaums ist die Verwendung eines Stapels, und die übliche Methode für Bei der nicht rekursiven Breitendurchquerung wird eine Warteschlange verwendet.

Tiefendurchquerung:

1. Vorbestellungsdurchquerung:

/**
* 前序遍历(递归方法)
*/
private function pre_order1($root)
{
    if (!is_null($root)) {
      //这里用到常量__FUNCTION__，获取当前函数名，好处是假如修改函数名的时候，里面的实现不用修改
      $function = __FUNCTION__;
      echo $root->key . " ";
      $this->$function($root->left);
      $this->$function($root->right);
    }
}
/**
* 前序遍历(非递归方法)
* 因为当遍历过根节点之后还要回来，所以必须将其存起来。考虑到后进先出的特点，选用栈存储。
*/
private function pre_order2($root)
{
    //    $stack = new splstack();
    //    $stack->push($root);
    //    while(!$stack->isEmpty()){
    //      $node = $stack->pop();
    //      echo $node->key.' ';
    //      if(!is_null($node->right)){
    //        $stack->push($node->right);
    //      }
    //      if(!is_null($node->left)){
    //        $stack->push($node->left);
    //      }
    //    }
    if (is_null($root)) {
      return;
    }
    $stack = new splstack();
    $node = $root;
    while (!is_null($node) || !$stack->isEmpty()) {
      while (!is_null($node)) {
        //只要结点不为空就应该入栈保存，与其左右结点无关
        $stack->push($node);
        echo $node->key . ' ';
        $node = $node->left;
      }
      $node = $stack->pop();
      $node = $node->right;
    }
}
//前序遍历
public function PreOrder()
{
    // 所在对象中的tree属性保存了一个树的引用
    //   $this->pre_order1($this->tree->root);
    $this->pre_order2($this->tree->root);
}

Erklärung: 1. Ich habe alle Traversierungsmethoden in einer Klassentraverse gekapselt. 2. In der pre_order2-Methode verwende ich bei Verwendung des Stapels splstack, der von der PHP-Standardbibliothek SPL bereitgestellt wird. Wenn Sie an die Verwendung von Arrays gewöhnt sind, können Sie array_push() und array_pop() verwenden, um die Implementierung zu simulieren.

2. Durchlauf in der Reihenfolge:

/**
* 中序遍历(递归方法)
*/
private function mid_order1($root)
{
    if (!is_null($root)) {
      $function = __FUNCTION__;
      $this->$function($root->left);
      echo $root->key . " ";
      $this->$function($root->right);
    }
}
/**
* 中序遍历(非递归方法)
* 因为当遍历过根节点之后还要回来，所以必须将其存起来。考虑到后进先出的特点，选用栈存储。
*/
private function mid_order2($root)
{
    if (is_null($root)) {
      return;
    }
    $stack = new splstack();
    $node = $root;
    while (!is_null($node) || !$stack->isEmpty()) {
      while (!is_null($node)) {
        $stack->push($node);
        $node = $node->left;
      }
      $node = $stack->pop();
      echo $node->key . ' ';
      $node = $node->right;
    }
}
//中序遍历
public function MidOrder()
{
    //    $this->mid_order1($this->tree->root);
    $this->mid_order2($this->tree->root);
}

3

/**
* 后序遍历(递归方法)
*/
private function post_order1($root)
{
    if (!is_null($root)) {
      $function = __FUNCTION__;
      $this->$function($root->left);
      $this->$function($root->right);
      echo $root->key . " ";
    }
}
/**
* 后序遍历(非递归方法)
* 因为当遍历过根节点之后还要回来，所以必须将其存起来。考虑到后进先出的特点，选用栈存储。
* 由于在访问了左子节点后怎么跳到右子节点是难点，这里使用一个标识lastVisited来标识上一次访问的结点
*/
private function post_order2($root)
{
    if (is_null($root)) {
      return;
    }
    $node = $root;
    $stack = new splstack();
    //保存上一次访问的结点引用
    $lastVisited = NULL;
    $stack->push($node);
    while(!$stack->isEmpty()){
      $node = $stack->top();//获取栈顶元素但不弹出
      if(($node->left == NULL && $node->right == NULL) || ($node->right == NULL && $lastVisited == $node->left) || ($lastVisited == $node->right)){
        echo $node->key.' ';
        $lastVisited = $node;
        $stack->pop();
      }else{
        if($node->right){
          $stack->push($node->right);
        }
        if($node->left){
          $stack->push($node->left);
        }
      }
    }
}
//后序遍历
public function PostOrder()
{
    //    $this->post_order1($this->tree->root);
    $this->post_order2($this->tree->root);
}

Breite-zuerst-Durchquerung:

1 Durchquerung:

/**
* 层次遍历(递归方法)
* 由于是按层逐层遍历，因此传递树的层数
*/
private function level_order1($root,$level){
    if($root == NULL || $level < 1){
      return;
    }
    if($level == 1){
      echo $root->key.&#39; &#39;;
      return;
    }
    if(!is_null($root->left)){
      $this->level_order1($root->left,$level - 1);
    }
    if(!is_null($root->right)){
      $this->level_order1($root->right,$level - 1);
    }
}
/**
* 层次遍历(非递归方法)
* 每一层从左向右输出
元素需要储存有先进先出的特性，所以选用队列存储。
*/
private function level_order2($root){
    if(is_null($root)){
      return;
    }
    $node = $root;
    //利用队列实现
//    $queue = array();
//    array_push($queue,$node);
//
//    while(!is_null($node = array_shift($queue))){
//      echo $node->key.&#39; &#39;;
//      if(!is_null($node->left)){
//        array_push($queue,$node->left);
//      }
//      if(!is_null($node->right)){
//        array_push($queue,$node->right);
//      }
//    }
    $queue = new splqueue();
    $queue->enqueue($node);
    while(!$queue->isEmpty()){
      $node = $queue->dequeue();
      echo $node->key.&#39; &#39;;
      if (!is_null($node->left)) {
        $queue->enqueue($node->left);
      }
      if (!is_null($node->right)) {
        $queue->enqueue($node->right);
      }
    }
}
//层次遍历
public function LevelOrder(){
//    $level = $this->getdepth($this->tree->root);
//    for($i = 1;$i <= $level;$i ++){
//      $this->level_order1($this->tree->root,$i);
//    }
    $this->level_order2($this->tree->root);
}
//获取树的层数
private function getdepth($root){
    if(is_null($root)){
      return 0;
    }
    $left = getdepth($root -> left);
    $right = getdepth($root -> right);
    $depth = ($left > $right ? $left : $right) + 1;
    return $depth;
}

Hinweis: In der Methode level_order2 verwende ich bei Verwendung der Warteschlange die vom PHP-Standard bereitgestellte splqueue Bibliothek SPL: Wenn Sie mit der Verwendung von Arrays vertraut sind, können Sie

und array_push() verwenden, um die Implementierung zu simulieren. array_shift()

Verwendung:

Schauen wir uns nun den Client-Code an:

class Client
{
  public static function Main()
  {
    try {
      //实现文件的自动加载
      function autoload($class)
      {
        include strtolower($class) . '.php';
      }
      spl_autoload_register('autoload');
      $arr = array(10, 8, 12, 7, 9, 11, 13);
      $tree = new Bst();
//      $tree = new Avl();
//      $tree = new Rbt();
      $tree->init($arr);
      $traverse = new traverse($tree);
      $traverse->PreOrder();
//      $traverse->MidOrder();
//      $traverse->PostOrder();
//      $traverse->LevelOrder();
    } catch (Exception $e) {
      echo $e->getMessage();
    }
  }
}
CLient::Main();

Ergänzung:

1. Die drei im Client verwendeten Klassen Bst, Avl und Rbt können auf Sie verweisen der vorherige Artikel: „Detaillierte Erläuterung der grafischen Anzeigefunktion zum Zeichnen von Binärbäumen in PHP“

2. Warum empfehle ich Ihnen, die in der SPL-Standardbibliothek bereitgestellten

und splstack zu verwenden? Folgendes habe ich in einem Artikel gesehen: Obwohl wir herkömmliche Variablentypen zur Beschreibung von Datenstrukturen verwenden können, beispielsweise Arrays zur Beschreibung von Stapeln (Strack), verwenden wir dann die entsprechenden Methoden pop und push (splqueue, array_pop()). Aber man muss immer vorsichtig sein, denn schließlich sind sie nicht speziell dafür konzipiert, Datenstrukturen zu beschreiben – eine falsche Operation kann den Stapel zerstören. Das SplStack-Objekt von SPL beschreibt Daten streng in Form eines Stapels und stellt entsprechende Methoden bereit. Gleichzeitig sollte ein solcher Code auch verstehen können, dass er auf einem Stapel und nicht auf einem Array ausgeführt wird, sodass Ihre Kollegen den entsprechenden Code besser verstehen können und er schneller ist. Ursprüngliche Adresse: PHP SPL, das verlorene Juwel array_push()

3 Referenzartikel zu diesem Artikel: „Detaillierte Erklärung gängiger Binärbaumoperationen in der C-Sprache [Vorbestellung, Inorder, Postorder, hierarchische Durchquerung und Nicht- rekursive Suche, Anzahl zählen, vergleichen und Tiefe ermitteln]“, „Java-Implementierung von Tiefendurchquerungs- und Breitendurchquerungsalgorithmen – Beispiele für Binärbäume“

Verwandte Empfehlungen:

PHP-Sortieralgorithmus Bubbling Sort (Bubble Sort)

Das obige ist der detaillierte Inhalt vonPHP implementiert die Tiefendurchquerung (Pre-Order, Mid-Order, Post-Order) und die Breiten-First-Durchquerung (Ebene) von Binärbäumen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!