트리 완전 탐색 - BFS, DFS

이진트리 완전 탐색

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

public class BinaryTreeSearch {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        BinaryTree binaryTree = new BinaryTree();

        for (int i = 0; i < N; i++) {
            binaryTree.add(scanner.next());
        }

        binaryTree.bfs();
        System.out.println();
        binaryTree.dfsPreOrder(1);
        System.out.println();
        binaryTree.dfsInOrder(1);
        System.out.println();
        binaryTree.dfsPostOrder(1);
    }

}

class BinaryTree {

    private List<String> binaryTree = new LinkedList<>();
    private int lastIndex;

    public boolean isEmpty() {
        return lastIndex == 0;
    }

    public BinaryTree() {
        binaryTree.add("");
    }

    public void add(String item) {
        binaryTree.add(++lastIndex, item);
    }

    public void remove() {
        binaryTree.remove(lastIndex);
    }

	// 너비우선탐색
    public void bfs() {
        if (isEmpty())  return;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.print(binaryTree.get(current) + " ");

            if (current * 2 <= lastIndex) queue.offer(current * 2);
            if (current * 2 + 1 <= lastIndex) queue.offer(current * 2 + 1);
        }
    }

	// 깊이우선탐색 - 전위 순회
    public void dfsPreOrder(int index) {
        if (index > lastIndex) return;

        System.out.print(binaryTree.get(index) + " ");
        dfsPreOrder(index * 2);
        dfsPreOrder(index * 2 + 1);
    }

	// 깊이우선탐색 - 중위 순회
    public void dfsInOrder(int index) {
        if (index > lastIndex) return;

        dfsInOrder(index * 2);
        System.out.print(binaryTree.get(index) + " ");
        dfsInOrder(index * 2 + 1);
    }

	// 깊이우선탐색 - 후위 순회
    public void dfsPostOrder(int index) {
        if (index > lastIndex) return;

        dfsPostOrder(index * 2);
        dfsPostOrder(index * 2 + 1);
        System.out.print(binaryTree.get(index) + " ");
    }

}