ホームページ >バックエンド開発 >C++ >BST (DSA) に要素を挿入するにはどうすればよいですか?

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

Patricia Arquette
Patricia Arquetteオリジナル
2024-10-31 05:45:30637ブラウズ

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

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

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

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

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

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

こんな感じです
How to Insert element into a BST (DSA) ?

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

How to Insert element into a BST (DSA) ?

そのため、最初にノードを作成し、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 サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。