[BOJ] 5639 이진검색트리 - JAVA

1. 문제

5639번: 이진 검색 트리

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진트리이다.

• 노드의 왼쪽 서브 트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브 트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브 트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

---

2. 풀이

전위 순회로 문제가 입력되기 때문에 루트 먼저 만들고 오른쪽 왼쪽 노드를 붙여도 된다.

Node 클래스

private static class Node {
   int data;
   Node left;
   Node right;

   private Node(int data) {
      this.data = data;
      this.left = null;
      this.right = null;
   }
}

 

메인

입력과 동시에 원본 tree를 만들었다.

1.  맨 처음 값을 가지고 tree 전체 루트를 만든다.

2.  그다음 값부터는 BST 트리 탐색을 통해서 새로 입력받은 값이 어디에 속해야 하는지 찾아낸다.

3.  찾아낸 위치에 새 Node를 더한다.

4.  완성된 tree를 후위 순회한다.

static StringBuilder sb = new StringBuilder();
static Node tree;

public static void main(String[] args) throws Exception {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

   String line = in.readLine();
   tree = new Node(Integer.parseInt(line));
   while ((line = in.readLine()) != null) {
      int data = Integer.parseInt(line);
      Node node = new Node(data);

      Node parent = tree;
      for (Node child = parent; child != null; ) {
         parent = child;
         if (node.data < parent.data) child = parent.left;
         else child = parent.right;
      }

      if (node.data < parent.data) parent.left = node;
      else parent.right = node;
   }

   post(tree);
   System.out.print(sb);
}

 

후위 순회

자식 노드가 null이 아닐 때만 재귀 호출했다.

자식을 모두 호출하고 난 뒤에 루트 데이터를 StringBuilder에 더했다.

private static void post(Node root) {
   if (root.left != null) post(root.left);
   if (root.right != null) post(root.right);
   sb.append(root.data).append('\n');
}

---

3. 결과