Tree

Tree는 노드로 구성된 계층적 자료구조로 그래프의 한 종류입니다.

• 하나 이상의 루트 노드(최상위 노드)가 있습니다.
• 루트 노드(최상위 노드)는 0개 이상의 자식 노드를 가질 수 있습니다.
• 자식 노드는 루트 노드와 마찬가지로 자손 노드를 가질 수 있고, 계속해서 반복 정의됩니다.

그래프의 한 종류?

Tree는 그래프와 같이 노드(vertex)와 간선(edge)들로 이루어져 있습니다. 그중에 방향성이 존재하는 directed graph이지만 Tree는 Cycle이 존재하지 않는 비순환 그래프의 한 종류입니다.
즉, 방향성이 있는 비순환 그래프입니다.

Tree 간략한 용어 정리

• node : A, B, C, D등 Tree를 구성하는 요소들을 node(vertex)라고 합니다.
• root : 위 그림처럼 최상위에 존재하는 노드를 root라고 합니다.
• depth : 루트를 기준으로 다른 노드에 접근하기 위한 거리를 depth라고 합니다.
• edge : 노드와 노드를 잇는 선을 간선(edge)이라고 합니다.
• leaf : 더 이상 자식이 존재하지 않는 노드를 leaf라고 합니다. (위 그림에서는 H, I, J가 leaf가 됩니다.)
• Siblings : 같은 부모를 가지고 같은 depth를 가진 노드는 Sibling관계를 가지게 됩니다.

Tree 구현

Method

• insertNode : 트리에 노드를 추가합니다.
• contains : 트리에 해당 노드가 존재하는지 여부를 반환합니다.

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

  insertNode(value) {
    const tree = new TreeNode(value);// 새로운 TreeNode를 생성
    this.children.push(tree); // 생성한 TreeNode를 자식 노드에 push
  }

  contains(value) {
    let bool = false;
    if (this.value === value) {//입력받은 value가 존재하면 true를 return
      bool = true;
    } else {
      for (const item of this.children) {
        if (item.contains(value)) { // 재귀를 통해 자식노드에 value가 존재하면 true를 return
          bool = true;
        }
      }
    }
    return bool;
  }
}

module.exports = TreeNode;