[알고리즘] 이진트리탐색 구현하기 - BFS(너비우선탐색)

 

이진트리탐색 구현하기- BFS(너비우선탐색)

 

 

BFS(너비우선탐색)

-bfs는 트리의 각 레벨을 순차적으로 탐색하는 방법이다.

 

 

코드

• Node 클래스 생성
  • 각 node는 값, 왼쪽자식, 오른쪽자식으로 구성되어있음.
• 이진트리탐색(BFS)
  • bfs를 구현하기위해서는 큐를 이용해야 한다.
  • 여기서는 덱을 이용해서 구현했다.

 

class Node {
    int data;
    Node lt,rt;
    public Node(int val) {
        data = val;
        lt=rt=null;
     }
}

public class Main {
    static Node root;
    public static void BFS(Node root){
        Deque<Node> dq = new ArrayDeque<>();
        dq.addFirst(root);
        int L = 0;
        while(!dq.isEmpty()){
            int len = dq.size();
            System.out.print(L + " : ");

            for(int i=0; i<len; i++){
                Node cur = dq.pollLast();
                System.out.print(cur.data + " ");
                if(cur.lt != null) dq.addFirst(cur.lt);
                if(cur.rt != null) dq.addFirst(cur.rt);
            }
            L++;
            System.out.println();
        }
}
public static void main(String[] args){
    root = new Node(1);
    root.lt  = new Node(2);
    root.rt = new Node(3);
    root.lt.lt = new Node(4);
    root.lt.rt = new Node(5);
    root.rt.lt = new Node(6);
    root.rt.rt = new Node(7);

    BFS(root);
    // 1: 1
    // 2: 2 3
    // 3: 3 4 5 6 출력
}