트리선회 (DFS & BFS)

Written on April 27, 2019

자료구조 중, 트리의 각 노드를 한 번 씩 방문하는 것을 트리 순회(Tree traversal)라고 한다. 아래와 같은 트리 구조에서 방문했던 노드를 재방문 하지 않고 효율적으로 전체 순회를 하기 위해서는 체계적인 알고리즘이 필요하다.

Tree 구조

가장 대표적인 것이 깊이우선탐색(DFS, Depth-first search)과 너비우선탐색(BFS, Breadth-first search)이다.

명칭에서 알 수 있듯이, sibling 노드로 넘어가기 전에 본인 노드의 모든 가능성(depth)을 탐색하는 것이다.

깊이우선탐색

이 방법이라면, 위의 순회는 F → B → A → D → C → E → G → I → H 순으로 진행된다. 즉, 트리노드를 방문해서 값을 확인하고, children이 있는지 확인 후, 있으면 child node 들도 똑같이 값을 확인하고, children 확인하고, 하는 식으로 계속 반복되는 리커젼이 된다.

각 노드를 순회하면서 filter함수 결과값을 리턴하는 DFS 함수를 생성한다고 하면, 아래와같이 구현할 수 있다.

// tree constructor
var Tree = function(value) {
  this.value = value;
  this.children = [];
};

//DFS recursion 함수 생성
Tree.prototype.DFSelect = function(filter) {
  let returnArr = [];
  let depth = 0;
  const DFSFunc = function(node, nodeDepth) {
    if (filter.call(null, node.value, nodeDepth)) {
      returnArr.push(node.value);
    }
    if (node.children.length > 0) {
      for (let i = 0; i < node.children.length; i++) {
        DFSFunc(node.children[i], nodeDepth + 1);
      }
    }
  };

  //실행
  DFSFunc(this, depth);
  return returnArr;
};

반면, 너비우선 탐색은 다음 depth 순으로 순회하는 것이다. depth 1에 있는 모든 노드를 확인하고 depth 2로 넘어가는.

너비우선탐색

즉, 위의 순회는 F → B → G→ A →D → I → C→ E→ H 순으로 진행된다. 이번에는 각 노드에서 children 노드로 바로 넘어가는 것이 아니라, children node를 배열에 넣어 depth별 노드들의 값을 한번에 확인해야한다.

각 노드를 순회하면서 filter함수 결과값을 리턴하는 DFS 함수를 생성한다고 하면, 아래와같이 구현할 수 있다.

//tree constructor
var Tree = function(value) {
  this.value = value;
  this.children = [];
};

Tree.prototype.BFSelect = function(filter) {
  let firstNodeArr = [];
  firstNodeArr.push(this);
  let filteredArr = [];
  let dep = 0;

  //DFS 리커젼 함수
  searchFunc = (nodeArr, depth) => {
    let childNodeArr = [];
    //현재 depth에있는 노드들의 값 확인
    for (let i = 0; i < nodeArr.length; i++) {
      if (filter.call(null, nodeArr[i].value, depth)) {
        filteredArr.push(nodeArr[i].value);
      }
      //depth+1 노드들을 한 배열에 정렬
      if (nodeArr[i].children.length > 0) {
        for (let j = 0; j < nodeArr[i].children.length; j++)
          childNodeArr.push(nodeArr[i].children[j]);
      }
    }
    if (childNodeArr.length === 0) {
      return;
    }
    //depth+1 노드들을 리커전 함수에 적용
    searchFunc(childNodeArr, depth + 1);
  };

  searchFunc(firstNodeArr, dep);
  return filteredArr;
};

👩🏻‍💻 배우는 것을 즐기는 프론트엔드 개발자 입니다
부족한 블로그에 방문해 주셔서 감사합니다 🙇🏻‍♀️

in the process of becoming the best version of myself