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

문제

• 이진 검색 트리(백준5639)

풀이

문제 해석을 하자면,

• 이진 검색 트리의 순회 문제이다.
• 문제에서 이진 검색 트리를 전위 순회한 결과를 입력으로 주어지면, 후위 순회한 결과를 출력해야 한다.

풀이

• 전위->후위 바로 구하는법은 모르겠지만,
• 전위를 통해서 BST를 구하고, 후위 순회는 구할 수 있을것 같다.
• 입력 끝까지 받는 EOF 관련해서 다시 기억해두자.
  • while() 문 내에서 cin 사용해서 EOF 확인하면 자동으로 탈출해주므로 while(cin>>inNum) 형태로 사용할 것

코드

#include<iostream>
#include<vector>
using namespace std;

struct node {
	int key=0;
	node* left = nullptr;
	node* right = nullptr;
};
typedef node* Node;

void insert(Node root, Node n1) {
	if (root->key < n1->key) {
		if (root->right != nullptr) {
			insert(root->right, n1);
		}
		else {
			root->right = n1;
		}
	}
	else if (root->key > n1->key) {
		if (root->left != nullptr) {
			insert(root->left, n1);
		}
		else {
			root->left = n1;
		}
	}
}

void postOrder(Node root) {
	if (root->left != nullptr)
		postOrder(root->left);
	if (root->right != nullptr)
		postOrder(root->right);
	cout << root->key << '\n';
}

int main() {
	// 전위 순회는 처음값 무조건 root
	int inNum = 0;
	cin >> inNum;
	Node root = new node();
	root->key = inNum;

	while (cin >> inNum) { // 이곳에 cin 넣어야 EOF보고 자동으로 종료 해줌
		// 종료시점(테스트할때 EOF는 Ctrl+Z 입력시 발생시킬 수 있음)

		Node n1 = new node();
		n1->key = inNum;
		
		// 1. insert함수를 통해서 root부터 자기자리 찾아가서 넣어주자.
		insert(root, n1);
	}
	// 2. 이후 postOrder 함수를 통해서 후위순회 구하자.
	postOrder(root);

	return 0;
}

느낀점

EOF 햇갈리지말자.

그리고 BST는 문제가 복잡할 경우엔 구현하는짓은 하지말자.
왠만하면 set, map같은 자료구조를 이용하던지 다른 방법을 찾던지 하자.