반응형
* 핵심
BinaryTree Class를 만들어서 left, right에 자식 이진 트리를 만들어 붙여 트리를 만든다.
* 문제
문제
이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
- 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
- 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
- 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
입력
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.
출력
입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.
* 소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | import java.io.*; import java.util.*; public class Main { public static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BinaryTree tree = new BinaryTree(Integer.parseInt(br.readLine())); String s = ""; while ((s = br.readLine()) != null && s.length() != 0) { //EOF까지 입력받음 tree = tree.addTree(tree, Integer.parseInt(s)); } postorder(tree); System.out.println(sb); } public static void postorder(BinaryTree tree) { if (tree.left != null) postorder(tree.left); if (tree.right != null) postorder(tree.right); sb.append(tree.data + "\n"); } } class BinaryTree { int data; BinaryTree left; BinaryTree right; public BinaryTree(int data) { this.data = data; this.left = null; this.right = null; } public BinaryTree addTree(BinaryTree tree, int val) { BinaryTree curTree = null; if (tree == null) return new BinaryTree(val); if (tree.data > val) { curTree = addTree(tree.left, val); //새로운 하위 이진 트리 생성 tree.left = curTree; //부모 노드의 왼쪽에 붙인다 } else if (tree.data < val) { curTree = addTree(tree.right, val); //새로운 하위 이진 트리 생성 tree.right = curTree; //부모 노드의 오른쪽에 붙인다 } return tree; //새로 붙인 트리 return } } | cs |
반응형
'∙Algorithm' 카테고리의 다른 글
| [Algorithm] 백준/1010 :: 다리 놓기 (0) | 2019.01.28 |
|---|---|
| [Algorithm] 백준/5568 :: 카드 놓기 (0) | 2019.01.28 |
| [Algorithm] 백준/1275 :: 커피숍2 (0) | 2019.01.22 |
| [Algorithm] 백준/2042 :: 구간 합 구하기 (0) | 2019.01.22 |