Exemples de PHP implémentant des opérations d'arbre binaire de traversée de pré-ordre, dans l'ordre et après-ordre basées sur des algorithmes non récursifs

Cet article présente principalement PHP pour implémenter des opérations de parcours de pré-ordre, dans l'ordre et après-ordre sur des arbres binaires basées sur des algorithmes non récursifs. Il analyse l'utilisation d'algorithmes non récursifs pour effectuer des pré-ordres, dans-. Opérations de parcours d'ordre et de post-ordre sur des arbres binaires en combinaison avec des exemples Pour les principes et les techniques d'implémentation spécifiques, les amis dans le besoin peuvent se référer à

Cet article décrit l'exemple de PHP basé sur un algorithme non récursif à implémenter. opérations d'arbre binaire de traversée de pré-ordre, dans l'ordre et après-ordre. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Aperçu :

Le principe de la traversée d'un arbre binaire est le suivant :

Traversée de l'arbre binaire illustré ci-dessus :

1. Traversée de précommande  : Traversez d'abord le nœud racine, puis traversez la gauche. sous-arbre, et enfin traverser le sous-arbre droit.

ABDHECFG

2. Traversée dans l'ordre  : Traversez d'abord le sous-arbre de gauche, puis traversez le nœud racine et enfin traversez le sous-arbre de droite.

HDBEAFCG

3. Traversée post-commande  : parcourez d'abord le sous-arbre de gauche, puis le sous-arbre de droite et enfin le nœud racine.

HDEBFGCA

Méthode de mise en œuvre :

Parcours de précommande : Utiliser la pile en premier en dernier out Caractéristiques : visitez d'abord le nœud racine, puis poussez le sous-arbre droit, puis poussez le sous-arbre gauche. Lors de sa suppression de cette manière, le sous-arbre de gauche est supprimé en premier et le sous-arbre de droite est supprimé en dernier.

function preorder($root){
 $stack = array();
 array_push($stack, $root);
 while(!empty($stack)){
  $center_node = array_pop($stack);
  echo $center_node->value; // 根节点
  if($center_node->right != null)
   array_push($stack, $center_node->right); // 压入右子树
  if($center_node->left != null)
   array_push($stack, $center_node->left); // 压入左子树
 }
}

Dans l'ordre : doit être parcouru de bas en haut, alors poussez d'abord le sous-arbre de gauche sur la pile, puis visitez la racine un par un nœud et le sous-arbre droit.

function inorder($root){
 $stack = array();
 $center_node = $root;
 while(!empty($stack) || $center_node != null){
  while($center_node != null){
   array_push($stack, $center_node);
   $center_node = $center_node->left;
  }
  $center_node = array_pop($stack);
  echo $center_node->value;
  $center_node = $center_node->right;
 }
}

Post-commande : Enregistrez d'abord le nœud racine, puis stockez le sous-arbre gauche et le sous-arbre droit dans l'ordre. Puis sortie.

function tailorder($root){
 $stack = array();
 $outstack = array();
 array_push($$stack, $root);
 while($empty($stack)){
  $center_node = array_pop($stack);
  array_push($outstack, $center_node);
  if($center_node->right != null)
   array_push($stack, $center_node->right);
  if($center_node->left != null)
   array_push($stack, $center_node->left);
 }
 while($empty($outstack)){
  $center_node = array_pop($outstack);
  echo $center_node->value;
 }
}

Articles qui pourraient vous intéresser :

PHP utilise deux piles pour implémenter des files d'attente Explication des méthodes fonctionnelles

Explication détaillée des principes de sérialisation et de désérialisation PHP

WeChat basé sur Swoole Explication du processus de mise en œuvre du code en scannant le code QR pour vous connecter

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!