[백준][C++] 5639 이진 검색 트리

www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

 

 

알고리즘 종류

    - 트리

    - 그래프

 

 

 

사고 과정

    - 전위 순회로 이진트리 만드는 방법

        1. 전위 순회는 root를 먼저 출력하고 자식들을 출력하기 때문에 맨 앞에 root가 나오게 된다. 따라서 전위 순회를 순서대로 넣어주면 이진트리를 만들 수 있다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
struct Node{
    int data;
    Node *left = NULL;
    Node *right = NULL;
};
 
void make_tree(Node *p, int num){
 
    Node *node = new Node;
    node->data = num;
    Node *tmp;
    
    while(p){
        tmp = p;
        if(p->data < num) p = p->right;
        else p = p->left;
    }
    if(num < tmp->data) tmp->left = node;
    else tmp->right = node;
}
 
 
void post_order(Node *p){
    if(p != NULL){
        post_order(p->left);
        post_order(p->right);
        cout << p->data << '\n';
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    Node *root = new Node;
    cin >> root->data;
    
    int num;
    while(cin >> num){
        make_tree(root, num);
    }
    
    post_order(root);
}

    - 배열을 이용한 트리 탐색

#include <iostream>
#include <vector>
 
using namespace std;
 
struct Node{
    int left=0;
    int right=0;
};
 
Node tree[1000001];
 
void insert(int p, int data){
    if(p<data){
        if(tree[p].right == 0) tree[p].right = data;
        else insert(tree[p].right, data);
    }
    else {
        if(tree[p].left == 0) tree[p].left = data;
        else insert(tree[p].left, data);
    }
}
 
void post_order(int p){
    
    if(p != 0){
        post_order(tree[p].left);
        post_order(tree[p].right);
        cout << p << "\n";
    }
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    int root;
    cin >> root;
    
    int num;
    while(cin >> num){
        insert(root, num);
    }
    
    post_order(root);
}
 

 

 

시행착오

    - 이진트리 만드는 방법을 배울 수 있었다.