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

#문제

1991번: 트리 순회

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

1991번: 트리 순회

 

---

#접근방법

먼저 입력값으로 트리를 만들고 재귀함수로 전위, 중위, 후위 순회한 결과를 출력하면 된다.

반응형

---

#풀이

#include <stdio.h>

int arr[26][2];

void pre(int x){
	if(x<0) return;
	
	printf("%c",x+65);
	pre(arr[x][0]);
	pre(arr[x][1]);
	
	return;
}

void in(int x){
	if(x<0) return;
	
	in(arr[x][0]);
	printf("%c",x+65);
	in(arr[x][1]);
	
	return;
}

void post(int x){
	if(x<0) return;
	
	post(arr[x][0]);
	post(arr[x][1]);
	printf("%c",x+65);
	
	return;
}

int main(){
	int n;
	char a,b,c;
	
	scanf("%d",&n);
	
	for(int i=0;i<n;i++){
		scanf("\n%c \n%c \n%c",&a,&b,&c);
		
		arr[a-65][0] = b-65;
		arr[a-65][1] = c-65;
	}
	
	pre(0); printf("\n");
	in(0); printf("\n");
	post(0); printf("\n");
	
	return 0;
}

 

입력값을 트리의 형태로 만들기 위해 A ~ Z를 0 ~ 25이라는 값으로 생각하고

 

A의 아스키 코드는 65이므로 arr[a-65][0] = b-65와 arr[a-65][1] = c-65의 형태로 저장을 해준다.

 

arr[a-65][0]에서 0의 의미는 왼쪽 자식이라는 의미고 arr[a-65][1]에서 1의 의미는 오른쪽 자식이라는 의미이다.

 

A ~ Z의 값 말고도 . 이라는 값이 들어오는데 이것의 아스키 코드는 46이므로 arr배열에 들어있는 값 중에 음수값이 있으면 그것은 자식이 없다는 뜻이다.

 

전위, 중위, 후위 순회의 함수는 각각 pre, in, post로 이름을 지정해주었다.

 

전위 순회 함수 pre함수를 위 코드에서 보면 루트 출력 -> 왼쪽 자식 탐색 -> 오른쪽 자식 탐색 순으로 재귀함수가 설계되어있다.

 

이 때, 조건문으로 음수값이 들어오면 자식이 없다는 뜻이므로 탐색을 종료 시켜주었다.

 

pre, in, post의 함수들은 비슷하게 생겼으나 루트 출력, 왼쪽 자식 탐색, 오른쪽 자식 탐색의 코드 3줄을 전위, 중위, 후위 순회를 하는 방법에 따라 코드를 변경 시켜주어서 정답을 구해주었다.

 

 

---

#성능

---

#정리

트리를 구현할 수 있는 구현력, 재귀 함수로 전위, 중위, 후위 순회를 하는 알고리즘을 짜는 능력을 가지고 있으면 풀 수 있는 문제였다.