[백준,c++] 1991번 - 트리 순회

문제

1991번: 트리 순회

 

코드

#include <iostream>
using namespace std;

int N;
int tree[52][2];

void preorder(int curr){
    if(curr==-1) return;
    cout<<(char)(curr+65);
    preorder(tree[curr][0]);
    preorder(tree[curr][1]);
}

void inorder(int curr){
    if(curr==-1) return;
    inorder(tree[curr][0]);
    cout<<(char)(curr+65);
    inorder(tree[curr][1]);
}

void postorder(int curr){
    if(curr==-1) return;
    postorder(tree[curr][0]);
    postorder(tree[curr][1]);
    cout<<(char)(curr+65);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    
    while(N--){
        char a,b,c; cin>>a>>b>>c;
        a = a - 65;
        if(b =='.') tree[a][0]= -1;
        else tree[a][0]=b-65;
        if(c =='.') tree[a][1]= -1;
        else tree[a][1]=c-65;
    }
    
    preorder(0);    //전위 순회
    cout<<'\n';
    inorder(0);     //중위 순회
    cout<<'\n';
    postorder(0);   //후위 순회
    
}

 

풀이

각 노드의 이름은 A부터 차례대로 알파벳 대문자로 주어집니다. 따라서 int배열에 담기 위해 A의 아스키코드인 65를 빼주어 정수로 만들어 삽입했습니다. 그리고 각각 전위 순회, 중위 순회, 후위 순회에 대한 개념은 아래와 같습니다.

• 전위: 현재 노드 출력 -> 왼쪽 노드 순회 -> 오른쪽 노드 순회
• 중위: 왼쪽 노드 순회 -> 현재 노드 출력 -> 오른쪽 노드 순회
• 후위: 왼쪽 노드 순회 -> 오른쪽 노드 순회 -> 현재 노드 출력

그렇기에 적절하게 print문 위치를 넣어주어 문제를 해결할 수 있습니다.