백준 5639 이진 검색 트리 (C++)

안유태·2022년 11월 23일
0

알고리즘

목록 보기
82/239
post-custom-banner

5639번: 이진 검색 트리

이진 트리를 이용한 문제이다. 먼저 전위 순회로 입력되는 값을 트리를 구현하여 저장해주었다. 그 후 후위 순회로 값들을 차례로 출력해주었다.
처음에는 배열로 노드를 구성하여 이를 순회하며 출력해주었는데 아웃바운드가 발생했다. 이유는 값이 많아질수록 배열의 요구 크기가 점점 너무 커지기때문에 범위 밖 접근이 발생한 것이다. 이를 해결하기 위해 트리를 직접 구현해주었다. 이 과정이 시간이 오래 걸렸다.



#include <iostream>

using namespace std;

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

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

    return node;
}

void printNode(Node* node) {
    if (node->left != NULL)
        printNode(node->left);

    if (node->right != NULL)
        printNode(node->right);

    cout << node->n << endl;
}

void solution(Node* node) {
    printNode(node);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    Node* A = NULL;
    int a;

    while (cin >> a) {
        if (a == EOF) break;

        A = setNode(A, a);
    }

    solution(A);

    return 0;
}
profile
공부하는 개발자
post-custom-banner

0개의 댓글