[C++] 백준 알고리즘 5639 이진 검색 트리

5639번: 이진 검색 트리 (acmicpc.net)

5639번: 이진 검색 트리

 

예전에 올린 이진 탐색 트리 코드를 일부 수정했다.

c언어로 구현했던 것을 c++로 구현하니 신경써야하는 부분이 있었다.

 

엔터 입력시 입력을 종료해야하는 부분이 까다로웠다.

그래서 getline을 이용해 문자열로 받은 다음,

stoi를 이용해 문자열을 정수로 변환했고

엔터 입력시 반복문을 빠져나오게 했다.

 

4358번 생태학 문제를 풀 때 비슷한 방법을 이용했다.

 

#include<iostream>
#include<map>
#include<string>

using namespace std;

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

Node* new_node(int n) { //새 노드 생성
	Node* node = new Node;
	node->data = n;
	node->left = NULL;
	node->right = NULL;
	return node;
}

Node* insert(Node* tree, int n) { //노드 삽입
	if (tree == NULL) return new_node(n);
	if (n < tree->data) // 단말 노드 만날 때 까지 재귀
		tree->left = insert(tree->left, n);
	else if (n > tree->data)// 단말 노드 만날 때 까지 재귀
		tree->right = insert(tree->right, n);
	return tree;
}

void postorder(Node* tree) { //후위 순회
	if (tree->left != NULL)
		postorder(tree->left);
	if (tree->right != NULL)
		postorder(tree->right);
	cout << tree->data << '\n';
}

int main() {
	Node* tree = NULL;
	string s;
	int n;
	while (true) {
		getline(cin, s);
		if (s == "") break; //마지막 입력이라면 반복문 탈출
		n = stoi(s); //입력이 있다면 문자열을 정수로 변환
		tree = insert(tree, n);
	}
	postorder(tree);
}