PHP explique comment imprimer des arbres binaires en zigzag

Cet article présente principalement la méthode PHP pour réaliser l'impression d'arbres binaires dans l'ordre zigzag, impliquant les compétences opérationnelles associées de PHP combinées à la traversée de pile d'arbres binaires. Les amis dans le besoin peuvent s'y référer

L'exemple. de cet article raconte l'implémentation PHP de l'impression d'arbres binaires en ordre zigzag. Une méthode pour imprimer un arbre binaire en ordre zigzag. Partagez-le avec tout le monde pour votre référence, comme suit :

Question

Veuillez implémenter une fonction pour imprimer l'arbre binaire dans un motif en zigzag, c'est-à-dire que la première ligne est la suivante : Imprimez de gauche à droite, le deuxième calque s'imprime de droite à gauche, la troisième ligne s'imprime 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;
}

Articles qui pourraient vous intéresser :

Explication de comment obtenir une image d'arbre binaire avec PHP

Explication de comment obtenir le Kème nœud du dernier dans une liste chaînée avec PHP

PHP imprime un arbre binaire de haut en bas Explication de la méthode

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!