Comment insérer un élément dans un BST (DSA) ?

Aujourd'hui, nous allons découvrir le BST et comment nous pouvons insérer un seul élément ou nous pouvons dire un seul nœud dans un BST**. C'est facile pour ceux qui connaissent déjà les listes BST et doubles, ces sujets sont importants avant de lire cet article. J'ai donc fourni le lien pour ces sujets, vous pouvez vous y référer.-

1.Pour les listes à double chaînage
2.Pour l'arbre binaire

Donc avant de savoir comment insérer un seul nœud dans BST. Vous devez savoir ce qu'est la BST, la BST est un

** Arbre de recherche binaire**
qui ont certaines propriétés comme :-

1. Le nœud gauche a moins de valeur ou comparé à l'élément racine et droit
2. Le nœud racine a moins de valeur que le nœud droit
3. Et lorsque nous triversons le nœud en appliquant le triversal Inorder, cela donner un tableau trié par ordre croissant.

Ça ressemble à ça

Pour insérer un élément dans BST, nous avons besoin d'un pointeur qui pointe vers le nœud racine car dans une certaine partie, nous devons comparer notre clé avec les données racine pour savoir comment nous savons si la clé va être insérée à gauche ou à droite.

Nous créons donc d’abord un nœud et l’initialisons pour qu’il se comporte comme un BST.

C'est le code auquel vous pouvez vous référer. Le code est présent en langage C.

#include<stdio.h>
#include<stdlib.h>
struct node{
   struct node* left;
   int data;
   struct node* right;
};
struct node* createNode(int key){
   struct node * newNode = NULL;
   newNode = malloc(sizeof(struct node));
   newNode->left = NULL;
   newNode->data = key;
   newNode->right = NULL;

   return newNode;
}
void insertNewNode(struct node* root , int key){
    struct node * prev = NULL;
    while(root!=NULL){
        prev = root;
        if(key==root){
            printf("element cannot insert it is present 
                              inside the bst already");
            return ;
        }
        else if(key>root->data)
        {   
                root = root->right;
        }
        else{
            root = root->left;
        }
    }
    struct node * newNode = createNode(key);
    if(key>prev->data){
        prev->right = newNode;
    }
    else{
        prev->left = newNode;
    }
}
void inOrder(struct node* root){
     if(root == NULL){
        return root;
    }
    inOrder(root->left);
    printf("%d",root->data1`1);
    inOrder(root->right);

}
int main(){

    struct node* head1 = createBst(20);
    struct node* head2 = createBst(10);
    struct node* head3 = createBst(30);


    head1->left=head2;
    head1->right=head3;

    insertNewNode(head1,40);
    printf("%d\n",head1->right->right->data);
    inOrder(head1);




    return 0;
}

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!