So implementieren Sie das sequentielle Drucken von Binärbäumen in PHP

In diesem Artikel wird hauptsächlich die Methode zum Drucken von Binärbäumen in Zick-Zack-Reihenfolge vorgestellt und die damit verbundenen Betriebsfähigkeiten von PHP in Kombination mit der Stapeldurchquerung von Binärbäumen behandelt. Ich hoffe, es kann jedem helfen .

Frage

Bitte implementieren Sie eine Funktion, um den Binärbaum in einem Zickzackmuster zu drucken, d. h. die erste Zeile wird in der Reihenfolge von gedruckt von links nach rechts, und die zweite Zeile wird in der Reihenfolge von links nach rechts gedruckt. Die Ebenen werden von rechts nach links gedruckt, die dritte Zeile wird von links nach rechts gedruckt und so weiter für die anderen Zeilen.

Lösung

Zwei Stapel verwenden

Implementierungscode

<?php
/*class TreeNode{
  var $val;
  var $left = NULL;
  var $right = NULL;
  function __construct($val){
    $this->val = $val;
  }
}*/
function MyPrint($pRoot)
{
  if($pRoot == NULL)
    return [];
  $current = 0;
  $next  = 1;
  $stack[0] = array();
  $stack[1] = array();
  $resultQueue = array();
  array_push($stack[0], $pRoot);
  $i = 0;
  $result = array();
  $result[0]= array();
  while(!empty($stack[0]) || !empty($stack[1])){
    $node = array_pop($stack[$current]);
    array_push($result[$i], $node->val);
    //var_dump($resultQueue);echo "</br>";
    if($current == 0){
      if($node->left != NULL)
        array_push($stack[$next], $node->left);
      if($node->right != NULL)
        array_push($stack[$next], $node->right);
    }else{
      if($node->right != NULL)
        array_push($stack[$next], $node->right);
      if($node->left != NULL)
        array_push($stack[$next], $node->left);
    }
    if(empty($stack[$current])){
      $current = 1-$current;
      $next  = 1-$next;
      if(!empty($stack[0]) || !empty($stack[1])){
        $i++;
        $result[$i] = array();
      }
    }
  }
  return $result;
}

Verwandte Empfehlungen:

Beispiele für die PHP-Implementierung des Pre-Order-, In-Order- und Post-Order-Traversal von Binärbäumen

Wie kann man mit PHP feststellen, ob ein Binärbaum symmetrisch ist?

Das obige ist der detaillierte Inhalt vonSo implementieren Sie das sequentielle Drucken von Binärbäumen in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!