[백준] 1991 트리 순회 - 트리, 재귀

[ 문제링크 ]

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

 

🚩 조건

1. 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력
2. 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어짐
3. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어짐
4. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 됨. 자식 노드가 없는 경우에는 .으로 표현

 

 

🚩 접근

트리 -> 구조체로 구현

순회 -> 재귀함수로 구현

 

 

🚩 시행착오

- 구조체 선언

struct NODE{
    char root;
    char left;
    char right;
};

 

- 구조체 변수 선언 후 접근

NODE node;
node.root = f;
node.left = s;
node.right = t;

 

- 아래와 같이 구조체 초기화도 가능

NODE node = {f, s, t};

 

 

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct NODE{
    char root;
    char left;
    char right;
};
NODE nodeArr[26];

void preorder(char root){
    cout<<root;
    if(nodeArr[root-'0'].left != '.')
        preorder(nodeArr[root-'0'].left);
    if(nodeArr[root-'0'].right != '.')
        preorder(nodeArr[root-'0'].right);
}

void inorder(char root){
    if(nodeArr[root-'0'].left != '.')
        inorder(nodeArr[root-'0'].left);
    cout<<root;
    if(nodeArr[root-'0'].right != '.')
        inorder(nodeArr[root-'0'].right);
}

void postorder(char root){
    if(nodeArr[root-'0'].left != '.')
        postorder(nodeArr[root-'0'].left);
    if(nodeArr[root-'0'].right != '.')
        postorder(nodeArr[root-'0'].right);
    cout<<root;
}

int main(){
    int N;
    cin>>N;
    char f, s, t;
    for(int i=0;i<N;i++){
        cin>>f>>s>>t;
        NODE node;
        node.root = f;
        node.left = s;
        node.right = t;
        nodeArr[f-'0'] = node;
    }
    
    preorder('A');
    cout << "\n";
    inorder('A');
    cout << "\n";
    postorder('A');
}