https://www.acmicpc.net/problem/5639
5639행: 이진 검색 트리
트리를 사전 순회한 결과를 제공합니다.
노드의 키 값은 106보다 작은 양의 정수입니다.
모든 값은 한 줄에 하나씩 주어지며 노드의 수는 10000개 미만입니다.
동일한 키를 가진 노드가 없습니다.
www.acmicpc.net
질문
이진 검색 트리는 다음 세 가지 조건을 만족하는 이진 트리입니다.
- 노드의 왼쪽 하위 트리에 있는 각 노드의 키는 해당 노드의 키보다 작습니다.
- 노드의 오른쪽 하위 트리에 있는 모든 노드의 키는 노드의 키보다 큽니다.
- 왼쪽 및 오른쪽 하위 트리도 이진 검색 트리입니다.
전위 순회(root-left-right)는 루트 노드, 왼쪽 하위 트리, 오른쪽 하위 트리를 차례로 방문하여 해당 노드의 키를 출력합니다.
사후 순회(left-right-root)는 왼쪽 하위 트리, 오른쪽 하위 트리 및 루트 노드의 순서로 키를 출력합니다.
예를 들어 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60이고 후위 순회 결과는 5 28 24 45 30 60 52 98 50입니다.
이진 검색 트리의 선위 순회가 주어지면 트리의 후위 순회를 반환하는 프로그램을 작성하십시오.
입력하다
트리를 사전 순회한 결과를 제공합니다.
노드에 포함된 키의 값은 $10^6$입니다.
모든 값은 각 행에 대해 1 미만의 양의 정수이며 노드 수는 10000 미만입니다.
동일한 키를 가진 노드가 없습니다.
인쇄
output 입력으로 제공된 이진 검색 트리를 한 줄에 하나씩 순회한 결과입니다.
728×90
예시 입력 1
50
30
24
5
28
45
98
52
60예제 출력 1
5
28
24
45
30
60
52
98
50import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main {
static ArrayList<Integer> tree;
static int() result;
static int index;
private static void postOrder(int start, int end) { // 후위 순회
result(index--) = tree.get(start); // 시작 노드를 답 배열에 담아줌
int left = -1; // 왼쪽 자식의 노드를 가리킬 인덱스
int right = -1; // 오른쪽 자식의 노드를 가리킬 인덱스
// 왼쪽 자식의 인덱스 구하기
if(start + 1 < tree.size() && tree.get(start) > tree.get(start + 1)) { // 왼쪽 자식이 있다면
left = start + 1; // start의 바로 다음 값은 start 값보다 작을 것
}
// 오른쪽 자식의 인덱스 구하기
for (int i = start + 1; i <= end; i++) {
if(tree.get(start) < tree.get(i)) {// 처음으로 나온 start 값보다 큰 곳이 오른쪽 자식의 인덱스
right = i;
break;
}
}
// 오른쪽 서브 트리를 후위 순회
if(right !
= -1) { // 오른쪽 자식이 있다면
postOrder(right, end);
}
// 왼쪽 서브 트리를 후위 순회
if(left !
= -1) { // 왼쪽 자식이 있다면
// 왼쪽 서브 트리의 끝 인덱스는
// 오른쪽 서브 트리가 있으면 오른쪽 인덱스 - 1
// 오른쪽 서브 트리가 없으면 끝까지
postOrder(left, right !
= -1 ? right - 1 : end);
}
}
public static void main(String() args){
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
tree = new ArrayList<>(); // 전위 순회한 트리 담을 리스트
while(true) { // 입력이 없을 때까지 반복(입력 끝났으면 ctrl+z)
try {
tree.add(Integer.parseInt(br.readLine()));
}
catch(Exception e) {
break;
}
}
// 트리를 후위 순회한 결과를 담을 배열
result = new int(tree.size());
index = tree.size() - 1;
// 후위 순회
postOrder(0, tree.size() - 1);
// 값 출력
for (int n : result) {
sb.append(n + "\n");
}
System.out.println(sb);
}
}구현 트리
아주 느린
위 코드 속도: 392ms
비트 전송률: 1436ms
위의 코드는 BufferedReader를 사용하여 입력을 수신하고 아래 코드는 스캐너를 사용하여 입력을 수신하므로 입력 속도도 큰 차이를 만들 수 있습니다.
import java.io.InputStreamReader;
import java.util.Scanner;
class Node {
int key;
Node parent;
Node leftChild;
Node rightChild;
Node(int key, Node parent) {
this.key = key;
this.parent = parent;
this.leftChild = null;
this.rightChild = null;
}
}
public class Main {
public static void main(String() args) throws Exception{
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
Node root = new Node(sc.nextInt(), null); // 루트 노드 입력
while(sc.hasNext()) { // 입력이 없을 때까지 반복(입력 끝났으면 ctrl+z)
Node p = root; // 현재 가리키고 있는 노드(맨 처음은 언제나 루트 노드를 가리킴)
int n = sc.nextInt();
while(true) { // 노드를 넣어줄 위치를 찾을 때까지 반복
if(p.key > n) { // 현재 가리키고 있는 노드의 key보다 작을 경우
if(p.leftChild !
= null) // 왼쪽 노드가 이미 있다면
p = p.leftChild; // 왼쪽 노드를 가리켜줌
else { // 왼쪽 노드가 비었다면
p.leftChild = new Node(n, p); // 왼쪽 노드에 넣어주고
break; // 다음 노드 입력 받으러
}
}
else { // 현재 가리키고 있는 노드의 key보다 클 경우
if(p.rightChild !
= null) // 오른쪽 노드가 이미 있다면
p = p.rightChild; // 오른쪽 노드를 가리켜줌
else { // 오른쪽 노드가 비었다면
p.rightChild = new Node(n, p); // 오른쪽 노드에 넣어주고
break; // 다음 노드 입력 받으러
}
}
}
}
// 후위 순회
Node p = root; // 현재 가리키는 노드
while(true) {
if(p.leftChild !
= null) // 현재 가리키는 노드의 왼쪽 자식이 있다면
p = p.leftChild; // 왼쪽 자식을 가리킴
else if(p.rightChild !
= null) // 현재 가리키는 노드의 오른쪽 자식이 있다면
p = p.rightChild; // 오른쪽 자식을 가리킴
else { // 현재 가리키는 노드의 자식이 없다면
sb.append(p.key + "\n"); // 출력
if(p.parent == null) // 루트 노드라면
break; // 모든 출력 완료, 반복문 탈출
if(p.key < p.parent.key) // 자신이 부모 노드의 왼쪽 자식이면
p.parent.leftChild = null; // 부모 노드의 왼쪽 자식 삭제
else // 자신이 부모 노드의 오른쪽 자식이면
p.parent.rightChild = null; // 부모 노드의 오른쪽 자식 삭제
p = p.parent; // 부모 노드를 가리켜줌
}
}
// 출력
System.out.println(sb);
}
}