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

문제 링크 - https://www.acmicpc.net/problem/1991

🌱 문제

🌱 풀이

• 트리의 노드들을 입력받아서 전위 순회, 중위 순회, 후위 순회 했을 때의 결과를 출력하는 문제이다.
• pair<char,char> node[26] 라는 pair형 배열을 선언해서 first에는 왼쪽자식을, second에는 오른쪽 자식을 담았다.
• 배열의 인덱스는 양의 정수형 이어야 하므로, char-'A'에 해당하는 index의 first,second 자리에 자식 노드를 담았다.
• 전위 순회 : 현재 노드 출력 -> 왼쪽 자식 출력 -> 오른쪽 자식 출력
• 중위 순회 : 왼쪽 자식 출력 -> 현재 노드 출력 -> 오른쪽 자식 출력
• 후위 순회 : 왼쪽 자식 출력 -> 오른쪽 자식 출력 -> 현재 노드 출력

🌻 [C++ STL] pair 클래스 사용법

• 헤더파일은 #include <'utility'>에 존재
• 'algorithm' 헤더나 'vector'헤더에도 'utility'헤더가 포함되어 있음.
• 형태 : pair<type1, type2> p;
  • p.first : p의 첫번째 인자 반환
  • p.second : p의 두번째 인자 반환
  • make_pair(값1, 값2) : 값1, 값2를 한쌍으로 하는 pair 만들어서 반환.

pair<int, int> a;
    	a=make_pair(2,4);
        cout<< a.first;  // 2 출력
        cout<< a.second; // 4 출력 

🌱 코드

// 1991번: 트리 순회
#include <iostream>
using namespace std;
pair<char,char> node[26];
int n;

//전위순회
void preorder(char cur){
    if(cur=='.')
    return;
    
    cout<<cur;
    preorder(node[cur-'A'].first);
    preorder(node[cur-'A'].second);
}
//중위순회
void inorder(char cur){
    if(cur=='.')
    return;

    inorder(node[cur-'A'].first);
    cout<<cur;
    inorder(node[cur-'A'].second);
}
//후위순회
void postorder(char cur){
    if(cur=='.')
    return;

    postorder(node[cur-'A'].first);
    postorder(node[cur-'A'].second);
    cout<<cur;
}

int main(){
  
  cin>>n;
    for(int i=0; i<n; i++){
      char parent, left, right;
      cin>>parent>>left>>right;
      node[parent-'A'].first=left;
      node[parent-'A'].second=right;
    }
  
    preorder('A');
    cout<<"\n";
    inorder('A');
    cout<<"\n";
    postorder('A');
}

참고 사이트
https://ya-ya.tistory.com/91