2022/05/04) 5. 이진트리 넓이우선탐색 [그래프와 탐색(DFS, BFS(넓이우선))]

1. 넓이우선탐색(BFS)

• BFS는 상태트리를 레벨탐색하며, 최단거리를 구하는 방법론이다.
  • 출발지점에서 한 번만에 갈 수 있는 정점을 보는데, 그 정점이 도착점인지 확인하고, 만약 아닐 시 이제 두 번만에 갈 수 있는 정점을 보고 또 도착점인지 확인한다. 이런식으로 가는 거다.
    1, 2, 3, 4, 5, 6, 7이 출력되도록 한다.![]

• 이해가 확실히 가지 않을 땐, 직접 그림을 그려보자.
  

2. 정답

        <script>
            function solution(){  
                let answer="";
                let queue = [];
                queue.push(1); //root노드
                while(queue.length){
                    let v = queue.shift();
                    answer += v+" ";
                    for(let nv of [v*2, v*2+1]){
                        if(nv > 7) continue;
                        queue.push(nv);
                    }
                }
                return answer;
            }
            console.log(solution());
        </script>