[백준] 5639. 이진 검색 트리 (자바 JAVA)

[ 문제 ]  [백준] 5639. 이진 검색 트리 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

---

# 접근 방법 및 풀이 

 

• 트리문제다. 문제의 조건에 맞는 이진트리를 구현하고, 후위순회를 재귀함수로 만들어 값을 프린트하면 된다.
• 이진트리를 구현하기 위해 Node 클래스를 만들어 "현재 노드의 값, 왼쪽 노드, 오른쪽노드" 변수 세개를 만들어 주었다.
• 문제의 입력에 첫번째로 입력되는 값이 root이므로 먼저 root 노드를 생성해준다.
• 그리고 Node 클래스에 insert함수를 만들어, "현재 노드의 값보다 작으면 왼쪽에, 크면 오른쪽"에 추가하도록 했다.
• 이때, 현재 노드의 추가하려는 왼쪽이나 오른쪽에 이미 노드가 있다면, 그 노드의 insert()에 값을 넘겨주면 된다.
• 후위순회 재귀함수는 "왼쪽-오른쪽-루트"대로 재귀를 구현했다.
• 자세한건 코드참조

# 주의할 점 

 

• 이진트리 구현하는 방법이 다양하게 있는데 어떻게 구현할지 먼저 초점두기. 배열로 할 수도 있다.

 

JAVA 코드

package Silver;

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

public class bj5639_이진검색트리 {
	static class Node{
		int num;
		Node left, right;
		public Node(int num) {
			this.num = num;
		}
		void insert(int num) {
			if(num < this.num) {
				if(this.left == null) {
					this.left = new Node(num);
				}else {
					this.left.insert(num);
				}
			}else {
				if(this.right == null) {
					this.right = new Node(num);
				}else {
					this.right.insert(num);
				}
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Node root = new Node(Integer.parseInt(in.readLine()));
		while(true) {
			String s = in.readLine();
			if(s == null)
				break;
			root.insert(Integer.parseInt(s));
		}
		postOrder(root);
	}
	private static void postOrder(Node node) {
		if(node.left != null)
			postOrder(node.left);
		if(node.right != null)
			postOrder(node.right);
		System.out.println(node.num);
	}
}

 

 

 

REVIEW

요즘 내가 약한 유형의 문제를 풀고있는데 너무 재밌다. 트리 문제 많이 풀어봐야지!

트리를 다양하게 구현할 수 있는 문제들을 많이 풀어봐야겠다.