https://www.acmicpc.net/problem/5639
5639행: 이진 검색 트리
트리를 사전 순회한 결과가 제공됩니다. 노드의 키 값은 106보다 작은 양의 정수입니다. 모든 값은 한 줄에 한 번 지정되며 노드 수는 10,000 미만입니다. 동일한 키를 가진 노드가 없습니다.
www.acmicpc.net
오늘 우리가 해결한 문제는 이진 트리 탐색입니다.
순회 방법은 저번에 풀었던 트리 순회 문제와 동일하지만, 입력 값은 이전 순회에서 생성된 값이 주어진다.
그래서 클래스 타입으로 트리를 만들 때 조건문에 주의를 기울여야 합니다.
이 문제는 입력 노드의 수가 고정되어 있지 않기 때문이기도 합니다.
입력이 null인지 확인하여 반복을 중지해야 합니다.
따라서 이 문제는 입력을 듣고 이진 트리를 만드는 것에 관한 것입니다.
이진 트리는 왼쪽 자식에 부모보다 작은 값을, 오른쪽 자식에 부모보다 큰 값을 저장하는 트리이므로 이 조건을 이용하여 조건문을 작성하였다.
이는 추가 재귀를 통해 수행할 수 있습니다.
작동 원리
1. 값이 상위 노드보다 작은지 확인하십시오.
2. 적으면 왼쪽 자식이 비어 있는지 확인합니다.
3. 비어 있으면 삽입 비어 있지 않으면 왼쪽 자식을 찾습니다.
1. 값이 상위 노드보다 큰지 확인하십시오.
2. 크면 오른쪽 자식이 비어있는지 확인한다.
3. 비어 있으면 삽입 비어 있지 않으면 올바른 자식을 찾습니다.
후방트래버스에 대해 잘 아시는 것 같아서 설명은 생략하겠습니다.
(왼쪽자식노드, 오른쪽자식노드, 부모노드 순으로)
응답 코드는 다음과 같습니다.
package backjoon.b5639;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class b5639 {
public static void main(String() args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Node root = new Node(Integer.parseInt(br.readLine()));
Graph g = new Graph(root);
while (true){
String sData = br.readLine();
if(sData==null) {
break;
}
if(sData.length()==0){
break;
}
g.create(Integer.parseInt(sData));
}
g.postOrder(root);
System.out.println(g.sb);
}
}
class Graph{
Node root;
StringBuilder sb;
public Graph(Node root) {
this.root = root;
sb = new StringBuilder();
}
public void create(int data){
search(root,data);
}
public void search(Node node, int data){
if(node==null){
return;
}
if(node.data>data){
if(node.left==null){
node.left = new Node(data);
}
else{
search(node.left,data);
}
}
else if(node.data<data){
if(node.right==null){
node.right = new Node(data);
}
else {
search(node.right,data);
}
}
}
public void postOrder(Node node){
if(node!=null){
if(node.left!=null)postOrder(node.left);
if(node.right!=null)postOrder(node.right);
sb.append(node.data).append("\n");
}
}
}
class Node{
Node right;
Node left;
int data;
public Node(int data) {
this.data = data;
}
}