PHP implémente des exemples d'opérations d'arbre binaire de traversée en pré-ordre, dans l'ordre et après l'ordre

Cet article présente principalement PHP pour implémenter des opérations de parcours de pré-ordre, dans l'ordre et post-ordre sur des arbres binaires basées sur des algorithmes non récursifs. Il analyse le principe de PHP utilisant des algorithmes non récursifs pour effectuer la pré-commande, Opérations de parcours dans l'ordre et après l'ordre sur des arbres binaires basées sur des exemples. Les amis qui en ont besoin peuvent se référer aux techniques d'implémentation spécifiques. J'espère que cela pourra aider tout le monde.

Aperçu :

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

Pour la traversée de l'arbre binaire illustré dans la figure ci-dessus :

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

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 parcourez le sous-arbre de droite et enfin parcourez le nœud racine.

HDEBFGCA

Méthode d'implémentation :

Parcours de précommande : en utilisant la fonctionnalité premier entré, dernier sorti de la pile, 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 : il 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;
 }
}

Recommandations associées :

Comment déterminer si un arbre binaire est symétrique en PHP

JavaScript Implémentation de méthodes de traversée en pré-ordre, dans l'ordre et après-ordre des arbres binaires

Explication détaillée de l'exemple de code de l'algorithme de traversée d'arbre binaire implémenté en PHP

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!