[백준 1991번 / C++] 트리 순회

dfs를 잘 활용해서 무엇을 언제 출력해야할지 풀면된다. 

 

#접근방법 

이차원 배열을 생성해서 각 알파벳들의 왼쪽 자식과 오른쪽 자식의 아스키코드값을 저장한다. 

 

1. preorder

먼저 'A' 값을 매개변수로 전달해서 해당 루트값이 '.' 라면 리턴하고 

그렇지 않다면, 루트 노드를 먼저 출력하고 루트노드의 왼쪽 자식과 오른쪽 자식 순대로 dfs를 호출한다. 

 

2. inorder

먼저 'A' 값을 매개변수로 전달해서 

루트노드의 왼쪽 자식을 계속 호출해서 해당 루트값이 '.' 라면 리턴해준다.

그 후 루트노드값을 출력하고 오른쪽 자식을 계속 호출을 반복한다. 

 

3. postorder

먼저 'A' 값을 매개변수로 전달해서

루트노드의 왼쪽 자식을 계속 호출해서 해당 루트값이 '.' 라면 리턴해준다.  

오른쪽 자식을 계속 호출해서 해당 루트값이 '.'라면 리턴해준다.  

 루트노드값을 출력한다. 

 

#include <iostream>
using namespace std;
int parent[26][2]; 
int n;
void preorder(char root) {
	if (root == '.')return; 
	cout << root; 
	preorder(parent[root-65][0]); 
	preorder(parent[root-65][1]);
}

void inorder(char root) {
	if (root == '.')return;
	inorder(parent[root - 65][0]);
	cout << root;
	inorder(parent[root - 65][1]);
}

void postorder(char root) {
	if (root == '.')return;	
	postorder(parent[root - 65][0]);
	postorder(parent[root - 65][1]);
	cout << root;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n; 
	for (int i = 0; i < n; i++) {
		char a, b, c; cin >> a >> b >> c; 
		parent[a - 65][0] = b; 
		parent[a - 65][1] = c; 
	}
	preorder('A');
	cout << endl; 
	inorder('A');
	cout << endl;
	postorder('A');

}

 

1991번: 트리 순회