Heim > Artikel > Backend-Entwicklung > 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:
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!