백준 5639. 이진 검색 트리

 

www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

문제제목 : 이진검색트리

문제난이도 : 실버1

문제유형 : 이진트리, 재귀

 

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

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

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

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

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

코드

//재귀X
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B5639 {
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Tree tree = new Tree();
	
        String input = "";
        while((input = br.readLine()) != null) {
        	int data = Integer.parseInt(input);
            tree.add(data);
        }
        tree.postOrder(tree.root);
	}
}

class Tree {
	Node root;
	
	//data 삽입
	public void add(int data) {
		if (root == null) {
			Node node = new Node(data);
			root = node;
		} else {
			search(root, data);
		}
	}
	
	public void search(Node root, int data) {
		Node p = null;
		Node t = root;
		Node node = new Node(data);
		
		while (t != null) {
			if (t.data == data) return;
			p = t;
			if (t.data < data) {
				t = t.right;
			} else {
				t = t.left;
			}
		}
		
		if (p != null) {
			if (p.data < data) {
				p.right = node;
			} else {
				p.left = node;
			}
		} else {
			root = node;
		}
	}
	
	public void postOrder(Node root) {
		if (root.left != null) postOrder(root.left);
		if (root.right != null) postOrder(root.right);
		System.out.println(root.data);
	}
}

class Node {
	int data;
	Node left;
	Node right;	
	
	public Node (int data){
		this.data = data;
		left = null;
		right = null;
	}
}

 

풀이아이디어

1. 전위순회한 결과 순서대로 트리에 삽입하면 올바른 트리가 된다. 따라서 입력받는 값 순서대로 트리에 삽입해준다.

2. 완성된 트리를 이용하여 후위순위결과를 구한다.

추가학습

●JAVA EOF●

-입력의 개수가 주어지지 않고 입력값만 들어올때, 입력이 끝났다는 걸 알 수 있다.

콘솔에서 ctrl+z를 누른 뒤 엔터키를 누르면 입력이 끝난 것으로 처리된다.

String input = "";
while((input = br.readLine()) != null) {
	
 }

 

+ 다른 사람들의 풀이를 보니 노드 삽입할 때 재귀로 사용하는 경우가 많아서 재귀로도 풀어봤다. 재귀는 넘 헷갈려....으아아아아아아악 

//재귀O
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B5639 {
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Tree tree = new Tree();
	
        String input = "";
        while((input = br.readLine()) != null) {
        	int data = Integer.parseInt(input);
            tree.add(tree.root, data);
        }
        tree.postOrder(tree.root);
	}
}

class Tree {
	Node root;
	
	//data 삽입
	public void add(Node node, int data) {
		if (root == null) {
			root = new Node(data);
		} else {
			if (node.data < data) {
				if (node.right != null) {
					add(node.right, data);
				} else {
					node.right = new Node(data);
				}
			} else {
				if (node.left != null) {
					add(node.left, data);
				} else {
					node.left = new Node(data);
				}
			}
		}
	}

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

class Node {
	int data;
	Node left;
	Node right;	
	
	public Node (int data){
		this.data = data;
		left = null;
		right = null;
	}
}