#1991 트리 순회

# 문제

# 입력 및 출력

# 풀이

배열을 int 배열을 쓸지 char 배열을 쓸지, 리스트를 쓸지 벡터를 쓸지 배열을 쓸지 감이 안오더라ㅋㅋㅋ

처음엔 int 배열을 쓰려고했는데 재귀호출할때 인덱스 접근이 애매해져서 힘들었다

그리고 입력이 A부터 순차적으로 들어오는 게 아니고 예시를 보면 D가 뒤에서 두번째에 입력돼서,,

 

 

일단 해결해야 할 문제

1) 입력이 숫자가 아닌 문자기 때문에 int 배열을 쓸지, char 배열을 쓸지

2-1) char 배열로 한다면 인덱스 접근은 어떻게 할지 (index-'A' 방식?)

2-2) int 배열로 한다면 재귀호출 시 인덱스 접근은 어떻게 할 지 ( 알파벳 순서대로 sort?)

3) . 입력은 어떻게 처리할지

4) A 노드부터 순차적으로 입력되는 게 아니라서 배열을 [26][3]배열을 써야 할 지 ( A, B, C 이렇게 저장하기 위해)

---

해결 방법

1) int 배열 사용

   - 인덱스 접근을 쉽게 하기 위해서 일단 int 배열로 선언했음

2) 노드의 알파벳 순서에 맞는 배열 위치에 접근해 저장

   - D 노드의 경우 배열의 [3][0]에 왼쪽 자식 노드 저장, [3][1]에 오른쪽 자식 노드 저장

3) . 입력은 -1로 처리

   - int 배열이기 때문에 숫자로 저장해줘야하는데 사용하지 않는 수인 -1로 처리해줌

4) 4번 문제는 2번 문제를 해결하면서 동시에 해결됨

 

 

전위 순회는 Root - L - R

중위 순회는 L - Root - R

후위 순회는 L - R - Root

* 순회명은 Root 기준

 

이론은 아래 블로그 참고

https://withhamit.tistory.com/282

트리 순회(전위 순회, 중위 순회, 후위 순회)

 

코드는 아래 블로그 참고

https://etyoungsu.tistory.com/74

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

 

 

#include <iostream>
using namespace std;
int tree[26][2];

// 전위
void preorder(int node) {
	if (node == -1) return;
	cout << char('A' + node);
	preorder(tree[node][0]);
	preorder(tree[node][1]);
}

// 중위
void inorder(int node) {
	if (node == -1) return;
	inorder(tree[node][0]);
	cout << char('A' + node);
	inorder(tree[node][1]);
}

// 후위
void postorder(int node) {
	if (node == -1) return;
	postorder(tree[node][0]);
	postorder(tree[node][1]);
	cout << char('A' + node);
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char a, b, c;
		cin >> a >> b >> c;
		if (b == '.') tree[a - 'A'][0] = -1;
		else tree[a - 'A'][0] = b - 'A';
		if (c == '.') tree[a - 'A'][1] = -1;
		else tree[a - 'A'][1] = c - 'A';
	}
	preorder(0);
	cout << endl;
	inorder(0);
	cout << endl;
	postorder(0);
	cout << endl;
}

 

구글링의 도움을 좀 받긴했지만ㅋㅋ

한번에 맞춤^~^