[백준 / BOJ] 5639 이진 검색 트리

문제

출처 : www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

트리를 전위 순회한 결과가 주어졌을때, 트리를 후위순회한 결과를 출력하는문제다.

 

풀이

문제는 간단한데 입력은 그렇지 않았다..

처음에는 완전이진트리를 생각하고 구현하다가 런타임에러가 떴다(배열 범위 초과). 다시 잘 읽어보니 노드가 한쪽으로 쭉 늘어날수있었다.

완전이진트리로 구현할려면, 배열의 범위가 2^10000 까지 가야해서 이 방법으로는 풀수없다.

 

런타임에러 코드

런타임에러 코드

//
//  main.cpp
//  5639 이진 검색 트리
//
//  Created by 이준영 on 2021/01/17.
//

#include <iostream>

using namespace std;
int tree[10005*4+5];

int findIdx(int idx, int num){
    while(true){
        if(tree[idx] == 0){
            break;
        }
        if(tree[idx] < num){
            idx = idx*2+1;
        }
        else{
            idx = idx*2;
        }
    }
    return idx;
}

void makeTree(){
    int num = 0;
    cin >> num;
    if(cin.eof() == true){
        return;
    }
    tree[findIdx(1, num)] = num;
    makeTree();
}

void search(int idx){
    if(tree[idx] == 0){
        return;
    }
    search(idx*2);
    search(idx*2+1);
    cout << tree[idx] << "\n";
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    makeTree();
    search(1);
    return 0;
}

 

배열을pair 형태로 선언해서 풀었다. 

 

노드의 키를 입력받을때마다, 해당 노드를 어디에 넣을수있는지 체크해준다.

배열을[부모노드의 키] = {왼쪽자식 노드의 키, 오른쪽자식노드의 키} 이런형태로 만들어줬다.

부모노드의 키와 입력받은 숫자를 비교해가면서 입력 받았는데,

1. 현재 부모노드의 키 보다 현재 수가 더 작을 경우, 부모노드의 왼쪽 노드를 확인한다.

-> 부모노드의 왼쪽노드가 비어있을때, 부모노드의 왼쪽노드에 입력받은 숫자를 저장하고 break해준다.

-> 비어있지않다면, 부모노드를 부모노드의 왼쪽노드로 바꿔준다. (idx = tree[idx].first)

 

2. 현재 부모노드의 키 보다 현재 수가 더 클 경우, 부모노드의 오른쪽 노드를 확인한다.

-> 부모노드의 오른쪽노드가 비어있을때, 부모노드의 오른쪽노드에 입력받은 숫자를 저장하고 break해준다.

-> 비어있지않다면, 부모노드를 부모노드의 오른쪽노드로 바꿔준다. (idx = tree[idx].second)

 

출력은 부모노드가 0이 아닐때까지 재귀를 들어가며 출력하면된다.

- 입력받는숫자들이 전부 양의 정수이므로 부모노드는 절대 0이될수없다. 업데이트 되지않은 tree배열의 first, second값은 0으로 초기화 되어있으므로, 0을 참조하는순간 끝내주면된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/5639%20%EC%9D%B4%EC%A7%84%20%EA%B2%80%EC%83%89%20%ED%8A%B8%EB%A6%AC/main.cpp

devxb/JJUNalgo