[BaekJoon] 5639 이진 트리 검색 (Java)

1.  문제 링크

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

2.  문제

요약

• 이진 검색 트리는 아래 3개의 조건을 만족하는 이진 트리입니다.
  • 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작습니다.
  • 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 큽니다.
  • 왼쪽, 오른쪽 서브트리도 이진 검색 트리입니다.
• 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브트리를 순서대로 방문하면서 노드의 키를 출력하는 것을 전위 순회라고 합니다.
• 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 방문하면서 키를 출력하는 것을 후위 순회라고 합니다.
• 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 문제입니다.
• 입력: 트리를 전위 순회한 결과가 주어집니다. 노드에 들어있는 키의 값은 $10^6$보다 작은 양의 정수이고, 노드의 개수는 10,000개 이하입니다.
• 출력: 입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력합니다.

3.  소스코드

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

public class Main {
	static Node head;
	static ArrayList<Integer> nodes;
	public void RearSearch(Node node) {
		if(node == null)
			return;
		RearSearch(node.left);
		RearSearch(node.right);
		System.out.println(node.value);
	}
	
	public void makeTree() {
		head = new Node(nodes.get(0));
		for(int i = 1; i < nodes.size(); i++) {
			head.insert(nodes.get(i));
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		nodes = new ArrayList<Integer>();
		while((line = br.readLine()) != null) {
			nodes.add(Integer.parseInt(line));
		}
		br.close();
		Main m = new Main();
		m.makeTree();
		m.RearSearch(head);
	}
	
	public static class Node {
		Node left, right;
		int value;
		public Node(int value) {
			this.value = value;
			this.left = null;
			this.right = null;
		}
		public Node(int value, Node left, Node right) {
			this.value = value;
			this.left = left;
			this.right = right;
		}
		void insert(int value) {
			if(value < this.value) {
				if(this.left == null) {
					this.left = new Node(value);
				} else {
					this.left.insert(value);
				}
			} else {
				if(this.right == null) {
					this.right = new Node(value);
				} else {
					this.right.insert(value);
				}
			}
		}
	}
}

4.  접근

• 전위 순회는 루트부터 방문하여 왼쪽 서브트리, 오른쪽 서브트리를 탐색하기 때문에 주어진 전위 순회한 결과의 첫 번째 수는 루트 노드에 들어있는 키의 값입니다.
• 그렇기 때문에 첫 번째 수를 루트로 두고 이후에 주어진 수들을 이진 검색 트리의 조건에 맞게 넣어줌으로써 트리를 완성합니다.
• 수들을 넣는 함수는 현재 노드의 수보다 크면 오른쪽, 작으면 왼쪽으로 가도록 하고 마지막 레벨까지 내려와 이후에 비교할 노드가 없을 때에는 맞는 위치에 해당 노드를 넣도록 하였습니다.
• 이렇게 트리가 모두 완성되면 왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문하여 해당 노드들의 값을 출력하도록 하면 해당 문제를 해결할 수 있습니다.

1. 왼쪽 노드를 나타내는 left, 오른쪽 노드를 나타내는 right, 현재 노드의 키의 값을 나타내는 value를 멤버변수로 하고 트리에 새로운 노드를 추가하는 insert 메소드를 갖는 클래스 Node를 생성합니다.
   • insert 함수는 새로 추가하려는 노드의 값이 현재 노드의 값보다 작다면 재귀함수를 통해 왼쪽으로 보내고 현재 노드의 값보다 크다면 재귀함수를 통해 오른쪽으로 보냅니다. 그러다 노드가 위치해야하는 곳에 노드가 없다면 해당 위치에 추가하려는 노드를 추가합니다.
2. 전위 순회한 결과를 ArrayList nodes에 순서대로 넣습니다.
3. 루트를 나타내는 변수 head에 nodes의 첫 번째 값을 값으로 하는 노드를 생성하여 넣습니다.
4. nodes의 두 번째 값부터 마지막 값까지 반복문을 돌며 Node 클래스의 insert 함수를 통해 트리를 완성합니다.
5. head부터 시작하여 재귀함수를 통해 후위 순회를 진행하고 각 노드의 값을 출력합니다.