Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

28. 트리

대표적인 그래프 종류 중 하나인 트리를 다뤄 봅시다.

Java / Python

6. 이진 검색 트리

5639번

이진 검색 트리의 전위 순회가 주어졌을 때 후위 순회를 구하는 문제

이번 문제는 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하는 문제이다.

전위 순회 : root -> l -> r
중위 순회 : l -> root -> r
후위 순회 : l -> r -> root

• Java

전위 순회의 경우 처음 탐색한 값이 항상 root이기 때문에 먼저 처음 값을 root로 선언한다. 반복문 내에 Node에 insert함수를 구현하고 현재 노드의 값보다 작으면 왼쪽 자식, 크면 오른쪽 자식으로 null일 경우 해당 노드를 생성하고, 아니면 재귀로 탐색하는 방식이다. 트리가 완성되면 후위 순회 함수를 구현해 왼쪽 자식, 오른쪽 자식, 현재 노드 순으로 탐색해 출력한다.

import java.io.*;
import java.util.*;

public class Main {
	static class Node {
		int num;
		Node left, right;

		Node(int num) {
			this.num = num;
		}

		Node(int num, Node left, Node right) {
			this.num = num;
			this.left = left;
			this.right = right;
		}

		void insert(int n) {
			if (n < this.num) {
				if (this.left == null) {
					this.left = new Node(n);
				} else
					this.left.insert(n);
			} else {
				if (this.right == null) {
					this.right = new Node(n);
				} else
					this.right.insert(n);
			}
		}
	}

	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		Node root = new Node(Integer.parseInt(br.readLine()));
		sb = new StringBuilder();

		String input;
		while ((input = br.readLine()) != null) {
			root.insert(Integer.parseInt(input));
		}
		postOrder(root);
		bw.write(sb.toString());

		bw.flush();
		br.close();
		bw.close();
	}

	public static void postOrder(Node node) {
		if (node == null)
			return;

		postOrder(node.left);
		postOrder(node.right);
		sb.append(node.num + "\n");
	}
}

• Python

후위 순회 : 왼쪽 오른쪽 루트순이므로 왼쪽, 오른쪽 호출한 뒤 찍기

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def post_order(start, end):
    if start > end:
        return

    root = pre_order[start] # 루트 노드
    idx = start + 1

    # root보다 커지는 지점을 찾기 
    while idx <= end:
        if pre_order[idx] > root:
            break
        idx += 1

    post_order(start + 1, idx - 1) # 왼쪽     
    post_order(idx, end) # 오른쪽

    print(root) # 후위 순회 root 마지막 출력


pre_order = []
while 1:
    try:
        pre_order.append(int(input()))
    # 예외 발생시 break
    except:
        break

post_order(0, len(pre_order) - 1)