BreadthFirstSearch in Tree - Javascript

트리에서의 너비우선탐색

먼저 깊이우선탐색에 대해서 상기해보면,

1. 트리의 루트 노드 탐색
2. chidren이 있다면?
3. childNode들에 대하여 각각 recursion으로써 탐색 함수를 실행

너비우선탐색은 위와 같이 recursion으로 탐색하게 되면,
현재 탐색하길 원하는 depth를 지정할 수가 없게 된다.
때문에 '큐(queue)'의 개념을 함께 사용하였다.

//기본적인 Tree의 구조이다
var Tree = function(value){
  this.value = value;
  this.children = [];
};

Tree.prototype.BFSelect = function(filter) {
  let result = [];
  let queue = [];
  let nextNode;

  queue.push({
    'depth': 0,
    'node': this
  })
//queue는 이미 탐색이 끝난 노드에 대한 표시 및 저장을 위하여 사용하였다.

  while(queue.length > 0) {
    nextNode = queue.shift()
      //여기서 항상 queue 기준의 맨 앞 값을 nextNode로 선언한다
    //depth가 바뀌어도, 이전에 쌓여있던 queue의 데이터가 튀어나오므로 depth first하게 탐색되진 않는다

    if(nextNode.node.children.length > 0) {
      for(let i = 0; i < nextNode.node.children.length; i++) {
      //chilrenNode들에 대해서 일단 push 해놓으면, 동일 depth 상의 노드들이 queue에 쌓이게 된다.
        queue.push({                        
          'depth': nextNode.depth + 1,
          'node': nextNode.node.children[i]
        })
      }
    }

    if (filter(nextNode.node.value, nextNode.depth)) {
      result.push(nextNode.node.value);
    }
  }
  return result;
};