data-structures
Arbre de recherche binaire

Créer un nœud dans BST

L'arbre de recherche binaire (BST) est une structure de données hiérarchique avec un seul pointeur vers le nœud racine.

Le nœud dans le fichier BST contient généralement des "éléments" (tels que des nombres ou des noms) pour une recherche rapide. Chaque nœud a au plus deux enfants (gauche et droite). Chaque nœud est organisé par un champ de données clé. Pour chaque nœud dans BST, sa clé est plus grande que la clé de l'enfant gauche et moins que la clé de l'enfant droit

Une structure typique de noeud (qui stocke un entier) serait

struct bst_node {
    int item; 
    bst_node* left;
    bst_node* right;
}; 

Il n'y aura qu'un seul nœud racine de BST. Le noeud racine peut être créé par

bst_node* root = NULL;
root = (bst_node*) malloc(sizeof(bst_node));

Pour définir la clé d’élément de la racine sur 10.

root->item = 10;

insertion d'un noeud dans l'arbre de recherche binaire

struct tree{
    int a;
    tree* right;
    tree* left;
};
tree* root=NULL;
void insert(tree*& in, int b){
        if(in){
            if(in->a<b)
                    insert(in->right,b);
            else if(in->a>b)
                    insert(in->left,b);
            else
                cout<<"the value is already in the tree."<<endl;
        }else{
            tree* temp = new tree;
            temp->a=b;
            temp->right=NULL;
            temp->left=NULL;
            in=temp;
        }
}