[BOJ] 1991 - 트리 순회

문제 링크

1991-트리순회

문제 설명

입력

• 이진 노드 갯수 N
• N개의 루트 -> 왼쪽 자식 노드 ->오른쪽 자식 노드

출력

• 전위 순회
• 중위 순회
• 후위 순회

문제 풀이

python

# 1991 트리 순회
import sys
input = sys.stdin.readline

n = int(input().strip())
tree = {}

for _ in range(n):
    root, left, right = input().strip().split()
    tree[root] = [left, right]

# 루트 -> 왼쪽 -> 오른쪽
def preorder(root):
    if root != '.':
        print(root, end='')
        preorder(tree[root][0])
        preorder(tree[root][1])

# 왼쪽 -> 루트 -> 오른쪽
def inorder(root):
    if root != '.':
        inorder(tree[root][0])
        print(root, end='')
        inorder(tree[root][1])

# 왼쪽 -> 오른쪽 -> 루트
def postorder(root):
    if root != '.':
        postorder(tree[root][0])
        postorder(tree[root][1])
        print(root, end='')

preorder('A')
print()
inorder('A')
print()
postorder('A')

• 입력 받은 루트와 자식 노드들을 하나로 묶어서 저장

• 각각의 순회에서 부모 노드가 ' . ' 면 넘어가고 아니면 순서대로 재귀 사용

• 다양한 테스트케이스가 주어져서 부모노드가 'A'가 아닌 경우에는 마지막 출력을 어떻게 해야할지 의문이다.

C++

#include<iostream>
using namespace std;

int T[27][2];
void postorder(int node) {
    if (node== -1)return;
    postorder(T[node][0]);
    postorder(T[node][1]);
    cout << char(node + 'A');
}

void inorder(int node) {
    if (node == -1)return;
    inorder(T[node][0]);
    cout << char(node + 'A');
    inorder(T[node][1]);
}

void preorder(int node) {
    if (node == -1)return;
    cout << char(node + 'A');
    preorder(T[node][0]);
    preorder(T[node][1]);
    
}

int main() {
    int n;
    cin >> n;
    char x, y, z;
    while (n--) {
        cin >> x >> y >> z;
        x -= 'A';
        if (y == '.')
            T[x][0] = -1;
        else
            T[x][0] = y - 'A';
        if (z == '.')
            T[x][1] = -1;
        else
            T[x][1] = z - 'A';
    }
    preorder(0);
    cout << '\n';
    inorder(0);
    cout << '\n';
    postorder(0);
    cout << '\n';
    return 0;
}

• 2중 배열 사용

• 진행하는 방식은 python이랑 동일

• python에서 마지막 출력에 대해서 해결하지 못한 부분이 해결됨