Algorithme d'arbre binaire en PHP et FAQ

Avec le développement continu du développement Web, PHP, en tant que langage de script serveur largement utilisé, ses algorithmes et ses structures de données deviennent de plus en plus importants. Parmi ces algorithmes et structures de données, l’algorithme de l’arbre binaire est un concept très important. Cet article présentera l'algorithme de l'arbre binaire et ses applications en PHP, ainsi que les réponses aux questions courantes.

Qu'est-ce qu'un arbre binaire ?

Un arbre binaire est une structure arborescente dans laquelle chaque nœud a au plus deux nœuds enfants, à savoir le nœud enfant gauche et le nœud enfant droit. Si un nœud n’a pas de nœuds enfants, il est appelé nœud feuille. Les arbres binaires sont couramment utilisés dans les algorithmes de recherche et de tri.

En PHP, vous pouvez utiliser des classes pour implémenter des arbres binaires. Voici un exemple de classe de nœud d'arbre binaire :

class TreeNode {
  public $val;
  public $left;
  public $right;

  function __construct($val) {
    $this->val = $val;
    $this->left = null;
    $this->right = null;
  }
}

Dans cette classe TreeNode, $val représente la valeur du nœud, $left et $right représentent respectivement le nœud enfant gauche et le nœud enfant droit du nœud.

Comment construire un arbre binaire ?

En PHP, vous pouvez construire un arbre binaire simple en suivant le code :

$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
$root->left->left = new TreeNode(4);
$root->left->right = new TreeNode(5);

Cela créera un arbre binaire dont le nœud racine a une valeur de 1, son nœud enfant gauche a une valeur de 2 et son nœud enfant droit a une valeur de 3. La valeur du nœud enfant gauche de son nœud enfant gauche est 4 et la valeur du nœud enfant droit de son nœud enfant gauche est 5.

Comment parcourir un arbre binaire ?

Il existe généralement trois façons de parcourir un arbre binaire : le parcours pré-ordre, le parcours dans l'ordre et le parcours post-ordre.

La traversée de précommande fait référence à la visite d'abord du nœud racine, puis à la traversée du sous-arbre gauche et du sous-arbre droit. En PHP, le parcours en pré-ordre peut être implémenté via le code suivant :

function preorderTraversal($root) {
  if ($root == null) {
    return;
  }
  echo $root->val . " ";
  preorderTraversal($root->left);
  preorderTraversal($root->right);
}

Le parcours dans l'ordre signifie d'abord traverser le sous-arbre de gauche, puis visiter le nœud racine et enfin traverser le sous-arbre de droite. En PHP, le parcours dans l'ordre peut être réalisé via le code suivant :

function inorderTraversal($root) {
  if ($root == null) {
    return;
  }
  inorderTraversal($root->left);
  echo $root->val . " ";
  inorderTraversal($root->right);
}

Le parcours post-ordre signifie d'abord traverser le sous-arbre gauche et le sous-arbre droit, puis visiter le nœud racine. En PHP, le parcours post-ordre peut être réalisé grâce au code suivant :

function postorderTraversal($root) {
  if ($root == null) {
    return;
  }
  postorderTraversal($root->left);
  postorderTraversal($root->right);
  echo $root->val . " ";
}

Comment trouver des nœuds dans un arbre binaire ?

Pour trouver des nœuds dans un arbre binaire, vous pouvez utiliser un algorithme récursif. Voici un exemple de code :

function search($root, $val) {
  if ($root == null || $root->val == $val) {
    return $root;
  }
  if ($val < $root->val) {
    return search($root->left, $val);
  }
  return search($root->right, $val);
}

Dans ce code, si la valeur du nœud est égale à $val, alors le nœud est renvoyé. Sinon, si $val est inférieur à la valeur du nœud, recherchez dans le sous-arbre de gauche. Sinon, recherchez dans le sous-arbre de droite.

Comment insérer un nœud dans un arbre binaire ?

Pour insérer un nœud dans un arbre binaire, vous pouvez utiliser un algorithme récursif. Voici un exemple de code :

function insert($root, $val) {
  if ($root == null) {
    return new TreeNode($val);
  }
  if ($val < $root->val) {
    $root->left = insert($root->left, $val);
  } else {
    $root->right = insert($root->right, $val);
  }
  return $root;
}

Dans ce code, si l'arbre binaire est vide, un nouveau nœud est renvoyé. Sinon, si $val est inférieur à la valeur du nœud, insérez-le dans le sous-arbre de gauche. Sinon, insérez dans le sous-arbre de droite.

Comment supprimer des nœuds dans un arbre binaire ?

Pour supprimer un nœud dans un arbre binaire, vous devez considérer les trois situations suivantes :

1. Le nœud à supprimer n'a pas de nœud enfant, il vous suffit de supprimer le nœud directement.
2. Le nœud à supprimer a un nœud enfant, qui doit être utilisé pour remplacer le nœud.
3. Le nœud à supprimer a deux nœuds enfants. Vous devez trouver le nœud successeur du nœud (c'est-à-dire le plus petit nœud dans le sous-arbre droit du nœud), remplacer le nœud par le nœud successeur, puis supprimer le nœud. nœud successeur.

Ce qui suit est un exemple de code :

function deleteNode($root, $val) {
  if ($root == null) {
    return null;
  }
  if ($val < $root->val) {
    $root->left = deleteNode($root->left, $val);
  } else if ($val > $root->val) {
    $root->right = deleteNode($root->right, $val);
  } else {
    if ($root->left == null) {
      return $root->right;
    } else if ($root->right == null) {
      return $root->left;
    }
    $successor = $root->right;
    while ($successor->left != null) {
      $successor = $successor->left;
    }
    $root->val = $successor->val;
    $root->right = deleteNode($root->right, $successor->val);
  }
  return $root;
}

Conclusion

L'algorithme de l'arbre binaire est un concept très important en PHP. Grâce à des algorithmes récursifs, diverses fonctions telles que la construction d'arbres binaires, le parcours, la recherche de nœuds, l'insertion de nœuds et la suppression de nœuds peuvent être réalisées. Comprendre ces applications est très utile pour développer des applications Web efficaces.

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!