[자료구조] 이진트리

 

🌳 이진 트리(Binary Tree)란?

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 계층적 자료구조.
자식 노드는 보통 왼쪽과 오른쪽으로 구분된다.

 

트리의 기본용어

 

• 노드(Node): 데이터를 저장하는 기본 단위
• 루트(Root): 트리의 최상위 노드
• 자식(Child): 특정 노드의 하위 노드
• 부모(Parent): 자식 노드의 상위 노드
• 리프(Leaf): 자식이 없는 노드
• 서브트리(Subtree): 특정 노드와 그 하위 트리

 

 

이진트리의 특징

 

• 자식 노드의 수: 최대 2개 (0~2)
• 재귀적 구조: 트리의 하위 구조도 트리 형태
• 균형도(Balance): 노드의 배치가 성능에 영향을 미침

 

이진 트리의 종류

1. 포화 이진 트리(Full Binary Tree)
   • 모든 노드가 0개 또는 2개의 자식을 가짐
   • 리프 노드는 동일한 깊이에 위치
2. 완전 이진 트리(Complete Binary Tree)
   • 마지막 레벨을 제외하고 모든 레벨이 꽉 찬 트리
   • 마지막 레벨은 왼쪽부터 채워짐
3. 편향 이진 트리(Skewed Binary Tree)
   • 한쪽 방향(왼쪽 또는 오른쪽)으로만 노드가 추가된 트리
4. 이진 탐색 트리(Binary Search Tree, BST)
   • 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
   • 빠른 검색, 삽입, 삭제 가능 (O(log n))
5. 균형 이진 트리(Balanced Binary Tree)
   • 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하
   • 예시: AVL 트리, 레드-블랙 트리

 

 

 

아래는 이진탐색트리 구현 후 GUI 추가한 코드

 

실행환경

java 11 이상의 intellij 

 

새프로젝트생성 -> 왼쪽 제너레이터 밑에 javaFX로 생성 후  아래 코드를 실행

 

package com.example.demo;

import javafx.application.Application;
import javafx.geometry.Pos;
import javafx.scene.Scene;
import javafx.scene.canvas.Canvas;
import javafx.scene.canvas.GraphicsContext;
import javafx.scene.control.Button;
import javafx.scene.control.TextField;
import javafx.scene.layout.BorderPane;
import javafx.scene.layout.HBox;
import javafx.scene.paint.Color;
import javafx.stage.Stage;

public class HelloApplication extends Application {

    private Binary root;  // 트리의 루트 노드
    private Canvas canvas;

    public static void main(String[] args) {
        launch(args);
    }

    @Override
    public void start(Stage primaryStage) {
        // 캔버스 생성
        canvas = new Canvas(800, 600);

        // 입력 필드 및 버튼 생성
        TextField inputField = new TextField();
        inputField.setPromptText("숫자 입력");
        Button insertButton = new Button("삽입");
        Button deleteButton = new Button("삭제");

        // 버튼 이벤트
        insertButton.setOnAction(e -> {
            try {
                int value = Integer.parseInt(inputField.getText());
                root = insert(root, value);
                drawTree();  // 트리 그리기
                inputField.clear();
            } catch (NumberFormatException ex) {
                inputField.setText("숫자만 입력");
            }
        });

        deleteButton.setOnAction(e -> {
            try {
                int value = Integer.parseInt(inputField.getText());
                root = delete(root, value);
                drawTree();  // 트리 그리기
                inputField.clear();
            } catch (NumberFormatException ex) {
                inputField.setText("숫자만 입력");
            }
        });

        // 레이아웃 구성
        HBox controls = new HBox(10, inputField, insertButton, deleteButton);
        controls.setAlignment(Pos.CENTER);

        BorderPane rootPane = new BorderPane();
        rootPane.setTop(controls);
        rootPane.setCenter(canvas);

        Scene scene = new Scene(rootPane, 800, 600);
        primaryStage.setTitle("이진 탐색 트리 시각화");
        primaryStage.setScene(scene);
        primaryStage.show();
    }

    // 트리 그리기
    private void drawTree() {
        GraphicsContext gc = canvas.getGraphicsContext2D();
        gc.clearRect(0, 0, canvas.getWidth(), canvas.getHeight());
        drawNode(gc, root, canvas.getWidth() / 2, 50, canvas.getWidth() / 4);
    }

    // 노드 및 연결선 그리기
    private void drawNode(GraphicsContext gc, Binary node, double x, double y, double offset) {
        if (node == null) return;

        gc.setFill(Color.LIGHTBLUE);
        gc.fillOval(x - 15, y - 15, 30, 30);
        gc.setFill(Color.BLACK);
        gc.strokeOval(x - 15, y - 15, 30, 30);
        gc.fillText(String.valueOf(node.value), x - 5, y + 5);

        if (node.left != null) {
            gc.strokeLine(x, y, x - offset, y + 50);
            drawNode(gc, node.left, x - offset, y + 50, offset / 2);
        }

        if (node.right != null) {
            gc.strokeLine(x, y, x + offset, y + 50);
            drawNode(gc, node.right, x + offset, y + 50, offset / 2);
        }
    }

    // 삽입 메서드
    private Binary insert(Binary node, int value) {
        if (node == null) return new Binary(value);
        if (value < node.value) {
            node.left = insert(node.left, value);
        } else if (value > node.value) {
            node.right = insert(node.right, value);
        }
        return node;
    }

    // 삭제 메서드
    private Binary delete(Binary node, int value) {
        if (node == null) return null;

        if (value < node.value) {
            node.left = delete(node.left, value);
        } else if (value > node.value) {
            node.right = delete(node.right, value);
        } else {
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;

            Binary minNode = findMin(node.right);
            node.value = minNode.value;
            node.right = delete(node.right, minNode.value);
        }
        return node;
    }

    // 최소값 찾기
    private Binary findMin(Binary node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // Binary 노드 클래스
    class Binary {
        int value;
        Binary left, right;

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

 

 

실행화면