[BOJ_C++] 1991번 : 트리 순회

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

typedef struct node {
    char left;
    char right;
};

node tree[27];

void inorder(char data);
void preorder(char data);
void postorder(char data);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; cin >> n;
    char root, left, right;
    for (int i = 0; i < n; i++) {
        cin >> root >> left >> right;
        tree[root].left = left;
        tree[root].right = right;
    }

    preorder('A'); printf("\n");
    inorder('A'); printf("\n");
    postorder('A'); printf("\n");
    
    return 0;
}

void inorder(char ptr) {
    if (ptr != '.') {
        inorder(tree[ptr].left);
        printf("%c", ptr);
        inorder(tree[ptr].right);
    }
}

void preorder(char ptr) {
    if (ptr != '.') {
        printf("%c", ptr);
        preorder(tree[ptr].left);
        preorder(tree[ptr].right);
    }
}

void postorder(char ptr) {
    if (ptr != '.') {
        postorder(tree[ptr].left);
        postorder(tree[ptr].right);
        printf("%c", ptr);
    }
}

• 노드의 최대 개수(27)만큼 node tree를 초기화 한다.
• 부모노드, 왼쪽 자식, 오른쪽 자식 순으로 입력을 받으므로, tree[부모노드].left = 왼쪽 자식, tree[부모노드].right = 오른쪽 자식이 되도록 트리를 초기화 한다.
• 전위 순회는 preorder로 루트 노드를 가장 먼저 방문하고 왼쪽 서브 트리, 오른쪽 서브 트리 순서로 탐색한다.
• 중위 순회는 inorder로 왼쪽 서브 트리, 루트 노드, 오른쪽 서브 트리 순서로 탐색한다.
• 후위 순회는 postorder로 왼쪽 서브 트리, 오른쪽 서브 트리, 루트 노드 순서로 탐색한다.
• 각 순회를 출력하고 프로그램을 종료한다. 

결과