백준 5639번 (이진 검색 트리, C++) [BAEKJOON]

글쓴이 / / BaekjoonOnlineJudge, C++/CPP
목차 테이블
  1. 이진 검색 트리

이진 검색 트리

https://www.acmicpc.net/problem/5639

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초256 MB3544213888982138.260%

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

  • 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
  • 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
  • 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다.

후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다.

예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다.

노드에 들어있는 키의 값은 106보다 작은 양의 정수이다.

모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다.

같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

50
30
24
5
28
45
98
52
60

예제 출력 1

5
28
24
45
30
60
52
98
50

출처

ICPC > Regionals > Asia Pacific > Thailand > 2011 ACM-ICPC Asia Phuket Regional Programming Contest B번

알고리즘 분류

통과된 코드

#include <iostream>

using namespace std;

struct BinaryNode
{
    int _Num;
    BinaryNode* _Left;
    BinaryNode* _Right;

    BinaryNode(int num)
        : _Num(num), _Left(nullptr), _Right(nullptr)
    {}

    void ArrayBinaryNode(int _n)
    {
        if (_Num > _n) {
            if (_Left == nullptr) _Left = new BinaryNode(_n);
            else _Left->ArrayBinaryNode(_n);
        }
        else {
            if (_Right == nullptr) _Right = new BinaryNode(_n);
            else _Right->ArrayBinaryNode(_n);
        }
    }
};

void PostorderTraverse(BinaryNode& CurrentNode)
{
    if (CurrentNode._Left != nullptr) PostorderTraverse(*CurrentNode._Left);
    if (CurrentNode._Right != nullptr) PostorderTraverse(*CurrentNode._Right);
    cout << CurrentNode._Num << "\n";
}


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

    int _N;
    cin >> _N;
    BinaryNode _RootNode(_N);
    while (true) {
        cin >> _N;
        if (cin.eof() == true)
            break;
        _RootNode.ArrayBinaryNode(_N);
    }

    PostorderTraverse(_RootNode);

	return 0;
}

“백준 5639번 (이진 검색 트리, C++) [BAEKJOON]”에 대한 1,304개의 생각

  2. Juniorwaing

    https://www.yplocal.com/business-professional-services/druera

    Hey everyone! I’ve recently started incorporating Ceylon cinnamon into my daily routine, and I’m loving the results so far. I used to use regular cinnamon without really thinking about it, but after reading up on the differences between Ceylon cinnamon (also known as “true cinnamon”) and the more common Cassia variety, I decided to make the switch.

    One of the first things I noticed was the flavor—it’s a lot milder and sweeter than the Cassia cinnamon, which makes it perfect for baking, smoothies, or even just sprinkling on oatmeal. I’ve been using Ceylon cinnamon powder regularly, but I also keep Ceylon cinnamon sticks on hand for brewing teas and spicing up dishes. It adds a subtle but really pleasant flavor, without the strong bite you sometimes get from other cinnamons.

    Beyond the taste, I made the switch because of the health benefits. Ceylon cinnamon has significantly less coumarin than Cassia cinnamon, which makes it a much better option for long-term use, especially if you’re taking it in supplement form. I’ve been using Ceylon cinnamon supplements to help with blood sugar management and inflammation, and I’ve definitely noticed improvements in my energy levels and digestion.

    If you’re into natural products, I highly recommend giving Ceylon cinnamon products a try. Whether it’s the powder, sticks, or supplements, it’s such an easy way to add flavor to your meals and support your overall health at the same time. Plus, the fact that it’s lower in coumarin makes it a much safer option if you’re using it daily like I am. Has anyone else here made the switch to Ceylon cinnamon? I’d love to hear how you’re using it in your routine!

    답글

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

관련 게시물

백준 11053번 (가장 긴 증가하는 부분 수열, C++) [BAEKJOON]

백준 11053번 (가장 긴 증가하는 부분 수열, C++) [BAEKJOON]

BaekjoonOnlineJudge, C++/CPP / 글쓴이 / / , , , , , , , , , , , , , , , , , , , , ,

백준 11053번 '가장 긴 증가하는 부분 수열' 문제에 대한 글입니다. DP 알고리즘을…

위로 스크롤