(C++) - 백준(BOJ) 5639번 : 이진 검색 트리

www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

재귀를 활용해 이진 검색 트리를 구현 한 뒤 후위순회를 하는 문제였습니다.

 

풀이방법

 배열로는 풀 수 없습니다. 이진 트리의 구조상 자식이 최대 2개이므로 극단적인 경우에서 만약 노드의 수가 10,000개이고 한쪽 자식이 계속 없는 식으로 구성된다면 비어있는 자식을 표현하기 위한 배열공간도 필요합니다. 따라서 2^10,000의 배열 크기를 선언해야하는데 파일 크기 제한으로 seg fault를 맛볼 수 있습니다.

 

 1. 초기화 : 노드 구조체를 만듭니다. cin시 EOF를 만났다면 0을 반환하기 때문에 while(cin>>node) 로 작성해 값을 입력받습니다. 매 loop마다 트리에 노드를 추가해줍니다.

 2. 노드 추가 함수 실행 : 현재 node가 NULL이라면 새로운 Node구조체 생성 후 key를 저장해줍니다.

    2-1) 들어와야 하는 key가 부모노드의 key 미만라면 node->left를 새로운 부모노드로 삼아 노드 추가 함수를 호출합니다.

    2-2) 반대의 경우는 node->right를 새로운 부모노드로 삼아 호출합니다.

    2-3) 실행 후에는 node를 반환해줍니다.

 

* key가 중복해서 들어오는 경우는 문제에 없으므로 고려하지 않아도 됩니다.

 

 3. 후위순회 함수 실행 : 왼쪽 자식이 있다면 (NULL이 아니라면) 왼쪽 자식을 새롭게 부모로 하여 재귀호출해줍니다. 오른쪽 자식이 있다면 마찬가지로 오른쪽 자식을 부모로하여 재귀호출해줍니다. 모든 호출 뒤에 현재 노드의 key를 출력해줍니다.

 

 

Code

#include <bits/stdc++.h>
using namespace std;

struct Node { int key; Node *left,*right; };
int n;

Node *addNode(Node *node, int key){
    if(node == NULL){
        node = new Node();
        node -> key = key;
        node->left = node->right = NULL;
    }
    else if(key < node->key) node->left = addNode(node->left,key);
    else node->right = addNode(node->right,key);
    return node;
}

void postOrder(Node *node){
    if(node == NULL) return;
    postOrder(node->left);
    postOrder(node->right);
    cout << node->key << '\n';
}

int main(){
    Node *tree = NULL;
    while(cin >> n) tree = addNode(tree,n);
    postOrder(tree);
}