백준 5639번: 이진 검색 트리

문제

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

---

풀이

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리일 때 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 출력해야하는 문제입니다.

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

---

접근

전위 순회의 경우 처음 출력되는 값에 대한 노드가 루트노드입니다. 그러므로 루트노드를 설정하고 이진 검색 트리의 규칙에 맞게 삽입한 후에 후위 순회한 결과를 출력하도록 하여 문제를 해결했습니다.

---

코드

자바

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class node {
    Integer data;
    node left, right;

    public node(Integer data) {
        this.data = data;
    }

    public void insert(int data) {
        if (this.data == null) { // (1)
            this.data = data;
            return;
        }
        if (data < this.data) { // (2)
            if (this.left == null) this.left = new node(data);
            else this.left.insert(data);
        } else if (data > this.data) { // (3)
            if (this.right == null) this.right = new node(data);
            else  this.right.insert(data);
        }
    }
}

public class Main {

    static StringBuilder sb = new StringBuilder();

    public static void postorder(node root) { // (4)
        if (root == null) return;
        if (root.left != null) postorder(root.left);
        if (root.right != null) postorder(root.right);
        sb.append(root.data).append("\n");
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        node root = new node(null);
        String str = null;
        while ((str = br.readLine()) != null) {
            int data = Integer.parseInt(str);
            root.insert(data);
        }
        postorder(root);
        System.out.print(sb);
    }
}

트리의 노드 클래스 node에서 data는 Integer로 선언하여 null 값을 받을 수 있게 하고

노드(node) 클래스는 해당 노드의 번호 data를 Integer로 선언하여 null 값을 받을 수 있게 하였고 왼쪽 오른쪽 자식노드 left, right를 가지며  insert() 메소드를 포함시켜 이진 검색 트리의 규칙에 맞게 삽입할 수 있도록 하였습니다. 루트노드 root는 new node(null)로 초기화한 후에 몇 개의 노드를 넣을지 명시하지 않았기 때문에 입력이 끝날 때 까지 root.insert(data)를 실행합니다.

 

(1) 현재 탐색중인 노드의 data가 null일 경우에 this.data = data로 초기화한 뒤에 return합니다.

현재 탐색중인 노드의 data가 null일 경우는 new node(null)로 초기화한 루트노드 root일 경우밖에 없습니다. 위에서 설명하였듯이 전위 순회한 결과에서 맨 처음 데이터를 갖는 노드가 루트노드가 되므로 맨 처음에 딱 1번 실행됩니다.

 

(2) 현재 탐색중인 노드의 data가 삽입하려는 data보다 큰 경우입니다.

이 경우는 현재 탐색중인 노드의 왼쪽 자식노드로 이동해야합니다. 만약 현재 탐색중인 노드의 왼쪽 자식노드(this.left)가 null인 경우에 해당 노드를 new node(data)로 삽입하고 null이 아닐 경우에 this.left.insert(data)를 실행하여 왼쪽 자식노드부터 insert() 메소드를 반복하게 합니다.

 

(3) 현재 탐색중인 노드의 data가 삽입하려는 data보다 작은 경우입니다.

이 경우는 (2)와 반대로 현재 탐색중인 노드의 오른쪽 자식노드로 이동해야합니다. 만약 현재 탐색중인 노드의 오른쪽 자식노드(this.right)가 null인 경우에 해당 노드를 new node(data)로 삽입하고 null이 아닐 경우에 this.right.insert(data)를 실행하여 오른쪽 자식노드부터 insert() 메소드를 반복하게 합니다.

 

(4) 트리가 완성되었다면 후위 순회를 실시합니다.

왼쪽 자식노드가 있다면 왼쪽 자식노드로 이동하고 없다면 오른쪽 자식노드가 있는지 확인합니다. 이때 오른쪽 자식노드가 있다면 오른쪽 자식노드로 이동하고 위의 과정을 반복합니다. 이때 왼쪽 자식노드, 오른쪽 자식노드 둘 다 없다면 현재 노드의 데이터를 StringBuilder sb에 저장합니다.

 

모든 과정을 종료한 후에 StringBuilder에 각 값을 넣고 한꺼번에 출력합니다.

C언어

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
	int data;
	struct Node* left;
	struct Node* right;
} Node;
void postorder(Node* root) {
	if (root) {
		postorder(root->left);
		postorder(root->right);
		printf("%d\n", root->data);
	}
}
Node* newNode(int data) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->left = node->right = NULL;
	return node;
}
Node* insertNode(Node* node, int data) {
	if (node == NULL) return newNode(data); // (1)
	if (data < node->data) { // (2)
		node->left = insertNode(node->left, data);
	}
	else if (data > node->data) { // (3)
		node->right = insertNode(node->right, data);
	}
	return node;
}
main() {
	Node* root = NULL;
	int value;
	while (scanf("%d", &value) != EOF) {
		root = insertNode(root, value);
	}
	postorder(root);
}

자바를 이용한 풀이와 비슷하지만 C언어로는 구조체 안에 함수를 넣을 수 없기 때문에 insertNode() 함수를 만들어 연결리스트로 잇는 방법으로 풀었습니다. insertNode() 함수의 return값은 Node*이며 처음에 입력할 때 루트노드 Node* root를 null로 선언하고 root = insertNode(root, value)를 반복합니다. insertNode 함수를 보면 다른 점을 확인할 수 있습니다.

 

(1) 현재 탐색중인 노드 node가 null일 경우에 newNode(data)를 return합니다.

newNode(data) 함수를 보면 자바에서의 new node(data)와 유사합니다. return받은 노드는 루트노드 root가 됩니다.

 

(2) 현재 탐색중인 노드의 data가 삽입하려는 data보다 큰 경우입니다.

이 경우는 node->left = insertNode(node->left, data)로 현재 탐색중인 노드의 왼쪽 자식노드로 이동해야합니다. 현재 탐색중인 노드 node가 null일 때까지 과정을 반복합니다.

 

(3) 현재 탐색중인 노드의 data가 삽입하려는 data보다 작은 경우입니다.

이 경우는 node->right = insertNode(node->right, data)로 현재 탐색중인 노드의 오른쪽 자식노드로 이동해야합니다. 현재 탐색중인 노드 node가 null일 때까지 과정을 반복합니다.

---

결론

이 문제를 처음 봤을 때 전위 순회와 후위 순회와의 관계에 대한 규칙에 대해 고민했었는데 트리의 모양에 따라 규칙이 달라지기 때문에 결국 알아내지 못했습니다. 그래서 예제 입력 결과에서 전위 순회 결과와 후위 순회 결과에 대한 공통점이 무엇인지에 대해 고민하다가 전위 순회 결과의 처음 데이터와 후위 순회 결과의 맨 마지막 데이터가 루트노드의 데이터라는 것을 알게 되었습니다. 이처럼 문제에 대해 규칙을 찾다보면 더 어려운 문제도 해결할 수 있을 것입니다.