Comment implémenter l'impression séquentielle d'arbres binaires en PHP

Cet article présente principalement la méthode d'impression des arbres binaires en zigzag en PHP, et implique les compétences opérationnelles associées de PHP combinées à la traversée de pile d'arbres binaires. Les amis qui en ont besoin pourront s'y référer. .

Question

Veuillez implémenter une fonction pour imprimer l'arbre binaire en zigzag, c'est-à-dire que la première ligne est imprimée dans l'ordre de de gauche à droite, et la deuxième ligne est imprimée de gauche à droite, les calques sont imprimés de droite à gauche, la troisième ligne est imprimée de gauche à droite, et ainsi de suite pour les autres lignes.

Solution

Utiliser deux piles

Code d'implémentation

<?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;
}

Recommandations associées :

Exemples d'implémentation PHP de parcours d'arbres binaires en pré-commande, dans l'ordre et après-commande

Comment utiliser PHP pour déterminer si un arbre binaire est symétrique ?

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!