JavaScript로 Tree 구현하고 BFS, DFS로 탐색하기

Tree 구현을 위한 기본적인 코드를 작성해보고, Tree 자료구조의 특성을 이해해보았다.

---

Tree 구현을 위한 기본적인 코드

class Tree {
  constructor(value) {
		// constructor로 만든 객체는 트리의 Node가 된다.
    this.value = value;
    this.children = []; // 자식노드들도 객체형태인데 이 노드들을 담을 배열
  }

// 노드를 삽입하는 메소드
  insertNode(value) {
    const childNode = new Tree(value); //인스턴스 객체(=자식노드) 생성
    this.children.push(childNode); //자식노드를 푸시
  }

  // 트리 안에 해당 값이 포함되어 있는지 확인하는 메소드
  contains(value) {
    if (this.value === value) {
      return true;
    }
		// TODO: 값을 찾을 때까지 children 배열을 순회하며 childNode를 탐색하세요.
    else{
      for(let i=0; i<this.children.length; i++){
        const childNode = this.children[i];
        if (childNode.contains(value)) { //자식노드들이 value를 
          return true;
        }
      }
    }
		// 전부 탐색했음에도 true가 나오지 않는다면 마지막엔 false 반환
    return false;
  }
}

사용 예시를 보면,,,

const rootNode = new Tree(null);

for(let i = 0; i <= 4; i++) {
  if(rootNode.children[i]) {
    rootNode.children[i].insertNode(i)
  }
 rootNode.insertNode(i); 
}
rootNode; // 초반엔 rootNode에 자식 노드들이 한 개도 없으므로 rootNode = {value: null, children: Array(5)}
rootNode.contains(5); //false
rootNode.contains(1); //true

오늘 토이문제에서는 트리를 '클래스 컴포넌트'가 아니라 '함수 컴포넌트'로 구현한 것을 알 수 있었다. 두 방식에 문법적 차이가 조금 있다.

let Node = function (value) {
  this.value = value;
  this.children = [];
};

Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};

Tree BFS 탐색

먼저 tree의 형태가 어떻게 되어져 있는지, 그리고 탐색 순서가 어떻게 되는지를 확인해보기 위하여 아래와 같이 그려보았다

수도코드

//BFS는 queue를 활용한다
//탐색의 대상이 되는 노드를 queue에 넣고 
//그 queue에서 하나가 shift될 때 
//그 shift되는 노드의 자식노드들을 한번 훑어서 빈배열에 담아주고(탐색을 완료했다는 표시와도 같은 것), 
//탐색된 자식노드들을 queue에 모두 넣는다(자식노드들도 탐색해야 하므로)

코드로 구현해보면

let bfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.

  let values = [node.value] //그 값이 들어가고
  let queue = [node] //노드 자체가 들어간다

  while(queue.length!==0){
    let search = queue.shift(); //탐색 시작할 노드 하나 빼서
    for(let i=0; i<search.children.length; i++){ //그 노드의 children 배열을 순회
        values.push(search.children[i].value) //값은 values에 밀어넣고
        queue.push(search.children[i]) //children노드는 또 탐색을 해주기 위해 queue에 넣어준다
    }
  }
  return values;
   
};

Tree DFS 탐색

탐색 순서가 어떻게 되는지를 확인해보기 위하여 아래와 같이 그려보았다

수도코드

//탐색의 대상이 되는 루트 노드의 value를 values라는 배열에 넣고 
//자식노드들을 하나하나 훑기 시작한다(for반복문) 
//훑을 때 values에다가 그 자식노드의 value 값을 concat 해준다.(재귀함수 호출)
//자식노드가 더 이상 없을 때? 바깥 반복문에서 상위노드의 다음 자식노드를 탐색한다. 

코드로 구현해보면

let dfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  
  let values = [node.value] //최상단 노드를 방문도장 찍고
  
  for(let i=0; i<node.children.length; i++){
      values = values.concat(dfs(node.children[i])) 
    //자식노드들을 탐색할 때 재귀함수를 호출하여 하나하나 values에 concat 시킨다!
  }
  return values;

 
};