백준 1991번, 트리 순회(C, C++)

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

1991번: 트리 순회

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int N;
char X;
char Y;
char Z;
int parent[27][2];

void preorder(char root){
    if(root =='.'){
        return;
    }else{
        cout<<root;
        preorder(parent[root-'A'][0]);
        preorder(parent[root-'A'][1]);
    }
}
void inorder(char root){
    if(root == '.'){
        return;
    }else{
        inorder(parent[root - 'A'][0]);
        cout << root;
        inorder(parent[root - 'A'][1]);
    }
}

void postorder(char root){
    if (root == '.'){
        return;
    }else{
        postorder(parent[root - 'A'][0]);
        postorder(parent[root - 'A'][1]);
        cout << root;
    }
}

int main(){
    cin>> N;
    for(int i = 1; i <= N; i++){
        cin >> X >> Y >> Z;
        parent[X - 'A'][0] = Y;
        parent[X - 'A'][1] = Z;
    }
    preorder('A');
    cout<<'\n';
    inorder('A');
    cout<<'\n';
    postorder('A');
    cout<<'\n';

    return 0;
}

 

 

전위 순회를 하면

A-B-D-C-E-F-G순 (루트) (왼쪽 자식) (오른쪽 자식)

중위 순회를 하게되면

D-B-A-E-C-F-G순 (왼쪽 자식) (루트) (오른쪽 자식)

후위 순회

D-B-E-G-F-C-A순이다. (왼쪽 자식) (오른쪽 자식) (루트)

parents[27][0]을 왼쪽 노드, parents[27][1]을 오른쪽 노드로 설정합니다.

재귀함수를 이용해 전위 중위 후위 순회를 하는 재귀함수를 설정하는데

문제에서 "."으로 공백을 표현한다하였으니 더이상 진행하지않게 return;으로 함수를 종료합니다.

이제 입력에서 넣은 알파벳을 배열에 수로 표현하기 위해 아스키코드를 이용하여 X - 'A'를 빼주게 되면

for문이 돌아가게 되었을 때 각 N개씩 왼쪽, 오른쪽의 값이 정해지게됩니다.

즉, A B C 입력을 받게 되면 A라는 노드의 왼쪽은 B, 오른쪽은 C의 값이 정해집니다.

​