Comment implémenter un arbre binaire en php (exemple de code)

L'arbre binaire est une structure de données de base en informatique, c'est la structure arborescente la plus courante, telle que celle utilisée en informatique pour la recherche et le tri, et utilisée dans de nombreux autres domaines de l'informatique. PHP est un langage de script côté serveur largement utilisé qui prend en charge le développement Web dynamique. Dans cet article, nous présenterons comment implémenter un arbre binaire en utilisant PHP.

Qu'est-ce qu'un arbre binaire ?

Un arbre binaire est composé de plusieurs nœuds, chaque nœud a au plus deux nœuds enfants. Il possède trois attributs :

• Valeur du nœud
• Pointeur de sous-arbre gauche
• Pointeur de sous-arbre droit

Les arbres binaires sont divisés dans les catégories suivantes :

• Arbre binaire complet : à l'exception des nœuds feuilles, les autres nœuds ont deux nœuds enfants.
• Arbre binaire complet : si la profondeur de l'arbre binaire est d, à l'exception du niveau dième, tous les autres niveaux sont pleins, et au niveau dième, tous les nœuds feuilles sont à des positions consécutives sur la gauche
• Arbre de recherche binaire : sous-arbre gauche Tous les nœuds sont inférieurs à la valeur du nœud racine et toutes les valeurs des nœuds du sous-arbre droit sont supérieures à la valeur du nœud racine

Pour implémenter un arbre binaire

Nous pouvons utiliser des classes pour définir la structure de l'arbre binaire. Chaque nœud est un objet avec les propriétés suivantes :

• value : valeur du nœud
• gauche : pointeur de sous-arbre gauche
• droite : pointeur de sous-arbre droit

Créez une classe pour représenter le nœud.

class Node {
    public $value;
    public $left;
    public $right;
    function __construct($value){
        $this -> value = $value;
        $this -> left = null;
        $this -> right = null;
    }
}

Ensuite, nous devons créer une classe pour représenter l'arbre binaire.

class BinarySearchTree {
    public $root;
    function __construct() {
        $this -> root = null;
    }
}

Ensuite, nous définirons les méthodes suivantes pour les arbres binaires :

• insert(value) : Insérer une valeur dans un arbre binaire
• search(value) : Rechercher une valeur dans un arbre binaire
• delete(value) : Supprimer une valeur d'un arbre binaire

Insérer un nœud

La méthode Insérer un nœud insérera le nouveau nœud au bon emplacement. Si l'arborescence est vide, le nouveau nœud est le nœud racine. Sinon, nous commençons à comparer la valeur du nœud actuel à partir du nœud racine.

• Si la valeur du nouveau nœud est inférieure à la valeur du nœud actuel, alors nous insérons le nouveau nœud dans le sous-arbre de gauche.
• Si la valeur du nouveau nœud est supérieure à la valeur du nœud actuel, alors nous insérons le nouveau nœud dans le sous-arbre de droite.
• Si la valeur du nouveau nœud est égale à la valeur du nœud actuel, le nœud existe déjà et n'a pas besoin d'être inséré.

Voici le code de la méthode d'insertion :

function insert($value) {
    $newNode = new Node($value);
    if ($this -> root == null) {
        $this -> root = $newNode;
    } else {
        $current = $this -> root;
        while (true) {
            if ($value < $current -> value) {
                if ($current -> left == null) {
                    $current -> left = $newNode;
                    return;
                } else {
                    $current = $current -> left;
                }
            } else if ($value > $current -> value) {
                if ($current -> right == null) {
                    $current -> right = $newNode;
                    return;
                } else {
                    $current = $current -> right;
                }
            } else {
                return;
            }
        }
    }
}

Find Node

La méthode Find Node est une méthode récursive simple. Comparez les valeurs des nœuds en commençant par le nœud racine. Si les valeurs sont égales, renvoie le nœud actuel. Sinon, si la valeur du nœud est inférieure à la valeur que vous recherchez, continuez la recherche dans le sous-arbre de gauche. Si la valeur est supérieure à la valeur que vous recherchez, poursuivez la recherche dans le sous-arbre de droite.

Voici le code de la méthode find :

function search($value) {
    $current = $this -> root;
    while ($current != null) {
        if ($value == $current -> value) {
            return $current;
        } else if ($value < $current -> value) {
            $current = $current -> left;
        } else {
            $current = $current -> right;
        }
    }
    return null;
}

Delete Node

La méthode delete node est l'une des méthodes les plus complexes de toute l'implémentation. La manière dont un nœud est supprimé dépend du nombre d’enfants du nœud. Il peut y avoir les situations suivantes :

• Le nœud est un nœud feuille et n'a pas de nœud enfant. Supprimez le nœud directement. Le nœud
• n’a qu’un seul nœud enfant. Remplacez les nœuds enfants par ce nœud. Le nœud
• a deux nœuds enfants. Recherchez la valeur minimale dans le sous-arbre droit du nœud, remplacez la valeur minimale par ce nœud et supprimez la valeur minimale du sous-arbre droit.

Voici le code de la méthode delete :

function delete($value) {
    $current = $this -> root;
    $parent = null;
    while ($current != null) {
        if ($value == $current -> value) {
            if ($current -> left == null && $current -> right == null) {
                if ($parent == null) {
                    $this -> root = null;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = null;
                    } else {
                        $parent -> right = null;
                    }
                }
            } else if ($current -> left == null) {
                if ($parent == null) {
                    $this -> root = $current -> right;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = $current -> right;
                    } else {
                        $parent -> right = $current -> right;
                    }
                }
            } else if ($current -> right == null) {
                if ($parent == null) {
                    $this -> root = $current -> left;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = $current -> left;
                    } else {
                        $parent -> right = $current -> left;
                    }
                }
            } else {
                $replacementNode = $current -> right;
                while ($replacementNode -> left != null) {
                    $replacementNode = $replacementNode -> left;
                }
                $removeValue = $replacementNode -> value;
                $this -> delete($replacementNode -> value);
                $current -> value = $removeValue;
            }
            return;
        } else if ($value < $current -> value) {
            $parent = $current;
            $current = $current -> left;
        } else {
            $parent = $current;
            $current = $current -> right;
        }
    }
}

Conclusion

Maintenant, nous avons appris comment implémenter un arbre binaire en php. Les arbres binaires constituent une structure de données de base en informatique et de nombreux algorithmes et applications l'impliquent. Nous avons appris à insérer des nœuds, à rechercher des nœuds et à supprimer des nœuds. Nous pouvons également étendre cette classe pour implémenter d’autres méthodes pratiques.

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!