Maison interface Web js tutoriel Arbre de recherche binaire en Javascript

Arbre de recherche binaire en Javascript

Aug 09, 2024 am 09:13 AM

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;
    }
}
Copier après la connexion

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);
        }
    }
}
Copier après la connexion

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);
    }
}
Copier après la connexion

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);
    }
}
Copier après la connexion

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);
    }
}
Copier après la connexion

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

Exemple d'utilisation

Binary Search Tree in Javascript

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);
Copier après la connexion

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Remplacer les caractères de chaîne en javascript Remplacer les caractères de chaîne en javascript Mar 11, 2025 am 12:07 AM

Remplacer les caractères de chaîne en javascript

jQuery Vérifiez si la date est valide jQuery Vérifiez si la date est valide Mar 01, 2025 am 08:51 AM

jQuery Vérifiez si la date est valide

jQuery obtient un rembourrage / marge d'élément jQuery obtient un rembourrage / marge d'élément Mar 01, 2025 am 08:53 AM

jQuery obtient un rembourrage / marge d'élément

10 onglets jQuery Accordion 10 onglets jQuery Accordion Mar 01, 2025 am 01:34 AM

10 onglets jQuery Accordion

10 vaut la peine de vérifier les plugins jQuery 10 vaut la peine de vérifier les plugins jQuery Mar 01, 2025 am 01:29 AM

10 vaut la peine de vérifier les plugins jQuery

Http débogage avec le nœud et le http-console Http débogage avec le nœud et le http-console Mar 01, 2025 am 01:37 AM

Http débogage avec le nœud et le http-console

Tutoriel de configuration de l'API de recherche Google personnalisé Tutoriel de configuration de l'API de recherche Google personnalisé Mar 04, 2025 am 01:06 AM

Tutoriel de configuration de l'API de recherche Google personnalisé

jQuery Ajouter une barre de défilement à div jQuery Ajouter une barre de défilement à div Mar 01, 2025 am 01:30 AM

jQuery Ajouter une barre de défilement à div

See all articles