백준 5639번 C++

백준 5639번 이진 검색 트리

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

5639번: 이진 검색 트리

정답 코드

#include<iostream>
using namespace std;
struct node {
	int data;
	node* left;
	node* right;
};
node* insert(node* root, int data) {
	if (root == NULL) {
		root = new node();
		root->data = data;
		root->left = NULL;
		root->right = NULL;
	}
	else if (root->data < data)
		root->right = insert(root->right, data);
	else
		root->left = insert(root->left, data);
	return root;
}
void postorder(node *root) {
	if (root) {
		postorder(root->left);
		postorder(root->right);
		cout << root->data << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int input;
	node* root = NULL;
	while (cin >> input) {
		root = insert(root, input);
	}
	postorder(root);

}

문제 풀이

트리 구조를 구성하기 위해 구조체를 사용하였습니다. 트리에 원소를 삽입하는 insert함수와 전위순회하는 postorder함수 두 개를 생성하였습니다.
전위순회는 간단히 구현하였습니다. root가 null이 아니라면 루트가 가리키는 left를 방문하고 그 다음 root라 가리키는 right를 방문합니다. 이렇게 postorder함수를 계속 호출하면 재귀형식이 되기 때문에 root를 기준으로 좌측을 다 출력하면 root로 돌아간 뒤 root기준 우측값을 다 출력하게 됩니다.
insert함수는 세 가지 경우를 나누었습니다. 루트가 null일때, 루트 좌측이 삽입한 원소보다 작을 때, 클 때입니다. 만약 루트가 null이라면 새로운 구조체를 생성한 후 루트에 데이터를 삽입하고 left,right를 null값으로 처리합니다. 이후에 값이 들어와야 하기 때문입니다.
root가 null이 아니라면 이미 원소가 있는 것이기 때문에 새로 삽입하는 원소와 비교를 하여 좌측으로 갈지 우측으로 갈지 결정하게 하였습니다.