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

문제

5639번: 이진 검색 트리

전위 순회한 트리가 주어지면 이를 후위순회한 결과를 출력하면 되는 문제입니다.

 

제가 처음에 생각한 전략은 총 2가지 입니다.

1) 전위순회한 트리가 입력이 break point가 없게 들어오므로 어떻게 입력이 끝내는지 알 수 있나?

2) 입력으로 들어온 전위 순회 트리를 트리로 구현해 다시 후위 순회한 결과를 출력

 

typedef struct node *pointer;
typedef struct node{
	int ans;
	pointer left, right;
}node;

처음에 선언한 트리 노드의 선언입니다.

binary tree이므로 root 노드 보다 작으면 left , 크면 right로 갑니다.

 

1)번째 전략인 언제 끝날지 모르는 입력입니다.

pointer root = NULL;
int num;
while (cin >> num) {
	if (num == EOF)break;
	root = insert(root, num);
}

num == EOF 일때 break를 통해 입력을 끊어줍니다.

이제 num변수에 입력이 들어올 때 마다 insert 함수를 호출해 binary tree를 만들어 나갑니다.

pointer insert(pointer nod, int data) {
	if (nod == NULL) { //처음 초기 부분
		nod = new node();
		nod->ans = data;
		nod->left = nod->right = NULL;
	}
	else if (data <= nod->ans)
		nod->left = insert(nod->left, data);
	else
		nod->right = insert(nod->right, data);
	return nod;
}

처음 nod가 NULL 이라면 node를 생성해줍니다.

new 연산자는 c언어의 malloc과 비슷한 역할을 합니다.

void postorder(pointer ptr) {
	if (ptr) {
		postorder(ptr->left);
		postorder(ptr->right);
		cout << ptr -> ans << '\n';
	}
}

완성된 tree에 후위순회를 통해 출력해줍니다.

---

전체코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
typedef struct node *pointer;
typedef struct node{
    int ans;
    pointer left, right;
}node;
pointer insert(pointer nod, int data);
void postorder(pointer ptr);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    pointer root = NULL;
    int num;
    while (cin >> num) {
        if (num == EOF)break;
        root = insert(root, num);
    }
    postorder(root);
 
    return 0;
}
pointer insert(pointer nod, int data) {
    if (nod == NULL) { //처음 초기 부분
        nod = new node();
        nod->ans = data;
        nod->left = nod->right = NULL;
    }
    else if (data <= nod->ans)
        nod->left = insert(nod->left, data);
    else
        nod->right = insert(nod->right, data);
    return nod;
}
void postorder(pointer ptr) {
    if (ptr) {
        postorder(ptr->left);
        postorder(ptr->right);
        cout << ptr -> ans << '\n';
    }
}