BST (DSA) に要素を挿入するにはどうすればよいですか?

今日は BST について学び、BST に単一要素、つまり単一ノードを挿入する方法を学びます**。 BST とダブル リンク リストについてすでに知っている人にとっては、この記事を読む前に、これらのトピックが重要であることを理解するのは簡単です。したがって、これらのトピックへのリンクを提供しましたので、参照してください。-

1.二重リンクリストの場合
2.二分木の場合

BST に単一ノードを挿入する方法を知る前に。 BST とは何か、BST は

であることを知っておく必要があります。

** 二分探索ツリー**
次のようなプロパティがあります :-

1. 左側のノードの値は、ルートおよび右側の要素と比較して小さいです
2. ルートノードは右ノードと比較して値が小さい
3. そして、Inorder triversal を適用してノードを triverse すると、 昇順にソートされた配列を与えます。

こんな感じです

BST に要素を挿入するには、ルート ノードを指すポインタが 1 つ必要です。一部の部分ではキーとルート データを比較して、キーが左側または右側のどちらに挿入されるかを知る必要があるためです。

そのため、最初にノードを作成し、BST として動作するように初期化します。

これは、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;
}

以上がBST (DSA) に要素を挿入するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。