이진 트리에 삽입

난이도 쉽게
자주 묻는 질문 배달 팩트 셋 무료 GE 헬스 케어 인포에지
이진 트리 폭 우선 검색 나무조회수 74

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

이 기사에서 우리는 이진 트리에 삽입. 우리는 이미 BFS 이전 기사에서 이진 트리에 데이터를 삽입하는 데 동일한 개념을 사용합니다. 개념은 레벨 순서로 트리를 순회하고 왼쪽 또는 오른쪽 또는 두 노드가 모두 NULL 인 노드를 발견하면 NULL 노드의 위치에 데이터를 삽입합니다 (기본 설정은 왼쪽에서 먼저). 자세한 내용은 아래 예를 참조하십시오.

이진 트리에 삽입

위의 이진 트리에 data (10)가있는 노드를 삽입하려고합니다. BFS를 사용할 때 자식 NULL을 남긴 node (5)를 찾습니다. 그래서 우리는 10의 왼쪽 자식으로 data (5) 노드를 추가합니다.

이진 트리에 삽입

 

이진 트리에 삽입하기위한 C ++ 코드

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

이진 트리 삽입의 시간 복잡성

의 위에) 여기서 N은 주어진 이진 트리의 노드 수입니다. 최악의 시간 복잡성은 모든 노드에 정확히 하나의 자식이있을 때 발생합니다. 여기서 우리는 선형 시간으로 방문합니다. 선형 시간 복잡도는 N 순서임을 의미합니다.

공간 복잡성

O (1) 주어진 바이너리 트리에 노드를 추가 할 공간을 만들지 않기 때문입니다.

참고 인터뷰 질문

균열 시스템 설계 인터뷰
Translate »