[C언어 백준 풀이] 5639번 : 이진 검색 트리 (연결리스트 구조체로 트리 구현)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 Class 4에 해당하는 문제인 5639번 : 이진 검색 트리에 대한 풀이 코드와 해설을 다루고 있습니다. (Solved.ac 기준 난이도 Silver I)

 

 

 

5639번 : 이진 검색 트리

트리를 전위 순회한 결과가 입력값으로 들어오면, 이들을 후위 순회한 결과를 출력하는 문제입니다.

 

일반 트리가 아닌 이진 검색 트리이므로 노드의 키가 왼쪽 서브트리에 있는 모든 노드의 키들보다 크고 오른쪽 서브트리에 있는 모든 노드의 키들보다 작다는 조건을 만족합니다.

따라서 전위 순회(preorder)인 것만 알려주면 순서대로 키만 입력되어도 조건대로 트리를 재구현할 수 있습니다.

트리를 재구현한 뒤 postorder 방식으로 순회하며 각 노드들의 키를 출력하는 문제입니다.

 

#include <stdio.h>

typedef struct Node_type {
    int key;
    struct Node* left;
    struct Node* right;
} Node;

Node* insert(Node* node, int input) {
    if(node == NULL) {
        Node* node = (Node*)malloc(sizeof(Node));
        node->key = input;
        node->left = node->right = NULL;
        return node;
    }
    else if(input < node->key) node->left = insert(node->left, input);
    else if(input > node->key) node->right = insert(node->right, input);
    return node;
}

void postorder(Node* node) {
    if(node == NULL) return;
    postorder(node->left);
    postorder(node->right);
    printf("%d\n", node->key);
}

int main() {
    int input;
    Node* root = NULL;
    while(scanf("%d", &input) != EOF) {
        root = insert(root, input);
    }
    postorder(root);
}

 

풀이는 한 마디로 정리하면 연결리스트 구조체의 구현 + 재귀 함수를 통한 postorder 순회입니다.

우선 Node 타입의 구조체를 선언하여 key 값과 왼쪽 자식, 오른쪽 자식 노드가 있음을 설정합니다.

이 문제에서는 input 수량의 입력이 없기 때문에 EOF 이전까지 계속해서 입력을 받는 형식이 필요합니다.

저의 경우에는 key를 입력받으면 insert 함수에서 key에 알맞은 node 자리를 찾고, 하위 node를 연결하여 return 하는 방식을 선택했습니다.

앞서 말했듯 이진 탐색 트리이므로 key의 크기에 따라 log N 시간에 삽입이 가능하므로, 조건문을 세워 재귀적으로 자리를 찾아 나가는 방식을 이용하면 됩니다.

 

[C언어 백준 풀이] 1991번 : 트리 순회 (preorder, inorder, postorder 차이)

 

배치가 끝난 이후에는 postorder 방식으로 출력해주면 됩니다.

이에 대한 부가 설명은 위의 링크에도 되어있으니, 순회 방식에 대해 더 알아보는 것도 좋을 것 같습니다.

 

 

 

이 문제의 풀이 코드를 제출하실 때에는 채점 언어가 C++로 되어있지는 않은지 한 번 확인해야합니다.

백준에서는 기본 채점 언어가 C++로 되어있기 때문에 C++로 하면 컴파일 에러가 발생합니다.

이는 C언어와 C++에서 typedef 구조체 선언 과정에서의 키워드 형식이 다르기 때문인 것으로 보여집니다.

다른 사람들의 C++ 풀이는 많았지만 기본적인 C언어에서의 구조체 리스트 풀이가 없어 C언어로 해결해보았던 문제입니다.