자바 알고리즘 인터뷰 14. 트리

저번 주제인 그래프에 이어서 트리 역시 비선형 자료구조에 해당한다.

 

굳이 비교를 하자면, 그래프가 트리를 포함하는 구조라고 할 수 있다.

 

정의를 비교해보면, 그래프에서 방향과 사이클이 없는 자료 구조가 트리라고 할 수 있다.

 

 

그래프와 마찬가지지만 이러한 비선형 자료구조를 표현하기 위해서는 이중 연결리스트의 자료구조를 빌려올 필요가 있다. 주로 언급되는 대부분의 트리는 이진 트리임을 가정해 본 전제 하에서, 아래의 글을 읽으면 좋을 듯 하다.

 

우선 트리는 루트와 좌측 우측으로 나뉜다. 

 

 이러한 루트, 좌측, 우측이라는 구조가 재귀적으로 반복되는 것이 바로 (이진)트리의 형태이다.

 

우선 트리를 만들려면 루트, 즉 기준점이 있어야 한다. 그 다음에 그 기준점에서 상대적으로 좌측이니 우측이니가 정해지게 된다. 

 

자바는 여기에 this라는 멤버 변수를 만드는 키워드가 필요하기 때문에 그 부분이 추가된 것이라고 할 수 있다.

 

다음으로 전위 순회, 중위 순회, 후위 순회라는 개념을 살펴보자.

 

1. 전위 순회

전위 순회는 순회하는 과정이 루트 => 좌측 => 우측의 순서로 진행된다.

 

2. 중위 순회

중위 순회는 순회하는 과정이 좌측 => 루트 => 우측의 순서로 진행된다.

 

3. 후위 순회

후위 순회는 순회 과정이 좌측 => 우측 => 루트의 순서로 진행된다.

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

class Node{
    char data;
    Node left;
    Node right;

    Node(char data) {
        this.data = data;
    }
}

class Tree {
    public Node root;

    public void createNode(char data, char leftData, char rightData) {
        if(root == null) {
            root = new Node(data);
            root.left = leftData != '.' ? new Node(leftData) : null;
            root.right = rightData != '.' ? new Node(rightData) : null;
        }else {
            searchNode(root, data, leftData, rightData);
        }
    }

    public void searchNode(Node node, char data, char leftData, char rightData) {
        if(node == null) {
            return;
        }else if(node.data == data) {
            node.left = leftData != '.' ? new Node(leftData) : null;
            node.right = rightData != '.' ? new Node(rightData) : null;
        }else {
            searchNode(node.left, data, leftData, rightData);  // 오른쪽 재귀 탐색
            searchNode(node.right, data, leftData, rightData);  // 왼쪽 재귀 탐색
        }
    }

    // 전위순회 Preorder : Root -> Left -> Right
    public void preOrder(Node node) {
        if(node != null) {
            System.out.print(node.data);
            if(node.left != null) {preOrder(node.left);}
            if(node.right != null) {preOrder(node.right);}
        }
    }

    // 중위순회 Inorder : Left -> Root -> Right
    public void inOrder(Node node) {
        if(node != null) {
            if(node.left != null) {inOrder(node.left);}
            System.out.print(node.data);
            if(node.right != null) {inOrder(node.right);}
        }
    }

    // 후위순회 Postorder : Left -> Right -> Root
    public void postOrder(Node node) {
        if(node != null) {
            if(node.left != null) {postOrder(node.left);}
            if(node.right != null) {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());
        Tree t = new Tree();

        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            char root = st.nextToken().charAt(0);
            char left = st.nextToken().charAt(0);
            char right = st.nextToken().charAt(0);

            t.createNode(root, left, right);
        }

        t.preOrder(t.root);
        System.out.println();
        t.inOrder(t.root);
        System.out.println();
        t.postOrder(t.root);

        br.close();
    }
}