[c++ | 백준] 5639번 이진 검색 트리

c++ 문제풀이

 

 

 

 

---

 

 

[백준 5639번 이진 검색 트리 문제]

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

 

 

 

 

---

 

 

 

전체 풀이 코드

#include <iostream>
using namespace std;

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

Node* root = NULL;
Node* MakeNode(int data);
void Insert(Node* root, Node* newNode);
void Postorder(Node* r);

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

    int value;
    
    while (cin >> value)
    {
        Insert(root, MakeNode(value));
    }

    Postorder(root);

    return 0;
}

Node* MakeNode(int data)
{
    Node* newNode = new Node();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void Insert(Node* r, Node* newNode)
{
    if (root == NULL) root = newNode;
    else if (r->data < newNode->data)
    {
        if (r->right == NULL)
            r->right = newNode;
        else
            Insert(r->right, newNode);
    }
    else if (r->data > newNode->data)
    {
        if (r->left == NULL)
            r->left = newNode;
        else
            Insert(r->left, newNode);
    }
}

void Postorder(Node* r)
{
    if (r->left != NULL)
        Postorder(r->left);
    if (r->right != NULL)
        Postorder(r->right);
    cout << r->data << endl;
}

 

 

 

 

풀이 설명

먼저 후위 순회를 구현하기 위해 이진 탐색 트리를 구현했습니다.

 

1. 노드 구현

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

Node 구조체는 자신의 data와 왼쪽 자식 노드의 주소, 오른쪽 자식 노드의 주소를 가지고 있습니다.

 

 

2.  입력 받아 Node 생성하기

while (cin >> value)
    {
        Insert(root, MakeNode(value));
    }

더 이상 알맞은 입력이 들어오지 않을 때 까지 Insert()함수를 실행해 주는 while문을 main에서 실행해줍니다.

 

Node* MakeNode(int data)
{
    Node* newNode = new Node();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

MakeNode함수는 매개변수로 받은 data값을 가지는 Node를 new 키워드로 생성하여 주소값을 반환하여줍니다.

 

void Insert(Node* r, Node* newNode)
{
    if (root == NULL) root = newNode;
    else if (r->data < newNode->data)
    {
        if (r->right == NULL)
            r->right = newNode;
        else
            Insert(r->right, newNode);
    }
    else if (r->data > newNode->data)
    {
        if (r->left == NULL)
            r->left = newNode;
        else
            Insert(r->left, newNode);
    }
}

 

 

Insert함수에서 newNode로 들어온 Node가 바로 MakeNode함수로 만들어진 노드입니다.

root 노드가 없다면 만들어준 newNode를 root로 설정해줍니다.

root 노드가 있는 상황이라면 r과 newNode의 data값을 비교하여 root의 왼쪽 또는 오른쪽 자식으로 newNode를 넣는 작업을 합니다.

newNode의 data값이 r의 data보다 크다면 r의 오른쪽 자식으로 newNode를 넣어줍니다.

반대로 newNode의 data값이 r의 data보다 작다면 r의 왼쪽 자식으로 newNode를 넣어줍니다.

 

이렇게 전위 순회로 입력이 들어왔을 때는 부모 -> 왼쪽 노드 -> 오른쪽 노드 순서로 노드를 순회하기 때문에 이렇게 노드들을 세팅해주면 됩니다.

 

 

3. 후위 순회 출력

void Postorder(Node* r)
{
    if (r->left != NULL)
        Postorder(r->left);
    if (r->right != NULL)
        Postorder(r->right);
    cout << r->data << endl;
}

위에서 정리한 트리를 후위 순회로 출력할 차례입니다.

후위 순회는 왼쪽 노드 -> 오른쪽 노드 -> 부모 노드 순서로 순회를 하기 때문에 차례대로 노드들을 출력해야합니다.

처음에 root 노드를 넣어 root부터 만들어진 트리를 확인하면서 순회를 시작합니다.

왼쪽 노드를 Postorder 함수에 넘겨주고 그 다음으로 오른쪽 노드를 Postorder 함수에 넘겨줍니다.

왼쪽과 오른쪽 노드를 재귀로 불러주는 이유는 왼쪽 노드가 자식을 가지고 있을 수 있기 때문입니다.

마지막으로 자기 자신의 데이터를 출력하게 되면 재귀를 돌면서 후위 순회로 노드들의 데이터가 출력되게 됩니다.

 

---

 

이렇게 백준 5639번을 직접 이진 탐색 트리를 구현하여 풀이해보았습니다.