Tree implementation

Implementation Tree

Tree 구현을 위한 기본적인 코드가 작성되어 있습니다. Tree 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.

멤버 변수
입력 데이터를 담을 수 있는 value
하위 노드를 저장할 수 있는 Array 타입의 children

메서드
insertNode(value): 입력받은 value를 Tree에 계층적으로 추가할 수 있어야 합니다.
contains(value): 트리에 포함된 데이터를 찾을 수 있어야 합니다.

주의사항
value는 어떠한 값도 들어갈 수 있지만 현재 구현하는 Tree는 숫자로 제한합니다.

Tree implementation(1)

class Tree {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  insertNode(value) {
    const childNode = new Tree(value);
    this.children.push(childNode);
  }

  contains(value) {
    if (this.value === value) {
      return true;
    }
    
    for(let i=0; i<this.children.length; i++){
      if(this.children[i].contains(value))return true
    }
    return false;
  }
}

Tree implementation(2)

class Tree {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  insertNode(value) {
    const childNode = new Tree(value);
    this.children.push(childNode);
  }

  contains(value) {
    if (this.value === value) {
      return true;
    }
    
   const isFound = false;
   this.children.forEach((child)=>{
     if(child.contains(value) isFound = true;
   })
   if(isFound) return true;
   return false;
  }
}

(1)과 (2)의 차이점은 contains 메소드에서 for문을 사용했는지, forEach를 사용했는지 여부이다.

//for 문을 사용한 경우 잘 동작하지만
for(let i=0; i<this.children.length; i++){
  if(this.children[i].contains(value))return true
}
  return false;
}

//forEach를 사용하면 항상 false가 리턴된다
this.children.forEach((child) => {
  if(child.contains(value))return true;
}
  return false;
}

• forEach의 특징 이해하기
  forEach를 쓰다보면 break가 동작하지 않아서 for문으로 바꿔 작성해야하는 경우가 있었는데 이번의 경우도 for문을 사용하면 되고, forEach를 사용하면 제대로 동작하지 않았다.

  • forEach는 return true, return false를 코드블록에 작성해놓더라도 continue된다
  • forEach의 return 값은 undefined이다

• 해결방법

  • for문을 사용할 수도 있다
  • Tree implementation(2)와 같이 forEach 스코프 밖에 하나의 변수(boolean값을 갖는다)를 선언해놓고, 그 변수에 다른 값(boolean)을 할당하면 된다. 그리고 forEach문을 중단시켜 리턴시키지 않고 배열의 요소를 모두 순회한 후 forEach 스코프 밖에서 값을 리턴시켜주면 된다.