Wie füge ich ein Element in ein BST (DSA) ein?

Heute lernen wir etwas über BST und wie wir ein einzelnes Element oder sagen wir einen einzelnen Knoten in ein BST einfügen können**. Für diejenigen, die sich bereits mit BST und doppelt verknüpften Listen auskennen, ist es einfach, diese wichtigen Themen zu lesen, bevor Sie diesen Artikel lesen. Deshalb habe ich den Link für diese Themen bereitgestellt, auf den Sie verweisen können.-

1.Für doppelt verknüpfte Liste
2.Für Binärbaum

Also vorher: Wissen, wie man einen einzelnen Knoten in BST einfügt. Sie müssen wissen, was BST ist, BST ist ein

** Binärer Suchbaum**
die einige Eigenschaften haben wie :-

1. Der linke Knoten hat einen geringeren Wert oder weniger als das Wurzel- und das rechte Element
2. Der Wurzelknoten hat im Vergleich zum rechten Knoten einen geringeren Wert
3. Und wenn wir den Knoten mithilfe der Inorder-Triversierung triversieren, wird dies der Fall sein Geben Sie ein aufsteigend sortiertes Array an.

Es sieht so aus

Zum Einfügen eines Elements in BST benötigen wir einen Zeiger, der auf den Wurzelknoten zeigt, da wir teilweise unseren Schlüssel mit den Wurzeldaten vergleichen müssen, um zu wissen, ob der Schlüssel entweder auf der linken oder rechten Seite eingefügt wird.

Also erstellen wir zuerst einen Knoten und initialisieren ihn so, dass er sich wie ein BST verhält.

Dies ist der Code, auf den Sie verweisen können. Code ist in C-Sprache vorhanden.

#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;
}

Das obige ist der detaillierte Inhalt vonWie füge ich ein Element in ein BST (DSA) ein?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!