[알고리즘 / 백준] 1991 - 트리 순회

 

문제는 위와 같으며 입력되는 트리 데이터를 {부모 노드: [왼쪽 자식 노드, 오른쪽 자식 노드], ...} 형태로 저장한 다음 전위, 중위, 후위 순회를 재귀 함수로 실행하면서 노드를 저장해 출력하는 방식으로 문제를 해결하였습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin


def preorder(array, start_node):
    global pre
    pre += start_node

    left = array[start_node][0]
    right = array[start_node][1]

    if left != ".":
        preorder(array, left)

    if right != ".":
        preorder(array, right)


def inorder(array, start_node):
    global inord

    left = array[start_node][0]
    right = array[start_node][1]

    if left != ".":
        inorder(array, left)

    inord += start_node

    if right != ".":
        inorder(array, right)


def postorder(array, start_node):
    global post

    left = array[start_node][0]
    right = array[start_node][1]

    if left != ".":
        postorder(array, left)

    if right != ".":
        postorder(array, right)

    post += start_node


n = int(stdin.readline())
pre = ""
inord = ""
post = ""

binary_tree = dict()
for _ in range(n):
    inputs = stdin.readline().split()
    binary_tree[inputs[0]] = [inputs[1], inputs[2]]

preorder(binary_tree, "A")
inorder(binary_tree, "A")
postorder(binary_tree, "A")

print(pre)
print(inord)
print(post)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static StringBuilder pre = new StringBuilder();
    static StringBuilder ino = new StringBuilder();
    static StringBuilder post = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        Map<String, String[]> binaryTree = new HashMap();

        for (int i = 0; i < n; i++) {
            String[] inputs = br.readLine().split(" ");
            String[] values = {inputs[1], inputs[2]};
            binaryTree.put(inputs[0], values);
        }

        preOrder(binaryTree, "A");
        inOrder(binaryTree, "A");
        postOrder(binaryTree, "A");

        System.out.println(pre);
        System.out.println(ino);
        System.out.println(post);
    }

    private static void preOrder(Map<String, String[]> tree, String startNode) {
        pre.append(startNode);

        if (!".".equals(tree.get(startNode)[0])) {
            preOrder(tree, tree.get(startNode)[0]);
        }

        if (!".".equals(tree.get(startNode)[1])) {
            preOrder(tree, tree.get(startNode)[1]);
        }
    }

    private static void inOrder(Map<String, String[]> tree, String startNode) {
        if (!".".equals(tree.get(startNode)[0])) {
            inOrder(tree, tree.get(startNode)[0]);
        }

        ino.append(startNode);

        if (!".".equals(tree.get(startNode)[1])) {
            inOrder(tree, tree.get(startNode)[1]);
        }
    }

    private static void postOrder(Map<String, String[]> tree, String startNode) {
        if (!".".equals(tree.get(startNode)[0])) {
            postOrder(tree, tree.get(startNode)[0]);
        }

        if (!".".equals(tree.get(startNode)[1])) {
            postOrder(tree, tree.get(startNode)[1]);
        }

        post.append(startNode);
    }
}