Arbre de recherche binaire en Javascript

Implémentation d'un arbre de recherche binaire en JavaScript

Dans cet article, nous explorerons comment implémenter un arbre de recherche binaire (BST) de base en JavaScript. Nous aborderons l'insertion de nœuds et l'exécution de différentes méthodes de parcours d'arborescence : dans l'ordre, en pré-commande et en post-commande.

La classe Noeud
Tout d’abord, définissons une classe Node pour représenter chaque nœud de l’arborescence :

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

Chaque objet Node possède trois propriétés :

• valeur : Les données stockées dans le nœud.
• gauche : un pointeur vers le nœud enfant gauche.
• right : un pointeur vers le nœud enfant droit.

La classe BinarySearchTree

Ensuite, nous définirons une classe BinarySearchTree qui gérera les nœuds et fournira des méthodes pour interagir avec l'arborescence :

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    isEmpty() {
        return this.root === null;
    }

    insertNode(root, newNode) {
        if(newNode.value < root.value) {
            if(root.left === null) {
                root.left = newNode;
            } else {
                this.insertNode(root.left, newNode);
            }
        } else {
            if(root.right === null) {
                root.right = newNode;
            } else {
                this.insertNode(root.right, newNode);
            }
        }
    }

    search(root, value) {
        if(!root) {
            return false;
        }
        if(root.value === value) {
            return true;
        } else if(root.value > value) {
            return this.search(root.left, value);
        } else {
            return this.search(root.right, value);
        }
    }

    insert(value) {
        const newNode = new Node(value);
        if(this.isEmpty()) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }
}

Méthodes clés :

• isEmpty() : Vérifie si l'arborescence est vide.
• insertNode(root, newNode) : insère un nouveau nœud dans l'arborescence, en conservant la propriété de l'arbre de recherche binaire.
• search(root, value) : recherche récursivement une valeur dans l'arborescence.
• insert(value) : Une méthode pratique pour insérer une nouvelle valeur dans l'arborescence.

Méthodes de traversée des arbres

Une fois qu'on a un arbre, on a souvent besoin de le traverser. Voici les trois méthodes de parcours courantes :

Parcours dans l'ordre

Le parcours dans l'ordre visite les nœuds dans l'ordre suivant : Gauche, Racine, Droite.

inOrder(root) {
    if(root) {
        this.inOrder(root.left);
        console.log(root.value);
        this.inOrder(root.right);
    }
}

Ce parcours imprime les nœuds dans un ordre non décroissant pour un arbre de recherche binaire.

Précommandez Traversal

Le parcours de précommande visite les nœuds dans l'ordre suivant : Racine, Gauche, Droite.

preOrder(root) {
    if(root) {
        console.log(root.value);
        this.preOrder(root.left);
        this.preOrder(root.right);
    }
}

Ce parcours est utile pour copier la structure arborescente.

Traversée post-commande

Le parcours post-ordre visite les nœuds dans l'ordre suivant : Gauche, Droite, Racine.

postOrder(root) {
    if(root) {
        this.postOrder(root.left);
        this.postOrder(root.right);
        console.log(root.value);
    }
}

Ce parcours est souvent utilisé pour supprimer ou libérer des nœuds.

Exemple d'utilisation

Voyons comment ces méthodes fonctionnent ensemble :

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(3);
bst.insert(7);

console.log('In-order Traversal:');
bst.inOrder(bst.root);

console.log('Pre-order Traversal:');
bst.preOrder(bst.root);

console.log('Post-order Traversal:');
bst.postOrder(bst.root);

Conclusion

Avec cette implémentation, vous pouvez désormais créer et interagir avec un arbre de recherche binaire en JavaScript. Comprendre les structures arborescentes et les méthodes de parcours est crucial pour de nombreux problèmes algorithmiques, en particulier dans des domaines tels que les algorithmes de recherche, l'analyse des expressions et la gestion des données hiérarchiques.

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!