首頁 >後端開發 >C++ >如何將元素插入 BST (DSA) ?

如何將元素插入 BST (DSA) ?

Patricia Arquette
Patricia Arquette原創
2024-10-31 05:45:30650瀏覽

今天我們將學習 BST 以及如何將單一元素(或我們可以說單一節點)插入 BST**。對於已經了解 BST 和雙鍊錶的人來說,這很容易,在閱讀本文之前,這些主題很重要。所以我提供了這些主題的鏈接,您可以參考它。 -

1.對於雙鍊錶
2.對於二元樹

所以在了解如何將單一節點插入 BST 之前。你一定要知道BST是什麼,BST是一個

** 二元搜尋樹**
它具有一些屬性,例如 :-

  1. 左節點的值較小或與根和右元素相比
  2. 根節點與右節點相比具有較小的值
  3. 當我們透過應用中序三叉樹來對節點進行三叉樹時,它會 給出升序排序數組。

看起來像這樣
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