본문 바로가기
알고리즘

[백준 1991] 알고리즘 124일차 : 트리 순회

by SiO2whocode 2021. 8. 23.
반응형

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

 

1991번: 트리 순회

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자

www.acmicpc.net

C++ 트리

기본 Of 기본 트리 문제

이 문제는 트리의 세가지 순회 방법 전위순회, 중위순회, 후위순회를 다룬 문제입니다.

접근방법

사용한 자료구조 : 배열 (노드의 왼쪽자식과 오른쪽자식 정보를 담고 있는 2차원 배열)

재귀를 사용하여 자식 노드 방문

근데 이거 왜 실버1씩이나 되는거지

소스코드

#include <iostream>
using namespace std;
int adj[26][2];

void preorder_traverse(int root){
    cout << (char)(root+'A');
    int left, right;
    if((left = adj[root][0]) >= 0)
        preorder_traverse(left);
    if((right = adj[root][1]) >= 0)
        preorder_traverse(right);
}

void inorder_traverse(int root){
    int left, right;
    if((left = adj[root][0]) >= 0)
        inorder_traverse(left);
    cout << (char)(root+'A');
    if((right = adj[root][1]) >= 0)
        inorder_traverse(right);
}

void prorder_traverse(int root){
    int left, right;
    if((left = adj[root][0]) >= 0)
        prorder_traverse(left);
    if((right = adj[root][1]) >= 0)
        prorder_traverse(right);
    cout << (char)(root+'A');
}

int main(){
    //init & input
    int n;
    cin >> n;
    
    char node, left, right;
    for(int i = 0 ; i < n ; i++){
        cin >> node >> left >> right;
        adj[node-'A'][0] = left-'A';
        adj[node-'A'][1] = right-'A';
    }
    
    //process & output
    preorder_traverse(0);
    cout << "\n";
    inorder_traverse(0);
    cout << "\n";
    prorder_traverse(0);
    cout << "\n";

    return 0;
}
반응형

댓글0