/ BOJ

BOJ_1708_이진검색트리_JAVA

문제 : 이진검색트리

링크 : BOJ_1708_이진검색트리

접근 방식

이진 검색 트리의 조건을 만족하는 트리의 전위 순회 결과가 주어졌을 때, 이 트리의 후위 순회 결과를 구하면 되는 문제이다.

이진 검색 트리의 조건은 다음과 같다.

  1. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
  2. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
  3. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class BOJ_1708_이진검색트리 {
	static class Node {
		int v;
		Node left;
		Node right;

		public Node(int v) {
			this.v = v;
		}

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

		void insert(int v) {

			// 현재 정점보다 더 작은 수일 경우
			if (this.v > v) {
				// 왼쪽 자식에 노드가 없다면
				if (this.left == null) {
					// 자식으로 노드 추가
					this.left = new Node(v);
				} else {
					// 노드가 있다면 그 자식의 insert 메서드 호출
					this.left.insert(v);
				}
				// 현재 정점보다 더 큰 수일 경우
			} else {
				// 오른쪽 자식에 노드가 없다면
				if (this.right == null) {
					// 자식으로 노드 추가
					this.right = new Node(v);
				} else {
					// 노드가 있다면 오른쪽 자식 노드에서 insert 메서드 호출
					this.right.insert(v);
				}
			}

		}

	}

	public static void main(String[] args) {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Node root = null;
		try {

			root = new Node(Integer.parseInt(in.readLine()));
			while (true) {
				int node = Integer.parseInt(in.readLine());
				root.insert(node);
			}
		} catch (Exception e) {

		}
		post(root);
	}

	// 후위순회 왼 오 중
	static void post(Node node) {
		Node L = node.left;
		Node R = node.right;
		if (L != null) {
			post(node.left);
		}
		if (R != null) {
			post(node.right);
		}
		System.out.println((node.v));
	}

}

이진검색트리의 전위순회 결과를 읽어와서 트리를 만들고, 만들어진 트리를 후위순회하여 출력했다.