트리 순회 (선주문, 주문 및 후 주문)

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 MAQ 신탁 스냅 딜
이진 트리 나무 트리 순회조회수 84

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

먼저 우리는 다음에 대해 알아야합니다. 이진 트리에서 순회는 무엇입니까. Traversal은 특정 방식 / 순서로 모든 노드를 정확히 한 번 방문하는 방법의 한 유형입니다. 기본적으로 두 가지 유형의 순회가 있습니다. 이진 트리:

우리는 이미 무엇인지 알고 있습니다 BFS의 개념. 이제 Preorder, Inorder 및 Postorder 순회를 볼 수 있으며 이러한 순회는 이진 트리 DFS의 일부입니다. 따라서 모든 트리 유형을 자세히 볼 수 있습니다.

트리 순회 (Preorder, Inorder & Postorder)

순회 선주문

이 순회에서는 먼저 현재 노드의 데이터를 인쇄 한 다음 먼저 왼쪽 하위 트리로 이동 한 다음 오른쪽 하위 트리로 이동합니다. 위의 이진 트리의 사전 주문 순회는 다음과 같습니다. 0 1 3 4 2 5 6.

암호알고리즘

Algorithm: 
Preorder(root): 
Step:1 Print the data of the Node. 
Step:2 Move to the left side of the node(traverse left-subtree). 
Step:3 Move to the right side of the node(traverse right-subtree).

중위 순회

이 순회에서는 먼저 왼쪽 하위 트리로 이동 한 다음 노드의 데이터를 인쇄합니다. 노드의 데이터를 인쇄 한 후 오른쪽 하위 트리로 이동합니다. 위의 이진 트리의 순서 순회는 다음과 같습니다. 1 3 4 0 2 5 6.

암호알고리즘

Algorithm:  
Inorder(root): 
Step:1 Move to the left side of the node(traverse left-subtree). 
Step:2 Print the data of the Node.  
Step:3 Move to the right side of the node(traverse right-subtree).

포스트 오더 순회

이 순회에서는 먼저 왼쪽 하위 트리로 이동 한 다음 오른쪽 하위 트리로 이동합니다. 이동 후 노드의 데이터를 인쇄합니다. 위의 이진 트리의 사후 순회는 다음과 같습니다. 1 3 4 2 5 6 0.

암호알고리즘

Algorithm: 
Postorder(root): 
Step:1 Move to the left side of the node(traverse left-subtree). 
Step:2 Move to the right side of the node(traverse right-subtree). 
Step:3 Print the data of the Node.

실시

/*C++ Implementation of print the Preorder, Inorder, Postorder traversal of given 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 preorder of the given tree*/ 
void Preorder_tree(Node* root)
{
    if(root==NULL)
    {
        return;
    }
    cout<<root->data<<" ";
    Preorder_tree(root->left);
    Preorder_tree(root->right);
}
/*Function which print inorder of the given tree*/ 
void Inorder_tree(Node* root)
{
    if(root==NULL)
    {
        return;
    }
    Preorder_tree(root->left);
    cout<<root->data<<" ";
    Preorder_tree(root->right);
}
/*Function which print postorder of the given tree*/ 
void Postorder_tree(Node* root)
{
    if(root==NULL)
    {
        return;
    }
    Preorder_tree(root->left);
    Preorder_tree(root->right);
    cout<<root->data<<" ";
}
int main() 
{ 
    /*construct tree*/
    Node* root= new Node(0);//root node;
    root->left= new Node(1);
    root->right= new Node(2);
    root->left->left= new Node(3);
    root->left->right= new Node(4);
    root->right->left= new Node(5);
    root->right->right= new Node(6);
    cout<<"Preorder traversal of BT: ";
    Preorder_tree(root);cout<<"\n";
    cout<<"Inorder traversal of BT: ";
    Inorder_tree(root);cout<<"\n";
    cout<<"Postorder traversal of BT: ";
    Postorder_tree(root);cout<<"\n";
    return 0; 
}
Preorder traversal of BT: 0 1 3 4 2 5 6 
Inorder traversal of BT: 1 3 4 0 2 5 6 
Postorder traversal of BT: 1 3 4 2 5 6 0

시간 복잡성

의 위에) 여기서 N은 주어진 이진 트리에있는 총 노드 수입니다.

참조

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