백준 1991 트리 순회 C++

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

1991번: 트리 순회

---

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

---

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

---

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

---

이진 트리?

이진트리는 최대 2개의 자식을 가지는 트리를 의미한다.

이진트리의 노드는 오직 2명의 자식을 갖을 수 있기 떄문에, 우리는 이 자식을 왼쪽자식, 오른쪽 자식이라고 부른다.

이진트리(자식이2명!)

 이진 트리는 다음과 같은 부분을 갖을 수 있다.

1. Data 
2. Pointer to left child (왼쪽 자식에 대한 포인터)
3. Pointer to right child(오른쪽 자식에 대한 포인터)

먼저 이진트리의 구조체를 정의하였다. 문제에서 문자열의 대문자만 노드의 원소로 가지며, A가 루트노드가 되기 떄문에

char data,char left,char right를 통해서 트리 구조체를 선언한다. 그 후 n만큼 입력받으면서 왼쪽 자식, 오른쪽 자식, 노드의 값을 넣어주고,

전위 순회(루트->왼쪽자식->오른쪽자식), 중위 순회(왼쪽자식->루트->오른쪽 자식),

후위순회(왼쪽자식->오른쪽자식->루트)를 재귀적으로 구현하였다.

---

#include <iostream>
using namespace std;
//백준 1991 트리 순회

struct TREE{ //트리를 표현하는 구조체 ->'\0' NULL문자로 초기화
    char left = '\0';
    char right = '\0';
    char data = '\0';
};
 
typedef struct TREE tree;
 
 
tree arr[27];
 
 
void preorder(tree a){
    // 전위순회(루트 왼쪽 오른쪽)
    if(a.data == '\0' || a.data == '.'){
        return;
    }
    cout << a.data;
    if(a.left != '\0' && a.left != '.'){
        preorder(arr[a.left-'A']);
    }
    if(a.right != '\0' && a.right != '.'){
        preorder(arr[a.right-'A']);
    }
}
 
void order(tree a){ 
    // 중위순회(왼쪽 루트 오른쪽)
 
 
 
    if(a.left != '\0' && a.left != '.'){
        order(arr[a.left-'A']);
    }
     if(a.data == '\0' || a.data == '.'){
        return;
    }
    if(a.data != '\0' && a.data != '.'){
        cout << a.data;
    }
 
    if(a.right != '\0' && a.right != '.'){
        order(arr[a.right-'A']);
    }
}
 
void lastorder(tree a){ 
    //후위순회(왼쪽 오른쪽 루트)
 
    if(a.left != '\0' && a.left != '.'){
        lastorder(arr[a.left-'A']);
    }
    if(a.right != '\0' && a.right != '.'){
        lastorder(arr[a.right-'A']);
    }
    if(a.data != '\0' && a.data != '.'){
        cout << a.data;
    }
}
 
int main(void){
 
 
    int n;
    cin >> n;
    /*노드의 데이터,왼쪽자식,오른쪽 자식 입력받아서 저장*/
    for(int i = 0;i<n;i++){
        char a,b,c;
        cin >> a >> b >> c;
        arr[a-'A'].data = a;
        arr[a-'A'].left = b;
        arr[a-'A'].right = c;
    }
    
    /*각각 전위,중위,후위 순회*/
    preorder(arr['A'-'A']);
    cout << '\n';
    order(arr['A'-'A']);
    cout << '\n';
    lastorder(arr['A'-'A']);
 
 
}