🔧변경내용🔨

제목	날짜	내용
발행일	23.04.05

📌들어가기에 앞서

해당 포스트는 Tree를 구현해본 코드입니다.

---

🌈 Implementation Tree

class Tree {
  constructor(value) {
    // constructor로 만든 객체는 트리의 Node가 됩니다.
    this.value = value;
    // 현재 노드의 값
    this.children = [];
    // 현재 노드의 자식 노드를 저장할 배열
  }

  // 트리의 삽입 메서드를 만듭니다.
  insertNode(value) {
    // 값이 어떤 이름으로 만들어지고 어느 위치에 붙는지 떠올리는 것이 중요합니다.
    const childNode = new Tree(value);
    // 새로운 자식 노드를 생성합니다.
    this.children.push(childNode);
    // 새로운 자식 노드를 현재 노드의 children 배열에 추가합니다.
  }

  // 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
  contains(value) {
    if (this.value === value) {
      // 현재 노드의 값이 찾는 값과 일치하면 true를 반환합니다.
      return true;
    }
    for (let i = 0; i < this.children.length; i++) {
      // 현재 노드의 자식 노드들을 순회합니다.
      if (this.children[i].contains(value)) {
        // 자식 노드의 contains 메서드를 재귀적으로 호출하여 값이 있는지 확인합니다.
        return 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; // {value: null, children: Array(5)}
rootNode.contains(5); // false
rootNode.contains(1); // true

---

📚 레퍼런스

[자료구조/알고리즘] Tree 이론 기초