[Baekjoon] 1991번 : 트리 순회

1. 문제

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

• 트리, 구현 문제

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

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

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

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

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

// 예제 입력 1
7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

// 예제 출력 1
ABDCEFG
DBAECFG
DBEGFCA

2. 핵심 아이디어

• 전위 순회 : 루트 출력 -> 왼쪽 자식 -> 오른쪽 자식
• 중위 순회 : 왼쪽 자식 -> 루트 출력 -> 오른쪽 자식
• 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 루트 출력

3. Python 문제풀이

import sys
input = sys.stdin.readline

class Node :
  def __init__(self, data, left, right) :
    self.data = data
    self.left = left
    self.right = right

def pre_order(node) :
  print(node.data, end = '')
  if node.left != '.' :
    pre_order(tree[node.left])
  if node.right != '.' :
    pre_order(tree[node.right])

def in_order(node) :
  if node.left != '.' :
    in_order(tree[node.left])
  print(node.data, end = '')
  if node.right != '.' :
    in_order(tree[node.right])

def post_order(node) :
  if node.left != '.' :
    post_order(tree[node.left])
  if node.right != '.' :
    post_order(tree[node.right])
  print(node.data, end = '')

n = int(input())
tree = {}
for i in range(n) :
  data, left, right = input().split()
  tree[data] = Node(data, left, right)

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])

4. Java 문제풀이

import java.util.*;

class Node {
  char data;
  Node left, right;

  public Node(char data) {
    this.data = data;
  }
}

class Tree {
  Node root;

  public void Add(char data, char left_data, char right_data) {
    if (root == null) {
      if (data != '.') root = new Node(data);
      if (left_data != '.') root.left = new Node(left_data);
      if (right_data != '.') root.right = new Node(right_data);
    }
    else Search(root, data, left_data, right_data);
  }

  public void Search(Node root, char data, char left_data, char right_data) {
    if (root == null) return;
    else if (root.data == data) {
      if (left_data != '.') root.left = new Node(left_data);
      if (right_data != '.') root.right = new Node(right_data);
    }
    else {
      Search(root.left, data, left_data, right_data);
      Search(root.right, data, left_data, right_data);
    }
  }

  public void PreOrder(Node root) {
    System.out.print(root.data);
    if (root.left != null) PreOrder(root.left);
    if (root.right != null) PreOrder(root.right);
  }

  public void InOrder(Node root) {
    if (root.left != null) InOrder(root.left);
    System.out.print(root.data);
    if (root.right != null) InOrder(root.right);
  }

  public void PostOrder(Node root) {
    if (root.left != null) PostOrder(root.left);
    if (root.right != null) PostOrder(root.right);
    System.out.print(root.data);
  }

}
class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    Tree tree = new Tree();
    for (int i=0; i<n; i++) {
      tree.Add(sc.next().charAt(0), sc.next().charAt(0), sc.next().charAt(0));
    }

    tree.PreOrder(tree.root);
    System.out.println();
    tree.InOrder(tree.root);
    System.out.println();
    tree.PostOrder(tree.root);
  }
}