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

문제 링크: https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

1. 주의할 점

- EOF를 입력받을 때 까지 수를 받기 위해 While(cin>>val) 을 사용한다. While(!cin.eof()) 사용하면 오답으로 뜬다

 

2. 구현

- Insert() 함수를 통해 현재 Node가 NULL이라면 새로 Node를 만든 후, 추가하고 NULL이 아니라면 현재 Node의 Data값과 비교하여 작다면 Node->left로, Node->right로 이동후, 다시 검사한다

- Postorder() 함수를 사용하여 Root Node의 후위순위를 출력한다

 

#include <iostream>
using namespace std;

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

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

void postorder(Node* node) {
	if (node->left != NULL)
		postorder(node->left);
	if (node->right != NULL)
		postorder(node->right);
	cout << node->data << '\n';
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	Node* root = NULL;
	int val;
	while (cin>>val) {
		if (val == EOF) break;
		root = insert(root, val);
	}
	postorder(root);
	return 0;
}