What's Tree?

그래프의 여러 구조 중 방향그래프의 한 구조로,
하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 트리 구조라 부른다.

특징

• 계층적 자료구조
• 순차적으로 나열시킨 선형 구조가 아니라, 비선형 구조
• 노드(Node)와 간선(Edge)로 구성된 자료구조로, 아래로만 뻗기에 사이클이 없다.

트리 구현

class Tree {
  constructor(value) {
  // constructor로 만든 객체는 트리의 Node(데이터)
    this.value = value; 
    this.children = []; // 자식 노드를 담을 곳
    // {value: 인자로 들어온 값, children: []}
  }

// 트리의 삽입 메서드
// tree의 자식 노드를 생성 한 후에, 노드의 children에 push
  insertNode(value) {
  
    // 값이 어떤 이름으로 만들어지고 어느 위치에 붙어야 할까?
    const childNode = new Tree(value); // 부모와 같은 구조니까 인스턴스를 할당!
    this.children.push(childNode); // childNode를 만들어 children에 붙이기.
  }

// 트리 안에 해당 값이 존재하는지 탐색하는 메서드
  contains(value) {
  // 현재 노드에서 탐색
    if (this.value === value) { 
      return true;
    }
  // 자식노드에서 탐색
    for (let el of this.children) {
      if (el.contains(value)) {
        return true;
      }
    }
  // 전부 탐색했음에도 찾지 못했다면 false 반환.
    return false;
  }
}

트리 활용

대표적인 예제는 컴퓨터의 디렉토리 구조!