Detaillierte Erläuterung der Schritte des Binärbaum-Tiefen- und Breiten-First-Traversal-Algorithmus in PHP-PHP-Tutorial-php.cn

Dieses Mal werde ich Ihnen eine detaillierte Erklärung der Algorithmusschritte zum Implementieren der Tiefen- und Breiten-First-Traversierung von Binärbäumen in PHP geben. Was sind die Vorsichtsmaßnahmen für die Implementierung der Tiefen- und Breiten-First-Traversierung von Binärbäumen? Hier sind praktische Fälle.

Vorwort:

Tiefendurchquerung: Gehen Sie tief in jeden möglichen Zweigpfad hinein, bis es nicht mehr geht tiefer. 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.&#39; &#39;;
    //      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 . &#39; &#39;;
        $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);
}

Nach dem Login kopieren

Erklärung: 1. Ich werde alle durchqueren Methoden sind alle in einem Klassendurchlauf 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 <a href="http://www.php" verwenden. cn/wiki/1001.html" target="_blank">array_push<code><a href="//m.sbmmt.com/wiki/1001.html" target="_blank">array_push</a>() () und array_pop() Simulationsimplementierung.

2. Durchquerung 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 . &#39; &#39;;
      $node = $node->right;
    }
}
//中序遍历
public function MidOrder()
{
    //    $this->mid_order1($this->tree->root);
    $this->mid_order2($this->tree->root);
}

Nach dem Login kopieren

3. Durchquerung nach der Reihenfolge:

/**
* 后序遍历(递归方法)
*/
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.&#39; &#39;;
        $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);
}

Nach dem Login kopieren

Breite-zuerst-Durchquerung:

1. Level-Traversal:

/**
* 层次遍历(递归方法)
* 由于是按层逐层遍历，因此传递树的层数
*/
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;
}

Nach dem Login kopieren

Hinweis: Bei der Verwendung der Warteschlange verwende ich die von der PHP-Standardbibliothek SPL bereitgestellte splqueue, wenn Sie es gewohnt sind, Arrays zu verwenden , können Sie mit array_push() und array_shift() die Implementierung simulieren.

Verwendung:

Schauen wir uns nun den Client-Code an:

class Client
{
  public static function Main()
  {
    try {
      //实现文件的自动加载
      function autoload($class)
      {
        include strtolower($class) . &#39;.php&#39;;
      }
      spl_autoload_register(&#39;autoload&#39;);
      $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();

Nach dem Login kopieren

Ergänzung:

1. Die drei im Client verwendeten Klassen Bst, Avl und Rbt finden Sie im vorherigen Artikel: „Detaillierte Erläuterung der grafischen Anzeigefunktion zum Zeichnen von Binärbäumen“.

2. Warum empfehle ich jedem, splstack und splqueue zu verwenden, die in der SPL-Standardbibliothek enthalten sind? 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 (array_pop(), array_push()). 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

Ich glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Für weitere spannende Inhalte achten Sie bitte auf andere verwandte Artikel auf der chinesischen PHP-Website!

Empfohlene Lektüre:

Ausführliche Erläuterung des einfachen PHP-Auswahlsortierfalls

Ausführliche Erläuterung der Schritte zur Implementierung der Huffman-Codierung /Dekodierung in PHP

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Schritte des Binärbaum-Tiefen- und Breiten-First-Traversal-Algorithmus in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!