자바 - 이진트리구조( binary Tree )

불순분자들·2022년 9월 18일

자바

목록 보기

5/16

이진트리 구조

이진트리( Binary tree )란 모든 노드들이 둘 이하의 자식을 가진 트리이다.

위 그림에서 동그라미를 노드( node )라고 부르면서, 노드는 데이터를 담고 있다.

이진트리는 컴퓨터 응용에서 가장 많이 팔용되는 중요한 트리구조이다.

이진트리의 중요한 점은 왼쪽과 오른쪽의 서브트리를 확실하게 구분한다는 것이고, 모든 노드가 정확하게 두 개의 서브트리를 가지고 있다.

루트 노드( root node ) : 부모가 없는 노드.( 트리는 하나의 루트 노드를 가짐 )
단말 노드( leaf node ) : 자식이 없는 노드.
내부( internal ) 노드 : 단말 노드가 아닌 노드.
간선( edge ) : 노드를 연결하는 선으로 link, branch라고도 함.

이진트리 유형

전 이진트리( Full Binary Tree )

모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리.

완전 이진트리( Complete Binary Tree )

마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리.
마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야한다.

완전 이진트리를 구현할 때, 서브트리가 없다면 각 left, right의 데이터는 null이 된다.

포화 이진트리( Perfect Binary Tree )

포화 이진 트리는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 가진다.

균형 이진트리( Balanced Binary Tree )

왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는 트리이다.

이진트리 구현하기

package binaryTree;

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

    public Node() {

    }

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

    public int getValue() {
        return value;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }
}

package binaryTree;

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

public class BinaryTree {
    private Node root;

    public BinaryTree(Node root) {
        this.root = root;
    }

    public Node getRoot(){
        return root;
    }

    /*
     BFS : 너비 우선 탐색( Breath - First Search )
     루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
     주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용하는 방법이다.
     */
    public void  printByBFS(Node root) {
        Queue<Node> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            Node next = q.poll();
            System.out.println(next.getValue()+ " ");
            if (next.getLeft() != null) {
                q.offer(next.getLeft());
            }
            if (next.getRight() != null) {
                q.offer(next.getRight());
            }
        }
        System.out.println();
    }

    /*
    DFS : 깊이 우선 탐색( DFS, Depth - First Search )
    최대한 깊이 내려간 뒤, 더이상 갈 곳이 없으면 옆으로 이동
    모든 노드를 방문하고자 하는 경우에 이 방법을 사용하며, BFS보다 간단하지만 검색속도는 BFS보다 느린게 특징
     */

    public void printByDFS(Node root) {
        if (root == null) return;

        printByDFS(root.getLeft());
        System.out.println(root.getValue() + " ");
        printByDFS(root.getLeft());
    }
}

테스트 코드

package binaryTree;

import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

@DisplayName("BinaryTree Test")
class BinaryTreeTest {
    Node node10 = new Node(10, null, null);
    Node node9 = new Node(9, null, null);
    Node node8 = new Node(8, node10, null);
    Node node7 = new Node(7, null, node9);
    Node node6 = new Node(6, node8, null);
    Node node5 = new Node(5, null, null);
    Node node4 = new Node(4, node7, null);
    Node node3 = new Node(3, node5, node6);
    Node node2 = new Node(2, node4, null);
    Node node1 = new Node(1, node2, node3);

    BinaryTree binaryTree = new BinaryTree(node1);
    Node root = binaryTree.getRoot();

    @Test
    void printByBFS() {
        System.out.println("root : " + root.getValue());
        System.out.println();
        System.out.println("==========BFS==========");
        binaryTree.printByBFS(root);
    }

    @Test
    void printByDFS() {
        System.out.println();
        System.out.println("==========DFS==========");
        binaryTree.printByDFS(root);
    }
}