예제

1991번: 트리 순회

트리 순회의 가장 기초적인 문제이다.

개념

트리 순회 - 위키백과, 우리 모두의 백과사전

Preorder Traversal(전위 순회)

root → left → right

Inorder Traversal(중위 순회)

left → root → right

Postorder Traversal(후위 순회)

left → right → root

Level-Order Traversal(레벨 순서 순회)

노드를 낮은 레벨부터 차례대로 순회한다.

Python

import sys

def preorder(node):
    global tree
    if node is '.':
        return
    print(node, end='')
    preorder(tree[node][0])
    preorder(tree[node][1])

def inorder(node):
    global tree
    if node is '.':
        return
    inorder(tree[node][0])
    print(node, end='')
    inorder(tree[node][1])

def postorder(node):
    global tree
    if node is '.':
        return
    postorder(tree[node][0])
    postorder(tree[node][1])
    print(node, end='')

n = int(sys.stdin.readline())
tree = dict()

for _ in range(n):
    s = sys.stdin.readline()
    tree[s[0]] = (s[2], s[4])

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

C

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
    char left;
    char right;
} node;

void preorder(node* tree, char root) {
    if (root == '.') return;
    printf("%c", root);
    preorder(tree, tree[root - 'A'].left);
    preorder(tree, tree[root - 'A'].right);
}

void inorder(node* tree, char root) {
    if (root == '.') return;
    inorder(tree, tree[root - 'A'].left);
    printf("%c", root);
    inorder(tree, tree[root - 'A'].right);
}

void postorder(node* tree, char root) {
    if (root == '.') return;
    postorder(tree, tree[root - 'A'].left);
    postorder(tree, tree[root - 'A'].right);
    printf("%c", root);
}

int main() {
    int n;
    scanf("%d", &n);

    node* tree = (node*)calloc(n, sizeof(node));
    int i;
    char a, b, c, d;
    for (i = 0; i < n; i++) {
        scanf(" %c %c %c", &a, &b, &c);

        tree[a - 'A'].left = b;
        tree[a - 'A'].right = c;
    }

    preorder(tree, 'A');
    printf("\\n");
    inorder(tree, 'A');
    printf("\\n");
    postorder(tree, 'A');
    printf("\\n");

    free(tree);
    return 0;
}

C++