[자바] 백준 5639번: 이진 검색 트리

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

5639번: 이진 검색 트리

---

 

자료구조 시간에 배웠던 이진트리를 그대로 구현했다

 

값을 입력받아 이진트리를 구성하고,

실제로 만들어진 이진트리를 후위순회하며 값을 출력한다.

 

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

public class P5639 {

	static class Node{
		int key;
		Node l_child=null;
		Node r_child=null;
		public Node(int key) {
			this.key=key;
		}
	}
	static Node modified_search(Node root,int key) {
		
		if(root.key==key) {
			return null; 
		}
		else if(root.key>key) {
			if(root.l_child==null) {
				return root;
			}
			else {
				return modified_search(root.l_child, key);
			}
		}
		else{
			if(root.r_child==null) {
				return root;
			}
			else {
				return modified_search(root.r_child, key);
			}
		}
	}
	static void bst_add(Node root, int key) {
		Node parent=modified_search(root, key);
		if(parent.key<key) {
			parent.r_child=new Node(key);
		}
		else if(parent.key>key) {
			parent.l_child=new Node(key);
		}
	}
	
	static void postorder(Node root) {
		if(root!=null) {
			postorder(root.l_child);
			postorder(root.r_child);
			System.out.println(root.key);
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Node root=new Node(Integer.parseInt(br.readLine()));
		String num;

		while(true){
			num=br.readLine();
			if(num==null||num.equals(""))
				break;
			bst_add(root,Integer.parseInt(num));
		}

		postorder(root);
	}

}

 

입력값이 이진트리를 전위순회한 값인데,

예제 입력 1 

50
30
24
5
28
45
98
52
60

이 값들을 보면

값들이 계속 감소하다가(50 30 24 5)

어느순간 다시 증가(28 45 98)

또 감소(52)

다시 증가(60)한다...

..

이런 것들을 보니

이진트리를 다 구현하지 않고도 후위순회 값을 출력할 수 있지 않을까? 라는 생각을 했다.