Algorithm/문제풀이
[C++] 백준 알고리즘 5639 이진 검색 트리
사과당근
2021. 11. 22. 18:36
예전에 올린 이진 탐색 트리 코드를 일부 수정했다.
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);
}