[알고리즘] 코테 유형 분석 23. 이진 트리

안녕하세요 이번 시간에는 이진 트리에 대해 알아보는 시간을 갖도록 하겠습니다.

이진 트리란 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성되어 있는 트리입니다. 이진 트리는 크게 3가지 종류가 존재합니다.

먼저 편향 이진 트리란 노드들이 한 쪽으로 편향되어 생성된 이진 트리입니다. 탐색 속도가 저하되고 공간이 많이 낭비되는 단점이 있습니다. 두 번째로 포화 이진 트리란 트리의 높이가 모두 일정하며 리프 노드가 꽉찬 이진 트리입니다. 마지막으로 완전 이진 트리란 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고 마지막 레벨은 왼쪽부터 채워진 트리입니다. 따라서 트리를 생성하여 탐색할 때 완전 이진 트리 또는 포화 이진 트리를 만들어 탐색합니다.

트리를 탐색하는 방법은 크게 3가지가 존재합니다. 먼저 전위 순회란 현재 노드, 왼쪽 노드, 오른쪽 노드 순서로 탐색하는 방식이며 중위 순회란 왼쪽 노드, 현재 노드, 오른쪽 노드 순서로 탐색하는 방식입니다. 마지막으로 후위 순회란 왼쪽 노드, 오른쪽 노드, 현재 노드 순서로 탐색합니다. 즉 전위, 중위, 후위 순회의 차이점은 현재 노드를 언제 탐색하는가에 따라 나뉜다고 보시면 되겠습니다.

이진 트리를 구현하는 방법은 크게 배열을 이용하는 방법과 객체를 생성하는 방법이 있습니다.

먼저 배열을 이용하여 트리를 구현해보겠습니다. 배열에서 이동하고자 하는 노드에 따른 인덱스를 변화하면서 노드를 탐색합니다.

루트 노드로 이동할 때는 index = 1인 위치로 이동합니다. 부모 노드로 이동할 때는 자식 노드가 2개씩 존재하기 때문에 index /= 2로 이동합니다. 왼쪽 자식 노드로 이동하는 경우 마찬가지로 자식 노드가 2개씩 존재하기 때문에 index x= 2만큼 이동합니다. 또한 오른쪽 자식 노드는 index = index x 2 +1만큼 이동합니다. 단 부모 노드로 이동할 때는 현재 노드가 루트 노드이면 안되며, 자식 노드로 이동할 때는 이동한 노드가 전체 노드 개수보다 작아야 합니다.

그럼 배열을 이용하여 트리를 구현해보겠습니다. 백준 1991 (트리 순회) 문제의 경우 이진 트리를 입력받아 전위, 중위, 후위 순회한 결과를 출력하는 문제입니다. 트리를 [26][2]의 이차원 배열로 구현한 후 각 알파벳에 해당하는 노드에 2개씩 자식 노드를 추가하는 방식으로 구현합니다. 이 때 각 순회의 경우 재귀함수 형식으로 구현하며 전위 순회의 경우 가장 먼저 현재 노드를 탐색한 후 이어서 왼쪽 노드와 오른쪽 노드를 재귀함수로 실행합니다. 마찬가지로 중위 순회의 경우 왼쪽 노드, 현재 노드, 오른쪽 노드 순서대로, 후위 순회의 경우 왼쪽 노드, 오른쪽 노드, 현재 노드 순서대로 진행합니다.

import java.util.*;
import java.io.*;

class Main{
    static int N;
    static int[][] tree;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        tree = new int[26][2];

        for(int i=0;i<N;i++){
            String[] node = br.readLine().split(" ");
            int parent = node[0].charAt(0)-'A';
            char left = node[1].charAt(0);
            char right = node[2].charAt(0);

            if(left == '.') tree[parent][0] = -1;
            else tree[parent][0] = left-'A';

            if(right == '.') tree[parent][1] = -1;
            else tree[parent][1] = right-'A';
        }

        preOrder(0);
        System.out.println();
        inOrder(0);
        System.out.println();
        postOrder(0);
        System.out.println();
    }

    static void preOrder(int idx){
        if(idx == -1) return;

        System.out.print((char) (idx+'A'));
        preOrder(tree[idx][0]);
        preOrder(tree[idx][1]);
    }

    static void inOrder(int idx){
        if(idx == -1) return;

        inOrder(tree[idx][0]);
        System.out.print((char) (idx+'A'));
        inOrder(tree[idx][1]);
    }

    static void postOrder(int idx){
        if(idx == -1) return;

        postOrder(tree[idx][0]);
        postOrder(tree[idx][1]);
        System.out.print((char) (idx+'A'));
    }
}

다음은 객체를 생성하여 트리를 구현하는 방식입니다. 노드 객체를 생성한 후 각 객체의 값과 왼쪽 노드와 오른쪽 노드를 저장합니다. 이후 트리에 데이터를 추가하는 방식을 재귀함수로 구현하여 재귀함수로 탐색하는 현재 노드의 값이 타깃 노드(부모 노드)의 값과 같다면 해당 노드의 왼쪽 값과 오른쪽 값을 각각 주어진 값으로 대체합니다. 이후 배열 방식과 마찬가지로 재귀함수로 트리를 탐색하여 값을 출력합니다.

import java.io.*;
import java.util.*;

class Node {
    char data;
    Node left, right;

    public Node(char item) {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    void preOrder(Node node) {
        if(node == null) return;

        System.out.print(node.data);
        preOrder(node.left);
        preOrder(node.right);
    }

    void inOrder(Node node) {
        if(node == null) return;

        inOrder(node.left);
        System.out.print(node.data);
        inOrder(node.right);
    }

    void postOrder(Node node) {
        if(node == null) return;

        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data);
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        BinaryTree tree = new BinaryTree();
        for (int i=0;i<N;i++) {
            String[] input = br.readLine().split(" ");
            char parent = input[0].charAt(0);
            char left = input[1].charAt(0);
            char right = input[2].charAt(0);

            Node parentNode = new Node(parent);
            Node leftNode, rightNode;
            if(left == '.') leftNode = null;
            else leftNode = new Node(left);
            if(right == '.') rightNode = null;
            else rightNode = new Node(right);

            if (tree.root == null) tree.root = parentNode;
            Node currentNode = tree.root;
            insertChild(currentNode, parent, leftNode, rightNode);
        }

        tree.preOrder(tree.root);
        System.out.println();
        tree.inOrder(tree.root);
        System.out.println();
        tree.postOrder(tree.root);
        System.out.println();
    }

    static void insertChild(Node currentNode, char parent, Node leftNode, Node rightNode) {
        if (currentNode == null) return;

        if (currentNode.data == parent) {
            currentNode.left = leftNode;
            currentNode.right = rightNode;
        } else {
            insertChild(currentNode.left, parent, leftNode, rightNode);
            insertChild(currentNode.right, parent, leftNode, rightNode);
        }
    }
}