İkili bir ağacda yerləşdirmə

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çatdırılma Məlumat dəsti Pulsuz yükləmə GE Healthcare InfoEdge
İkili ağac Genişlik İlk Axtarış Queue AğacBaxılıb 72

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Bu yazıda, öyrənəcəyik ikili bir ağacda yerləşdirmə. Anlayışını artıq görmüşük BFS əvvəlki məqalədə, buna görə burada məlumatları ikili bir ağaca daxil etmək üçün eyni konsepsiyadan istifadə edəcəyik. Konsepsiya ağacdan səviyyə qaydasında keçir və sol və ya sağ və ya hər iki qovşaq NULL olan bir qovşaq ilə qarşılaşırıqsa, məlumatları NULL düyününün mövqeyinə daxil edin (əvvəlcə soldan üstünlük). Daha çox anlayış üçün aşağıdakı nümunəyə baxın.

İkili bir ağacda yerləşdirməPin

Yuxarıdakı ikili ağacda (10) məlumatları olan bir qovşaq əlavə etmək istəyirik. BFS-dən istifadə etdikdə sol uşağı NULL olan bir düyünü (5) tapırıq. Beləliklə, 10-in sol uşağı olaraq (5) məlumatları olan bir qovşaq əlavə edirik.

İkili bir ağacda yerləşdirməPin

 

İkili Ağacda Yerləşdirmə üçün C ++ Kodu

/*C++ Implementation of Insertion in Binary Tree*/ 
#include<bits/stdc++.h> 
using namespace std; 
/*Structure of Node of BT which contain pointer to left child and right child and a data for node.*/
struct Node{
    int data;
    struct Node* left;// for left child;
    struct Node* right;// for right child;
    Node(int value)// create a node using new_Node;
    {
        data=value;
        left=NULL;
        right=NULL;
    }
};
/*Function which print bfs of the given tree*/ 
void level_order(Node* root)
{
   if(root==NULL)
   { 
       return;
   }
   queue<Node*> q;
   q.push(root);
   while(!q.empty())
   {
       Node* temp=q.front();
       cout<<temp->data<<" ";
       q.pop();
       if(temp->left!=NULL)
       {
           q.push(temp->left);
       }
       if(temp->right!=NULL)
       {
           q.push(temp->right);
       }
   }
   cout<<endl;
}
void add(Node* root,int value)
{
    queue<Node*> q;
    q.push(root);
    while(!q.empty())
    {
        Node* temp=q.front();
        q.pop();
        if(temp->left==NULL)
        {
            temp->left=new Node(value);
            goto label;
        }
        if(temp->right==NULL)
        {
            temp->right=new Node(value);
            goto label;
        }
        if(temp->left!=NULL)
        {
           q.push(temp->left); 
        }
        if(temp->right!=NULL)
        {
            q.push(temp->right);
        }
    }
    label:;
}
int main() 
{ 
    /*construct tree*/
    Node* root= new Node(9);
    root->left= new Node(1);
    root->right= new Node(8);
    root->left->left= new Node(5);
    root->left->right= new Node(4);
    root->right->left= new Node(6);
    root->right->right= new Node(7);
    root->left->left->right= new Node(2);
    root->left->right->right= new Node(3);
    int value;
    cin>>value;//input the data of node which we want to insert;
    cout<<"Level order traversal before Insertion of node: ";
    level_order(root);
    /*add the node*/
    add(root, value);
    cout<<"Level order traversal after Insertion of node: ";
    level_order(root);
    return 0; 
}
Output:
Level order traversal before Insertion of node: 9 1 8 5 4 6 7 2 3 
Level order traversal after Insertion of node: 9 1 8 5 4 6 7 10 2 3

İkili Ağacda Yerləşdirmənin Zaman Mürəkkəbliyi

O (N) burada N - verilən ikili ağacdakı qovşaq sayı. Zamanın ən pis mürəkkəbliyi, hər düyünün tam bir uşağı olduqda baş verir. Burada xətti vaxtda ziyarət edirik. Xətti zaman mürəkkəbliyi N sırası ilə deməkdir.

Kosmik Mürəkkəblik

O (1) çünki verilən ikili ağacdakı qovluğu əlavə etmək üçün boşluq yaratmırıq.

arayış Müsahibə üçün sual

Crack Sistemi Dizayn Müsahibələri
Translate »