>  기사  >  백엔드 개발  >  BST(DSA)에 요소를 삽입하는 방법은 무엇입니까?

BST(DSA)에 요소를 삽입하는 방법은 무엇입니까?

Patricia Arquette
Patricia Arquette원래의
2024-10-31 05:45:30574검색

오늘 우리는 BST에 대해 알아보고 단일 요소를 삽입하는 방법 또는 BST**에 단일 노드를 삽입하는 방법을 알아보겠습니다. 이 기사를 읽기 전에 주제에 대한 BST 및 이중 연결 목록이 중요하다는 것을 이미 알고 있는 사람들에게는 쉽습니다. 그래서 참고할 수 있는 주제에 대한 링크를 제공했습니다.-

1.이중 연결 리스트의 경우
2.이진 트리의 경우

그래서 BST에 단일 노드를 삽입하는 방법을 알기 전에. BST가 무엇인지 알아야 합니다. BST는

** 이진 검색 트리**
다음과 같은 속성이 있습니다. :-

  1. 왼쪽 노드는 루트 및 오른쪽 요소에 비해 값이 적습니다
  2. 루트 노드는 오른쪽 노드에 비해 가치가 낮습니다
  3. 그리고 Inorder Triversal을 적용하여 노드를 Triverse하면 오름차순 정렬을 제공합니다.

이렇게 생겼네요
How to Insert element into a BST (DSA) ?

BST에 요소를 삽입하려면 루트 노드를 가리키는 하나의 포인터가 필요합니다. 어떤 부분에서는 키가 왼쪽이나 오른쪽에 삽입될지 어떻게 알 수 있는지 루트 데이터와 키를 비교해야 하기 때문입니다.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.