Un arbre de recherche binaire (BST) est un arbre binaire où le sous-arbre gauche ne contient que des n?uds avec des valeurs inférieures à la valeur du n?ud, le sous-arbre droit ne contient que des n?uds avec des valeurs supérieures à la valeur du n?ud, et les deux sous-arbres doivent également être BST; 1. L'implémentation C comprend une structure Treenode avec des pointeurs de valeur, gauche et droite; 2. La classe BST fournit des opérations d'insertion, de recherche et de traversée intégrée à l'aide de méthodes d'assistance récursive; 3. L'insertion maintient la propriété BST en comparant les valeurs et en évitant les doublons; 4. La recherche fonctionne dans le temps moyen o (log n) en naviguant vers la gauche ou la droite en fonction des comparaisons; 5. Valeurs de traversée en ordre dans l'ordre dans l'ordre trié en visitant à gauche, root, puis à droite; 6. Les considérations clés pour la production comprennent l'ajout d'un destructeur pour le nettoyage de la mémoire, l'équilibrage de l'arbre à l'aide d'une logique AVL ou rouge-noir et implémentant des méthodes itératives pour empêcher le débordement de la pile, ce qui fait de cet exemple une compréhension fondamentale des BST en c.

Voici un exemple C pratique d'un arbre de recherche binaire (BST) avec des opérations de base: insérer, recherche et traversée dans l'ordre.

? Qu'est-ce qu'un arbre de recherche binaire?

Un BST est un arbre binaire où:

• Le sous-arbre gauche d'un n?ud ne contient que des n?uds avec des valeurs inférieures à la valeur du n?ud.
• Le sous-arbre droit ne contient que des n?uds avec des valeurs supérieures à la valeur du n?ud.
• Les sous-arbres gauche et droit doivent également être des arbres de recherche binaires.

? C Exemple d'implémentation

 #include <iostream>
Utilisation de Namespace Std;

// définir la structure d&#39;un n?ud d&#39;arbre
struct treenode {
    INT VALEUR;
    Treenode * à gauche;
    Treenode * à droite;

    // constructeur
    Treenode (int Val): valeur (val), gauche (nullptr), droite (nullptr) {}
};

// Classe d&#39;arbre de recherche binaire
classe bst {
publique:
    Treenode * root;

    // constructeur
    Bst (): root (nullptr) {}

    // Fonction d&#39;insertion publique
    void insert (int value) {
        root = insertrecursive (root, valeur);
    }

    // Fonction de recherche publique
    BOOL Search (int Value) {
        return searchReCursive (root, valeur);
    }

    // Traversion dans l&#39;ordre (imprime les valeurs dans l&#39;ordre trié)
    void inOrder () {
        InOrderRecursive (racine);
        cout << endl;
    }

privé:
    // assistant: insérer le n?ud récursivement
    Treenode * insertrecursive (Treenode * n?ud, int value) {
        // Si l&#39;arbre est vide, créez un nouveau n?ud
        if (node == nullptr) {
            return new Treenode (valeur);
        }

        // sinon, reproduire l&#39;arbre
        if (valeur <Node-> valeur) {
            Node-> Left = insertRecursive (Node-> gauche, valeur);
        } else if (valeur> node-> value) {
            Node-> droite = insertrecursive (node-> droite, valeur);
        }
        // ignorer les doublons (valeur == n?ud-> valeur)

        Node de retour;
    }

    // assistant: recherche récursivement
    bool SearchReCursive (Node Treenode *, int Value) {
        if (node == nullptr) {
            retourne false; // pas trouvé
        }
        if (node-> value == valeur) {
            Retour Vrai; // Trouvé
        }
        if (valeur <Node-> valeur) {
            return searchReCursive (node-> gauche, valeur);
        } autre {
            return searchReCursive (node-> droite, valeur);
        }
    }

    // assistant: traversée dans l&#39;ordre (gauche -> root -> à droite)
    void inOrderRecursive (Treenode * n?ud) {
        if (node! = nullptr) {
            inOrderRecursive (n?ud-> gauche);
            cout << node-> value << "";
            inOrderRecursive (Node-> à droite);
        }
    }
};

// Exemple d&#39;utilisation
int main () {
    Bst arbre;

    // insérer des valeurs
    arbre.insert (50);
    arbre.insert (30);
    Tree.insert (70);
    arbre.insert (20);
    arbre.insert (40);
    arbre.insert (60);
    Tree.insert (80);

    // Imprimer la traversée dans l&#39;ordre (devrait être trié)
    cout << "Traversal dans l&#39;ordre:";
    Tree.inOrder (); // Sortie: 20 30 40 50 60 70 80

    // Recherche de valeurs
    cout << "Recherche 40:" << (arbre.search (40)? "Found": "non trouvé") << endl;
    cout << "Search 25:" << (Tree.Search (25)? "Found": "non trouvé") << endl;

    retour 0;
}

? Sortir:

 Traversion dans l'ordre: 20 30 40 50 60 70 80
Rechercher 40: trouvé
Recherche 25: Pas trouvé

? Points clés:

• L'insertion maintient la propriété BST en comparant les valeurs.
• La recherche est efficace (o (log n) en moyenne) en allant à gauche / à droite.
• La traversée dans l'ordre donne une sortie triée - l'un des principaux avantages des BST.
• Cette version ignore les valeurs en double . Vous pouvez le modifier pour autoriser les doublons (par exemple, en utilisant ou en stockant le nombre).

?? Remarque:

Il s'agit d'une implémentation de base. Pour une utilisation en production, considérez:

• Nettoyage de la mémoire (ajoutez un destructeur pour supprimer les n?uds).
• équilibrage (utilisez des arbres AVL ou rouge-noir pour éviter les arbres asymétriques).
• Versions itératives pour éviter le débordement de pile dans les arbres profonds.

Fondamentalement, cet exemple vous donne une base solide pour comprendre comment les BST fonctionnent en c.

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!