ഒരു ബൈനറി ട്രീയിൽ ഉൾപ്പെടുത്തൽ


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ദില്ലി ഫാക്റ്റ്സെറ്റ് ഫ്രീചാർജ് GE ഹെൽത്ത്കെയർ വിവരം
ബൈനറി ട്രീ വീതിയുടെ ആദ്യ തിരയൽ വരി വൃക്ഷം

ഈ ലേഖനത്തിൽ, ഞങ്ങൾ പഠിക്കും ഒരു ബൈനറി ട്രീയിൽ ഉൾപ്പെടുത്തൽ. എന്ന ആശയം ഞങ്ങൾ ഇതിനകം കണ്ടു BFS മുമ്പത്തെ ലേഖനത്തിൽ, അതിനാൽ ഒരു ബൈനറി ട്രീയിൽ ഡാറ്റ ചേർക്കുന്നതിന് ഞങ്ങൾ ഇതേ ആശയം ഉപയോഗിക്കും. ലെവൽ ക്രമത്തിൽ ട്രീയിലൂടെ സഞ്ചരിക്കുന്നതാണ് ഈ ആശയം, ഇടത് അല്ലെങ്കിൽ വലത് അല്ലെങ്കിൽ രണ്ട് നോഡുകളും NULL ആയ ഒരു നോഡ് കണ്ടുമുട്ടിയാൽ, NULL നോഡിന്റെ സ്ഥാനത്ത് ഡാറ്റ ചേർക്കുക (മുൻ‌ഗണന ഇടത് വശത്ത് നിന്ന്). കൂടുതൽ മനസിലാക്കാൻ ചുവടെയുള്ള ഉദാഹരണം കാണുക.

ഒരു ബൈനറി ട്രീയിൽ ഉൾപ്പെടുത്തൽ

മുകളിലുള്ള ബൈനറി ട്രീയിൽ ഡാറ്റ (10) ഉള്ള ഒരു നോഡ് ചേർക്കാൻ ഞങ്ങൾ ആഗ്രഹിക്കുന്നു. ഞങ്ങൾ‌ BFS ഉപയോഗിക്കുമ്പോൾ‌ NULL ഉപേക്ഷിച്ച ഒരു നോഡ് (5) കാണാം. അതിനാൽ, 10 ന്റെ ഇടത് കുട്ടിയായി ഞങ്ങൾ ഡാറ്റ (5) ഉള്ള ഒരു നോഡ് ചേർക്കുന്നു.

ഒരു ബൈനറി ട്രീയിൽ ഉൾപ്പെടുത്തൽ

 

ഒരു ബൈനറി ട്രീയിൽ ഉൾപ്പെടുത്തുന്നതിനുള്ള സി ++ കോഡ്

/*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

ഒരു ബൈനറി ട്രീയിൽ ഉൾപ്പെടുത്തലിന്റെ സമയ സങ്കീർണ്ണത

O (N) ഇവിടെ നൽകിയിരിക്കുന്ന ബൈനറി ട്രീയിലെ നോഡുകളുടെ എണ്ണം N ആണ്. ഓരോ നോഡിനും കൃത്യമായി ഒരു കുട്ടിയുണ്ടാകുമ്പോൾ സമയ സങ്കീർണ്ണതയുടെ ഏറ്റവും മോശം അവസ്ഥ സംഭവിക്കുന്നു. ലീനിയർ സമയത്താണ് ഞങ്ങൾ ഇവിടെ സന്ദർശിക്കുന്നത്. ലീനിയർ സമയ സങ്കീർണ്ണത എന്നതിനർത്ഥം ഇത് എൻ ക്രമത്തിലാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1) തന്നിരിക്കുന്ന ബൈനറി ട്രീയിൽ നോഡ് ചേർക്കാൻ ഞങ്ങൾ ഒരു സ്ഥലവും സൃഷ്ടിക്കുന്നില്ല.

അവലംബം അഭിമുഖം ചോദ്യം