백준 1991 c++ "트리 순회" -PlusUltraCode-

https://www.acmicpc.net/submit/1991

 

 

 

[필자 사고]

 

전위순회, 중위순회, 후위순회를 묻는 문제이다.

전위 순회는 현재 노드부터 왼쪽 자식끝으로 이동후 더이상 이동할 수 없으면 자신과 형제노드를 탐방하고 다시 부모를 탐방하는 방식이다.

 

중위 순회는 이진 트리 형태로 되어있을 때 줄자를 이용하여 왼쪽부터 이동하여 먼저 줄자에 닿게 되는 부분으로 탐방하는 순서다.

 

후위 순회는 맨 왼쪽 노드의 형제노드를 탐방 후 그의 왼쪽 노드 와 부모노드를 탐방하는 순서이다.

 

이 문제에서 핵심은 재귀함수 형태로 왼쪽 끝 노드를 탐방 할 수 있냐 없느냐가 키 포인트이다.

필자는 재귀함수구현에 있어서 출력 부분의 위치를 햇갈려 다소 시간이 걸렸다.

 

아래는 코드 해설이다.

 

 

• validateAlpha 함수
  이 함수는 부모 노드와 자식 노드 간의 관계를 설정하는 역할을 한다.
  입력받은 부모 노드의 문자를 A를 기준으로 0부터 시작하는 숫자로 변환한 후, 자식 노드를 확인한다.
  만약 자식 노드가 .이라면 자식이 없다는 뜻이므로 -1을 저장하고, 그렇지 않으면 자식 노드의 문자를 동일하게 숫자로 변환하여 부모 노드의 자식으로 추가한다.
• Input 함수
  트리의 구조를 입력받아 arr 벡터에 저장하는 함수이다.
  첫 번째 입력값 N은 트리의 노드 수를 나타낸다. arr은 크기가 N인 2차원 벡터로, 각 노드의 왼쪽과 오른쪽 자식 노드를 저장한다.
  부모 노드와 그 자식 노드들을 입력받고, 이를 validateAlpha 함수를 통해 트리 구조로 변환한다.
•  
• preOrder, inOrder, postOrder 함수
  이 함수들은 각각 전위, 중위, 후위 순회를 수행하는 함수이다.
  preOrder는 현재 노드를 먼저 방문하고 왼쪽 자식과 오른쪽 자식을 순차적으로 방문하며,
  inOrder는 왼쪽 자식을 방문한 후 현재 노드를 방문하고, 마지막으로 오른쪽 자식을 방문한다.
  postOrder는 왼쪽 자식과 오른쪽 자식을 모두 방문한 후에 현재 노드를 방문한다.
  모든 함수는 재귀적으로 호출되며, 자식 노드가 없을 경우 -1을 만나면 종료한다.
•  
• GameStart 함수
  이 함수는 전위, 중위, 후위 순회를 차례대로 호출하여 각각의 결과를 출력한다

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<vector<int>> arr;
int N;

void validateAlpha(string parent, string str) {
	int parentNode = parent[0] - 'A';

	if (str == ".") {
		arr[parentNode].push_back(-1);
	}
	else {
		arr[parentNode].push_back(str[0] - 'A');
	}
}
void Input() {
	cin >> N;
	arr.resize(N);
	//A를 0이라고 간주

	for (int i = 0; i < N; i++) {
		string parent, leftChild, rightChild;
		cin >> parent >> leftChild >> rightChild;
		validateAlpha(parent, leftChild);
		validateAlpha(parent, rightChild);

	}
}

void preOrder(int nowNode) {
	
	if (nowNode == -1) {
		return;
	}

	char ch = 'A' + nowNode;
	cout << ch;

	int leftChild = arr[nowNode][0];
	int rightChild = arr[nowNode][1];

	preOrder(leftChild);
	preOrder(rightChild);


}
void inOrder(int nowNode) {

	if (nowNode == -1) {
		return;
	}

	int leftChild = arr[nowNode][0];
	int rightChild = arr[nowNode][1];

	inOrder(leftChild);


	char ch = 'A' + nowNode;
	cout << ch;

	inOrder(rightChild);
}
void postOrder(int nowNode) {

	if (nowNode == -1) {
		return;
	}

	int leftChild = arr[nowNode][0];

	int rightChild = arr[nowNode][1];
	

	postOrder(leftChild);

	postOrder(rightChild);

	char ch = 'A' + nowNode;
	cout << ch;

}


void GameStart() {
	preOrder(0);
	cout << '\n';
	inOrder(0);
	cout << '\n';
	postOrder(0);
}

int main(void) {
	Input();
	GameStart();
}