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

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

1991번: 트리 순회

 

문제 요약

 

이진트리를 입력받아 전위 순회, 중위 순회, 후위 순회 결과 출력하는 프로그램

 

범위

 

이진트리의 노드의 개수 N(1 ≤ N ≤ 26)

 

 

 

---

 

 

전위 순회, 중위 순회, 후위 순회 각 함수를 따로 만들어서 순서대로 출력해줬다. 각 순회는 문제에도 나와있듯이

 

 - 전위 순회: 루트 - 왼쪽 - 오른쪽

 - 중위 순회: 왼쪽 - 루트 - 오른쪽

 - 후위 순회: 왼쪽 - 오른쪽 - 루트

 

순이므로 이것에 맞춰서 재귀 호출을 해주면 된다. 루트에 다다르는 순서에 맞춰서 해당 노드의 값을 출력해주면 된다. 

이때, 알파벳 대문자 char 형으로 받아서 맨 처음에 받은 알파벳을 루트로 설정해준다(root)

이진트리만 받기 때문에 column은 2개만 받는다. 이진트리의 자식은 최대 2개뿐이므로. 

 

재귀함수를 사용할 때, 주의할 점은 꼭 기저 조건(재귀 함수를 끝낼 조건)을 넣어줘야 한다는 것이다.

pre/in/post_order 함수에도 만약 해당 값이 ' . ' 라면 반환하도록 조건을 넣어줬다. ' . '는 leaf node를 의미하기 때문에 더 들어갈 필요도, 들어갈 수도 없다. 

 

#include <iostream>
using namespace std;
int n;
char c1, c2, c3, root;
char graph[55][2];

void input(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> c1 >> c2 >> c3;
        if(i==0) root = c1;
        graph[c1-'A'][0] = c2; 
        graph[c1-'A'][1] = c3; 
    }
}

void pre_order(char x){
    int i = x-'A';
    if(x == '.') return;
    cout << x;
    pre_order(graph[i][0]); //LEFT
    pre_order(graph[i][1]); //RIGHT
}

void in_order(char x){
    int i = x-'A';
    if(x == '.') return;
    in_order(graph[i][0]); //LEFT
    cout << x;
    in_order(graph[i][1]); //RIGHT
}

void post_order(char x){
    int i = x-'A';
    if(x == '.') return;
    post_order(graph[i][0]); //LEFT
    post_order(graph[i][1]); //RIGHT
    cout << x;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    pre_order(root);  cout << '\n';
    in_order(root);   cout << '\n';
    post_order(root); cout << '\n';
    return 0;
}

 

 

처음에는 벡터로 했는데, 메모리 초과가 나와서 배열로 바꿨다.

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!