[코드트리] 트리 순회 C++

문제

https://www.codetree.ai/missions/9/problems/the-tree-traversal?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드

배열을 저장해서 그걸로 트리를 일차원 배열 형태로 만들어서 풀려고 했다. 트리를 일차원 배열형태로 만드는 게 조금 어려웠다. 그래서 포기할까 하고 기본 개념을 다시 보고 있었는데 아이디어가 떠올랐다. 그냥 순회만 하면 되는데, 굳이 트리를 만들 필요가 없겠다.

#include <iostream>
using namespace std;

const int MAX_N = 27;

int n;
char arr[MAX_N][3];

// node, left, right
void Preorder(int idx){
    char node=arr[idx][0], left=arr[idx][1], right=arr[idx][2];

    // node
    cout << node;
    // left
    for(int i=0; i<n; ++i){
        if(left=='.') break;
        if(arr[i][0]==left) Preorder(i);
    }
    // right
    for(int i=0; i<n; ++i){
        if(right=='.') break;
        if(arr[i][0]==right) Preorder(i);
    }
}
// left, node, right
void Inorder(int idx){
    char node=arr[idx][0], left=arr[idx][1], right=arr[idx][2];

    // left
    for(int i=0; i<n; ++i){
        if(left=='.') break;
        if(arr[i][0]==left) Inorder(i);
    }
    // node
    cout << node;
    // right
    for(int i=0; i<n; ++i){
        if(right=='.') break;
        if(arr[i][0]==right) Inorder(i);
    }
}

// left, right, node
void Postorder(int idx){
    char node=arr[idx][0], left=arr[idx][1], right=arr[idx][2];

    // left
    for(int i=0; i<n; ++i){
        if(left=='.') break;
        if(arr[i][0]==left) Postorder(i);
    }
    // right
    for(int i=0; i<n; ++i){
        if(right=='.') break;
        if(arr[i][0]==right) Postorder(i);
    }
    // node
    cout << node;
}

int main() {
    cin >> n;
    for(int i=0; i<n; ++i){
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    }

    Preorder(0);
    cout << '\n';
    Inorder(0);
    cout << '\n';
    Postorder(0);
    cout << '\n';
    return 0;
}