JAVA | 이진트리 구현

이진트리 구현

Java Collection Framework에는 왜 이진 트리가 없을까?

1. 균형 문제
   • 이진 트리를 사용할 때 균형을 유지하지 않으면 최악의 경우 연결 리스트처럼 동작하여 성능이 크게 저하될 수 있습니다.
   • Java Collection Framework는 균형 이진 트리 기반 자료구조를 제공하는 것으로 이러한 문제를 해결했습니다.
2. Red-Black Tree 사용
   • Java의 TreeMap과 TreeSet은 모두 Red-Black Tree를 기반으로 하여 균형을 유지하면서 효율적인 탐색, 삽입, 삭제를 보장합니다.
   • 그래서 별도의 "이진 트리" 클래스가 필요하지 않습니다.
3. 직접 구현이 필요한 경우
   • 순수 이진 트리를 원한다면 직접 구현해야 합니다.
   • 위에서 제공한 Node와 BinaryTree 구현이 순수한 형태의 이진 트리를 구성하는 예제입니다.

이러한 이유로 Java에는 순수 이진 트리(Binary Tree)를 지원하는 표준 클래스가 없기 때문에, 이진 트리를 순회하거나 조작하려면 직접 구현해야 합니다. 

 

노드

이진트리를 이해하고 구현하려면 먼저 노드(Node)의 개념을 이해해야합니다!

노드는 데이터와 다른 노드와의 연결 정보를 포함하는 기본 단위입니다.

각 노드는 하나의 데이터를 저장하며, 이진 트리에서는 최대 두개의 자식노드(왼쪽, 오른쪽)와 연결됩니다.

      [10]           10: 루트 노드
     /    \          5 : 왼쪽 자식 노드
  [5]     [15]       15: 오른쪽 자식 노드

 

노드구현

class Node {
    int data;       // 노드의 데이터
    Node left;      // 왼쪽 자식
    Node right;     // 오른쪽 자식

    // 생성자
    public Node(int data) {
        this.data = data;   // 데이터를 초기화
        this.left = null;   // 초기에는 자식 노드가 없음
        this.right = null;
    }
}

 

 

이진트리

이진트리 순회

이진트리 순회에는 크게 4가지가 있습니다.

1. 전위 순회 (Pre-order Traversal)

  노드 → 왼쪽 → 오른쪽

2. 중위 순회 (In-order Traversal)

  왼쪽 → 노드 → 오른쪽

3. 후위 순회 (Post-order Traversal)

  왼쪽 → 오른쪽 → 노드

4. 레벨 순회 (Level-order Traversal)

  같은 깊이의 노드들을 왼쪽에서 오른쪽으로 순회

 

이진트리 순회 구현

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int data;
    Node left, right;

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

class BinaryTree {
    Node root;

    // 노드 삽입 메서드
    public void insert(int data) {
        root = insertRecursively(root, data);
    }

    private Node insertRecursively(Node current, int data) {
        if (current == null) {
            return new Node(data);
        }
        if (data < current.data) {
            current.left = insertRecursively(current.left, data);
        } else if (data > current.data) {
            current.right = insertRecursively(current.right, data);
        }
        return current;
    }

    // **전위 순회 (Pre-order Traversal)**
    public void preOrderTraversal() {
        preOrderRecursively(root);
        System.out.println(); // 줄바꿈
    }

    private void preOrderRecursively(Node node) {
        if (node != null) {
            System.out.print(node.data + " "); // 현재 노드 출력
            preOrderRecursively(node.left);  // 왼쪽 서브트리
            preOrderRecursively(node.right); // 오른쪽 서브트리
        }
    }

    // **중위 순회 (In-order Traversal)**
    public void inOrderTraversal() {
        inOrderRecursively(root);
        System.out.println(); // 줄바꿈
    }

    private void inOrderRecursively(Node node) {
        if (node != null) {
            inOrderRecursively(node.left);  // 왼쪽 서브트리
            System.out.print(node.data + " "); // 현재 노드 출력
            inOrderRecursively(node.right); // 오른쪽 서브트리
        }
    }

    // **후위 순회 (Post-order Traversal)**
    public void postOrderTraversal() {
        postOrderRecursively(root);
        System.out.println(); // 줄바꿈
    }

    private void postOrderRecursively(Node node) {
        if (node != null) {
            postOrderRecursively(node.left);  // 왼쪽 서브트리
            postOrderRecursively(node.right); // 오른쪽 서브트리
            System.out.print(node.data + " "); // 현재 노드 출력
        }
    }

    // **레벨 순회 (Level-order Traversal)**
    public void levelOrderTraversal() {
        if (root == null) return;

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

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            System.out.print(current.data + " ");

            if (current.left != null) queue.add(current.left); // 왼쪽 자식 추가
            if (current.right != null) queue.add(current.right); // 오른쪽 자식 추가
        }
        System.out.println(); // 줄바꿈
    }
}

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

        // 데이터를 삽입하여 트리 생성
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(3);
        tree.insert(7);
        tree.insert(12);
        tree.insert(18);

        // 순회 출력
        System.out.println("Pre-order Traversal:");
        tree.preOrderTraversal(); // 출력: 10 5 3 7 15 12 18

        System.out.println("In-order Traversal:");
        tree.inOrderTraversal(); // 출력: 3 5 7 10 12 15 18

        System.out.println("Post-order Traversal:");
        tree.postOrderTraversal(); // 출력: 3 7 5 12 18 15 10

        System.out.println("Level-order Traversal:");
        tree.levelOrderTraversal(); // 출력: 10 5 15 3 7 12 18
    }
}