백준 1991번 트리 순회 C++

리뷰

전위, 중위, 후위 순회 겁먹지 말고 그냥 출력 시점만 조정해 주면 된다.

우선 문제는 굉장히 친절하다, A, B, C 오름차순으로 주어지고 루트는 항상 A고 좌우 노드 모두 친절히 설명해 준다.

 

문제 풀이

1. 맵을 통해 앞의 노드를 키로 갖고 뒤의 값 두개를 pair로 받아준다.
2. A를 시작으로 dfs를 돌려주고 '.'가 아닌 노드를 왼쪽부터 방문해 주면 된다.
3. 전위 순회 : dfs 재귀를 실행하기 전에 루트 노드부터 출력 해준다.
4. 중위 순회 : 왼쪽 노드 재귀를 실행한 후 루트 노드를 출력해 주면 된다.
5. 후위 순회 : 왼쪽 및 오른쪽 노드 모두 재귀를 실행해 주고 나서 루트 노드를 출력해 주면 된다.
6. 각 dfs 실행 사이에 줄바꿈을 한번씩 해주면 된다.

 

참고 사항

문제에 친절히 힌트를 넣어줬다.

 

정답 코드

#include <iostream>
#include <vector>
#include <map>

using namespace std;
map<char, pair<char, char>> dic;

void dfs1(char index, vector<int> v) {
	char left = dic[index].first, right = dic[index].second;
	cout << index;
	if (left != '.' && !v[left]) {
		v[left] = 1;
		dfs1(left, v);
	}
	if (right != '.' && !v[right]) {
		v[right] = 1;
		dfs1(right, v);
	}
}

void dfs2(char index, vector<int> v) {
	char left = dic[index].first, right = dic[index].second;
	if (left != '.' && !v[left]) {
		v[left] = 1;
		dfs2(left, v);
	}
	cout << index;
	if (right != '.' && !v[right]) {
		v[right] = 1;
		dfs2(right, v);
	}
}

void dfs3(char index, vector<int> v) {
	char left = dic[index].first, right = dic[index].second;
	if (left != '.' && !v[left]) {
		v[left] = 1;
		dfs3(left, v);
	}
	if (right != '.' && !v[right]) {
		v[right] = 1;
		dfs3(right, v);
	}
	cout << index;
}

int main() {
	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		char a, b, c;
		cin >> a >> b >> c;
		dic[a] = { b, c };
	}
	vector<int> v(100, 0);
	dfs1('A', v);
	cout << "\n";
	dfs2('A', v);
	cout << "\n";
	dfs3('A', v);
}