java 이진트리(Binary Tree) 탐색 풀이

간단한 외주를 받게돼서 만들었던건데 tree 공부하기 좋아보여서 포스팅한다.

이진트리 (Binary Tree)

이진트리의 이론은 크게 어렵지않은데 구조 자체가 낯설어서 그런지 어려워하는 사람들이 생각보다 많은 것 같다.
외주를 부탁했던 클라이언트?분도 취준생이었는데 구조 자체를 너무 어려워하더라ㅜㅜ 한 번 이해하면 이래저래 이용하기 편한데..

용어

이진 트리 : 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.
자식 노드(child node) : 하위노드
부모 노드(parent node) : 그 노드를 자식으로 하는 상위노드이다.
형제 노드(sibling node) : 부모가 같은 두 노드이다.
노드의 차수(degree) : 자식의 수이다.
노드의 깊이(depth) : 루트 노드에서 자신까지 가는 경로의 길이이다. 특히, 루트 노드의 깊이는 0이다.
노드의 레벨(level) : 루트 노드에서 자신까지 가는 경로의 길이 더하기 1이다. 특히, 루트 노드의 레벨은 1이다. 간혹 트리의 특정 깊이를 가지는 노드의 집합을 레벨이라고 하기도 한다.

이진트리에 사용하는 용어는 더 많지만 일단 필수적으로 알아야 할 것은 이 정도인 것 같다.

Node.java

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

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

Node의 구조는 간단하다.
node의 값을 저장할 변수(위의 value), left child node, right child node를 저장할 변수(위의 left, right)를 가지고 있어야 한다.
생성자가 2개인 이유는 node 단독 하나만 만들 수도 있지만 자식노드까지 한번에 만들 수 있도록 해봤다. 근데 이진트리 같은 경우에는 원하는 부모노드에 끼워넣는 것이 아니라 순서대로 넣는 것이 통상적이라 사실 위의 생성자만 있어도 무방하다.

BinaryTree.java (add 기능 / BFS, DFS 탐색기능)

코드 참고 https://math-coding.tistory.com/164

import java.util.Queue;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;

public class BinaryTree {

    Node root;

    public BinaryTree() {
        root = null;
    }

    public void add(Node node) {
        if (root == null) { // root node인 경우
            root = node;
        } else {
            Queue<Node> queue = new LinkedList<Node>();
            queue.add(root);

            while (!queue.isEmpty()) {
                Node temp = queue.poll();
                if (temp.left == null) { // head node의 left 값이 비어있으면 추가
                    temp.left = node;
                    break;
                } else { // head의 left 값이 이미 있는 경우, queue에 left 값 추가 (다음 parent node로 사용)
                    queue.add(temp.left);
                }

                if (temp.right == null) {  // head node의 right 값이 비어있으면 추가
                    temp.right = node;
                    break;
                } else { // head의 right 값이 이미 있는 경우, queue에 right 값 추가 (다음 parent node로 사용)
                    queue.add(temp.right);
                }
            }
        }
    }

    public void dfs(Node node) { // 깊이우선탐색 전위순회
        System.out.println(node.value);
        if(node.left != null) dfs(node.left);
        if(node.right != null) dfs(node.right);
    }

    public void bfsPerLevel(Node node, int depth) { // 넓이우선탐색
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(node);

        List<Integer> depthList = new ArrayList<>();
        for(int i=0; i<depth; ++i){
            depthList.add((int)Math.pow(2, i));
        }

        int i=0;
        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            System.out.print(temp.value+" ");
            ++i;
           
            if(depthList.get(0) == i) {
                System.out.println();
                depthList.remove(0);
                i=0;
            }

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

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

add 같은 경우는 순차적으로 위에서부터 빈 공간을 찾아서 node를 넣어주는 거라고 생각하면 된다.

DFS(깊이우선탐색)는 전위순회로 제작하였고, BFS(넓이우선탐색)는 level 별로 확인할 수 있도록 제작했다.
예시를 보면 이해하기 쉬울 것이다.

차례대로 0, 1, 2, 3, 4 를 넣어주면 트리구조는

   		 0
	  1		2
	3	4	5	6

이와 같은 형태가 된다.
이것을 깊이우선탐색 전위순회로 돌리면 0135642, 넓이우선탐색으로 돌리면 0123456이 나온다.

사실 혼자 만들어봤다가 위의 코드 참고링크를 보고 queue를 이용하니 훨씬 효율적이길래 거의 그대로 참고했다.
찾다보니 다른 방법도 여러개 나오는데 queue를 사용하는게 제일 알아보기도 쉽고 효율적으로 보였다.
하나하나 설명하려니 주석이 너무 많아져서 직접 돌려보는걸 추천한다.