백준(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;

}