[Data Structure] Java 이진트리(Binary Tree) 구현

• 이 글은 "온라인 자바 스터디 내용"을 정리한 글입니다.

이진트리(Binary Tree)란?

• 트리란 노드와 간선으로 이루어져 반복적으로 정의되는 자료구조입니다.

• 이진 트리는 트리의 종류 중 하나로 모든 노드가 두 개의 서브트리를 가지고 있는 트리입니다.

• 이진 트리의 서브 트리는 공백이 될 수도 있고 하나의 서브트리만 가지거나 두 개 모두 가질 수도 있습니다.

이진트리 구현

노드 클래스

public class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

먼저 이진트리를 구현하기 전에 이진트리에 필요한 노드를 클래스로 표현해야 합니다. 이 때 노드 내에 담을 데이터와 왼쪽 서브트리, 오른쪽 서브트리를 가리킬 포인터를 가져야 합니다.

이진트리 클래스

• void push(Node node) : 노드를 트리에 추가하는 함수
• int pop(Node node) : 노드를 트리에서 제거하는 함수
• boolean contain(Node node) : 노드가 트리에 있는지 확인하는 함수
• Node removeLastNode(Node node) : 트리에서 마지막 노드를 제거하는 함수
• boolean isSame(Node a, Node b) : 두 개의 노드가 같은 노드인지 확인하는 함수

BFS (Breadth-First Search)란?

• BFS는 그래프 전체를 탐색하는 알고리즘 중 하나로 루트 노드에서부터 시작하여 가까운 노드부터 먼저 탐색하는 방법입니다.
• 루트노드부터 가까운 정점을 방문하고 멀리 떨어져 있는 노드는 상대적으로 나중에 방문함으로써 노드를 넓게 탐색합니다.
• BFS 알고리즘 구현 시 큐(Queue) 를 이용하여 구현합니다.

    public void printBFS(Node node) {

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

        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            System.out.println(temp.value);

            if (temp.left != null) {
                queue.add(temp.left);
            }

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

DFS(Depth-First Search)란?

• DFS도 마찬가지로 그래프 전체를 탐색하는 알고리즘으로 루트노드에서 하나의 노드를 방문하게 되면 다음 인접한 노드로 가기 전에 방문한 노드를 끝까지 탐색하는 방법입니다.
• 하나의 노드를 끝까지 방문하기 때문에 노드를 깊게 탐색한다고 볼 수 있습니다.
• DFS 알고리즘 구현 시 재귀함수 또는 스택을 이용하여 구현합니다.

    public void printDFS(Node node) {

        if(node.left == null && node.right == null){
            System.out.println(node.value);
        }else{
            if(node.left != null){
                printDFS(node.left);
            }
            System.out.println(node.value);
            if(node.right != null){
                printDFS(node.right);
            }
        }
    }

결과

public class Main {
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();

        Node node = new Node(3);
        Node node1 = new Node(5);
        Node node2 = new Node(7);
        Node node3 = new Node(4);
        Node node4 = new Node(2);

        bt.push(node);
        bt.push(node1);
        bt.push(node2);
        bt.push(node3);
        bt.push(node4);

        System.out.println("BFS로 탐색합니다");
        bt.printBFS(node);

        System.out.println("\nDFS로 탐색합니다");
        bt.printDFS(node);
    }
}