과제(Optional)

int 값을 가지고 있는 이진 트리를 나타내는 Node라는 클래스를 정의하세요
int value, Node left, right를 가지고 있어야 합니다
BinaryTree라는 클래스를 정의하고 주어진 노드를 기준으로 출력하는 bfs(Node node)와 dfs(Node node) 메소드를 구현하세요
DFS는 왼쪽, 루트, 오른쪽 순으로 순회하세요

이진 트리(binary tree)

자식노드가 최대 두 개인 노드들로 구성된 트리
정이진트리, 완전이진트리, 균형이진트리 등

이진 탐색 트리(binary search tree)

효율적인 탐색, 삽입 및 삭제 연산을 가능
이진 탐색 특성에 따라 키가 정렬되어 있어 트리 내에서 요소를 찾는 것이 용이합
데이터베이스, 검색 엔진, 다양한 알고리즘 및 데이터 구조와 같이 효율적인 탐색이 필요한 응용 프로그램에서 일반적으로 사용됨
정렬된 데이터 저장 및 효율적인 검색 사이의 균형을 제공함

이진 탐색 트리 데이터 구조

BST의 각 노드는 키 값을 가지며, 트리 내에 있는 두 노드는 동일한 키 값을 가지지 않음
노드의 왼쪽 서브트리에 있는 키 값은 해당 노드의 키 값보다 작음
노드의 오른쪽 서브트리에 있는 키 값은 해당 노드의 키 값보다 큼
노드의 왼쪽 서브트리와 오른쪽 서브트리는 모두 이진 탐색 트리임

이진 트리 순회

전위(pre-order) 순회 = 루트로 부터 시작하여 왼쪽, 오른쪽을 순차적으로 순회하는 방법
- A -> B -> C -> D -> E -> F -> G
중위(in-order) 순회 = 왼쪽 자식 노드를 방문한 뒤 부모노드, 우측노드를 순차적으로 순회하는 방법
- C -> B -> D -> A -> F -> E -> G
후위(post-order) 순회 = 좌측노드, 우측노드 그리고 부모노드를 순차적으로 순회하는 방법
- C -> D -> B -> F -> G -> E -> A

BFS(Breadth-First Search)

루트노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
장점
- 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작
- 깊은 우선 탐색(DFS)보다 단순 검색 속도가 빠름
- 너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장
- 최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾아냄
단점
- 노드의 수가 많아지면 탐색해야하는 노드가 많아짐
- 재귀호출을 이용하는 DFS와는 달리 큐에 다음에 탐색할 노드를 저장하기 때문에 저장공간이 많이 필요함

DFS(Depth-First Search)

한 노드에 대해 탐색할 수 있는 깊이까지 먼저 탐색한 뒤 다음 탐색을 이어가는 방법
장점
- 현 경로상의 노드만을 기억하면 되므로 저장공간이 많이 필요하지 않음
- 목표노드가 같은 단계에 있을 경우 결과를 빠르게 구할 수 있음
단점
- 결과 값이 없는 경로에 깊이 빠질 가능성 존재
- 결과 값이 다수 존재할 경우 해당 값이 최단 경로라는 보장이 없음

public class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

public class BinarySearchTree {
    Node root;

    BinarySearchTree() {
        root = null;
    }

    void insert(int key) {
        root = insertRec(root, key);
    }

    Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }

        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);

        return root;
    }

    void deleteKey(int key) {
        root = deleteRec(root, key);
    }

    Node deleteRec(Node root, int key) {
        if (root == null)
            return root;

        if (key < root.key)
            root.left = deleteRec(root.left, key);
        else if (key > root.key)
            root.right = deleteRec(root.right, key);
        else {
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            root.key = minValue(root.right);

            root.right = deleteRec(root.right, root.key);
        }

        return root;
    }

    int minValue(Node root) {
        int minValue = root.key;
        while (root.left != null) {
            minValue = root.left.key;
            root = root.left;
        }
        return minValue;
    }

    void inorder() {
        inorderRec(root);
        System.out.println("종료");
    }

    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.key + " -> ");
            inorderRec(root.right);
        }
    }

    void postorder() {
        postorderRec(root);
        System.out.println("종료");
    }

    void postorderRec(Node root) {
        if (root != null) {
            postorderRec(root.left);
            postorderRec(root.right);
            System.out.print(root.key + " -> ");
        }
    }

    void preorder() {
        preorderRec(root);
        System.out.println("종료");
    }

    void preorderRec(Node root) {
        if (root != null) {
            System.out.print(root.key + " -> ");
            preorderRec(root.left);
            preorderRec(root.right);
        }
    }

    void bfs(Node searchNode) {
        if (root == null)
            return;

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.key + " -> ");

            if (node.key == searchNode.key)
                break;

            if (node.left != null)
                queue.add(node.left);

            if (node.right != null)
                queue.add(node.right);
        }

        System.out.println("종료");
    }

    void dfs(Node searchNode) {
        if (root == null)
            return;

        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.print(node.key + " -> ");

            if (node.key == searchNode.key)
                break;

            if (node.right != null)
                stack.push(node.right);

            if (node.left != null)
                stack.push(node.left);
        }

        System.out.println("종료");
    }

}