이진트리 순회(너비우선탐색 : 레벨탐색)

level 0 : 1

level 1 : 2, 3

level 2 : 4, 5, 6, 7

왼쪽의 이진트리는 층별로 노드들이 이루어져 있다.

너비우선 탐색, BFS는 층별로 탐색을 한다. 수평적으로 탐색을 하기 때문에 순회 순서를 나타내면, 1-2-3-4-5-6-7 순서로 순회한다. BFS는 큐를 사용하여 탐색한다.

 

 

 

 

 

class Node{
    int data;
    Node lt, rt;
 
    public Node(int root){
        data = root;
        lt = rt = null;
    }
}
 
public class Practice {
    public static Node root;
    public static Queue<Node> q;
    
    public static void BFS(){
        while(!q.isEmpty()){
            int len = q.size();
            for(int i=0; i<len; i++){
                Node cur = q.poll();
                System.out.print(cur.data + " ");
                if(cur.lt!=null) q.offer(cur.lt);
                if(cur.rt!=null) q.offer(cur.rt);
            }
        }
    }
 
    public static void main(String[] args){
        q = new LinkedList<>();
 
        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);
 
        q.offer(root);
        BFS();
    }
}
 

위의 코드에서 변수 len은 층별로 담겨있는 노드의 개수를 뜻한다. 

 

큐를 활용하여 설명하자면, 이진 트리의 최상위에 있는 노드를 먼저 큐에 넣고 시작하게 된다.

최상위 노드를 큐에서 빼낸 뒤 자식 노드가 있는지 검사를 한다. 있다면, 자식 노드들을 넣어준다. 

위의 과정을 큐가 빌 때까지 반복하면 된다.