백준 1991. 트리 순회

알고리즘 기초 문제 중 620 - 트리

트리 순회

1. 간단 설명

트리를 입력받고, 전위 중위 후위 순으로 출력하는 문제

2. 예시

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

	A
	| \
	B	C
	|	| \
	D	E	F
			|
			G

전위 순회 - 루트, 왼쪽, 오른쪽 A B D C E F G

중위 순회 - 왼쪽, 루트, 오른쪽 D B A E C F G

후위 순회 - 왼쪽, 오른쪽, 루트 D B E G F C A

3. 알고리즘

먼저 입력을 어떻게 저장할 것인가, 그리고 이를 순회하는 방법을 어떻게 구현할 것인가로 나눔

1. 어떤 자료구조를 이용하여 저장할지

• 해시맵, 그래프, 링크드리스트를 이용하여, 각 노드에 연결된 노드를 저장하는 방법

• 링크드 리스트를 사용한다면 2차원 벡터로 vector< vector<char> > graph graph[A] -> B, C 이런식으로 저장 가능

• 구조체 이용

  • 노드라는 구조체를 만들어서 노드의 이름과, 왼쪽, 오른쪽 포인터를 저장

구조체를 이용하는 방법이 더 간단해보여서 이를 이용할 예정

2. 순회 방법 구현

각 순회는 재귀적으로 구현할 수 있다

1) 전위 순회

void pre_order(int node){
	현재 노드 출력
	왼쪽 연결된 노드 따라 들어가기
	오른쪽 연결된 노드 따라 들어가기
}

2) 중위 순회

void mid_order(int node){
	왼쪽 연결된 노드 따라 들어가기
	현재 노드 출력
	오른쪽 연결된 노드 따라 들어가기
}

3) 후위 순회

void post_order(int node){
	왼쪽 연결 노드 따라 들어가기
	오른쪽 연결 노드 따라 들어가기
	현재 노드 출력
}

이런식으로 언제 출력을 하느냐에 따라 전위, 중위, 후위 순회를 구현할 수 있다

주의사항

• 이진 트리 노드의 개수는 최대 26개고, A부터 차례대로 알파벳 대문자로 매겨진다
  • 즉, 입력 중에 A C B처럼 왼쪽 노드가 오른쪽 노드보다 알파벳 순서가 느린 경우는 없음

4. 소스코드

#include <iostream>

using namespace std;

int N;

struct Node {
	char name;
	Node* left = nullptr; // Q1. NULL과 nullptr 차이는?
	Node* right = NULL;
} node[27];

// 전위 순회
void pre_order(Node* cur) {
	// 현재 노드 출력
	cout << cur->name;

	// 왼쪽 노드 탐색
	if (cur->left != nullptr) {
		pre_order(cur->left);
	}

	// 오른쪽 자식 탐색
	if (cur->right != nullptr) {
		pre_order(cur->right);
	}
}

// 중위 순회
void mid_order(Node* cur) {
	// 왼쪽 노드 탐색
	if (cur->left != nullptr) {
		mid_order(cur->left);
	}

	// 현재 노드 출력
	cout << cur->name;

	// 오른쪽 자식 탐색
	if (cur->right != nullptr) {
		mid_order(cur->right);
	}
}

// 후위 순회
void post_order(Node* cur) {
	// 왼쪽 노드 탐색
	if (cur->left != nullptr) {
		post_order(cur->left);
	}

	// 왼쪽 노드 탐색
	if (cur->right != nullptr) {
		post_order(cur->right);
	}

	// 현재 노드 출력
	cout << cur->name;
}


int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		char name, left, right;
		cin >> name >> left >> right;
		node[name - 'A'].name = name;
		if (left != '.') {
			node[name - 'A'].left = &node[left -'A'];
		}
		if (right != '.') {
			node[name - 'A'].right = &node[right - 'A'];
		}
	}

	pre_order(&node[0]);
	cout << '\n';
	mid_order(&node[0]);
	cout << '\n';
	post_order(&node[0]);
	cout << '\n';

	return 0;
}

배운점

---

1. NULL과 nullptr차이

• NULL
  • C++11이전 버전에서는 컴파일러가 NULL을 포인터가 아니라 정수 0과 동일하게 여김. 즉 정수형 상수 타입
  • 일반적으로 #define NULL 0 또는 #define NULL ((void*)0) 로 정의되어있음
  • NULL을 정수와 비교하거나 잘못된 타입으로 사용할 가능성이 있음
• nullptr
  • C++11에서 도입된 키워드로 std::nullptr_t 타입의 값. 명시적으로 포인터를 나타내는 타입
  • 다른 정수 타입과 혼동되지 않아, 타입의 안정성을 보장한다

즉, 포인터를 사용할 때는 NULL 대신 nullptr를 사용할 것을 권장함

그러나 C와의 호환성을 유지해야하거나, C++11 이전의 레거시 코드를 유지보수하는 경우, NULL을 사용한다

2. 검사 시점

다음 두 함수를 보자

void pre_order(Node* cur) {
    if (cur == nullptr) return;

    cout << cur->name; // 현재 노드 출력
    pre_order(cur->left); // 왼쪽 노드 탐색
    pre_order(cur->right); // 오른쪽 노드 탐색
}

void pre_order(Node* cur) {
	cout << cur->name;

	if (cur->left != NULL) 
		pre_order(cur->left);

	if (cur->right != NULL) 
		pre_order(cur->right);
}

두 함수는 모두 전위 탐색을 수행하는 함수지만, 검사 시점이 다르다

첫번째 함수는 현재 노드가 nullptr인지 체크한 뒤, 맞다면 종료한다

두번째 함수는 자식 노드로 들어가기 전에 nullptr 검사를 수행한다

첫번째 함수는 코드가 간결하지만, 모든 노드에서 nullptr 검사를 위해 재귀호출을 한번 더 수행하게 된다

두번째 함수는 코드가 약간 가독성이 떨어지지만, 자식노드에 대해 재귀호출을 수행하지 않으므로

메모리와 시간 측면에서 효율적일 수 있다