백준(BOJ) 1991번 트리 순회
문제: https://www.acmicpc.net/problem/1991
이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
예를 들어 위와 같은 이진 트리가 입력되면,
- 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
- 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
- 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
가 된다.
나의 풀이:
입력에 항상 A가 루트 노드가 된다라는 조건이 있기 때문에 따로 루트 노드를 구할 필요가 없는 문제였다. 배열을 만들어서 A- Z를 인덱
스 [0] ~ [26] 으로 생각하고 자식 노드들을 넣는다. 순회 방식은 자료구조에서 배웠던 것 처럼 preOrder : V L R // InOrder L V R
// postORder L R V 식으로 순회하며 답을 출력한다. 순회하면서 '.'이 온다면 NULL 이라는 의미임으로 탐색을 종료한다.
'A'- 'A' = 0
0 + 'A' = 'A'
코드 ( C ++ )
#include <iostream>
#include <vector>
using namespace std;
int N;
const int MAX = 26;
int parent[MAX];
vector<vector<char>> Tree;
void preOrder(char root)
{
// '.' 이라면 탐색종료
if (root == '.')
return;
char left =Tree[root-'A'][0];
char right =Tree[root-'A'][1];
printf("%c", root);
preOrder(left);
preOrder(right);
}
void InOrder(char root)
{
if (root == '.')
return;
// [0] 이 왼쪽 , [1]이 오른쪽 자식이 될 것
char left = Tree[root - 'A'][0];
char right = Tree[root - 'A'][1];
InOrder(left);
printf("%c", root);
InOrder(right);
}
void postOrder(char root)
{
if (root == '.')
return;
char left = Tree[root - 'A'][0];
char right = Tree[root - 'A'][1];
postOrder(left);
postOrder(right);
printf("%c", root);
}
int main()
{
cin >> N;
Tree = vector<vector<char>>(N, vector<char>());
for (int i = 0; i < N; ++i)
{
char a, b, c;
cin >> a >> b >> c;
// 왼쪽자식, 오른쪽자식을 넣어준다.
Tree[a - 'A'].push_back(b);
Tree[a - 'A'].push_back(c);
}
preOrder(0 + 'A');
cout << endl;
InOrder(0 + 'A');
cout << endl;
postOrder(0 + 'A');
return 0;
}
