Explication détaillée des étapes pour imprimer un arbre binaire en utilisant l'ordre Zigzag en PHP

Cette fois, je vais vous donner une explication détaillée des étapes pour imprimer un arbre binaire en forme de Z à l'aide de PHP Quelles sont les précautions pour utiliser PHP pour imprimer un arbre binaire en forme de Z. commander Voici un cas pratique, jetons un coup d'oeil.

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

Je pense que vous maîtrisez la méthode après avoir lu le cas dans cet article. Pour des informations plus intéressantes, veuillez prêter attention aux autres articles connexes sur le site Web chinois de php !

Lecture recommandée :

Explication détaillée des étapes pour implémenter la classe de fonctionnement en mode singleton mongoDB en php

Pourquoi il existe une classe PHP SoapClient n'a pas trouvé de problème et sa méthode de solution

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!