Heim  >  Artikel  >  Backend-Entwicklung  >  So implementieren Sie das sequentielle Drucken von Binärbäumen in PHP

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

小云云
小云云Original
2018-01-16 16:36:531323Durchsuche

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!

Stellungnahme:
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