[백준(BOJ)] 1991번: 트리 순회

입/출력

• 입력: 이진 트리의 노드의 개수 N, 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드
  • 항상 A가 루트 노드. 자식 노드가 없는 경우에는 .
• 출력: 첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력

 

트리 순회

• 전위 순회(Preorder): 노드 출력 -> 왼쪽 자식 노드 방문 -> 오른쪽 자식 노드 방문
• 중위 순회(Inorder): 왼쪽 자식 노드 방문 -> 노드 출력 -> 오른쪽 자식 노드 방문
• 후위 순회(Postorder): 왼쪽 자식 노드 방문 -> 오른쪽 자식 노드 방문 -> 노드 출력

 

제출 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Node{
    char left;
    char right;
};

vector<Node> tree(26);

void Preorder(char current){
    if(current=='.') return;
    
    cout << current;
    Preorder(tree[current-'A'].left);
    Preorder(tree[current-'A'].right);
}
void Inorder(char current){
    if(current=='.') return;
    
    Inorder(tree[current-'A'].left);
    cout << current;
    Inorder(tree[current-'A'].right);
}
void Postorder(char current){
    if(current=='.') return;
    
    Postorder(tree[current-'A'].left);
    Postorder(tree[current-'A'].right);
    cout << current;
}

int main(){
    int N;
    cin >> N;
    
    for(int i=0; i<N; i++){
        char root, left, right;
        cin >> root >> left >> right;

        tree[root-'A'].left = left;
        tree[root-'A'].right = right;
    }
    
    Preorder('A');
    cout << endl;
    Inorder('A');
    cout << endl;
    Postorder('A');
    cout << endl;
    
    return 0;
}

• 노드 구조체에 left, right를 char 형으로 저장. 알파벳 대문자는 ASCII 문자이면서 65부터 숫자값에 대응하므로 char형으로 저장
• 최대 26개의 노드를 가지므로 구조체는 vector로 26개 크기로 선언
• 각 root-'A' 위치에 left와 right 값을 저장함
• Preorder, Inorder, Postorder 알고리즘에 따라 트리 순회를 진행하고, 자식 노드 방문 시 tree[current-'A'].left, tree[current-'A'].right으로 방문

 

제출 결과