이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
- 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
- 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
- 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
import java.io.*;
class Main {
static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static class Tree{
int value;
Tree left;
Tree right;
public Tree(int value){
this.value=value;
left=null;
right=null;
}
public static void insert(Tree head, int value) {
Tree temp = new Tree(value);
Tree ptr = head;
while(true){
if(value>ptr.value) {
if (ptr.right == null) {
ptr.right = temp;
return;
} else
ptr = ptr.right;
}
else {
if (ptr.left == null) {
ptr.left = temp;
return;
} else
ptr = ptr.left;
}
}
}
public static void postorder(Tree ptr) throws IOException {
if(ptr==null)
return;
postorder(ptr.left);
postorder(ptr.right);
bw.write(ptr.value+"\n");
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s=br.readLine();
Tree head=new Tree(Integer.parseInt(s));
while(true){
s=br.readLine();
if(s==null)
break;
if(s.equals(""))
break;
Tree.insert(head, Integer.parseInt(s));
}
Tree.postorder(head);
bw.flush();
}
}
Binary Search Tree를 만들어서 입력 받는 값을 넣은 뒤 Postorder Traversal 해서 출력했다. 입력의 끝을 알 수가 없어서 BufferedReader의 readline 메소드를 사용한 뒤 s의 값을 null과 비교해줘서 탈출 시켰다.
런타임 에러(탈출 했을 때 마지막 문자열은 ""인 상태이므로 parseInt("")에서 런타임 에러가 발생한다. 따라서 조건을 추가해줬다.)
😁