🔍 Tree

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

데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조로, 아래로만 뻗어나가기 때문에 사이클이 없다.

즉, 사이클이 없는 하나의 연결 그래프라고 할 수 있다.

위의 이미지를 참고해 용어를 살펴보면,

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터

• 루트(Root) : 트리 구조의 시작점이 되는 노드

• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드

• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드

• 리프(Leaf) : 트리 구조의 끝 지점이며 자식 노드가 없는 노드

• 깊이(depth)
  루트~하위 계층의 특정 노드까지의 깊이
  
  ex) root = 0 / Q,R = 1 / A,B,C,D = 2 ...

• 레벨(level)
  같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현할 수 있으며, 같은 레벨에 나란히 있는 노드를 형제노드(Slibling Node)라고 한다.
  
  ex) P = 1 / Q,R = 2 / A,B,C,D = 3 ...
  
  

• 높이(Height)
  리프 노드를 기준으로 루트까지의 높이를 표현할 수 있다.
  
  ex) E,F,G,B,H,I,D = 0 / L,M = 1 / A,C = 2 / Q,R = 3 / P = 4

• 서브 트리
  큰 트리 내부의 트리구조를 갖춘 작은 트리를 의미한다.
  
  ex) (L,E,F,G) / (Q,A,B) / (M,H,I) / (R,C,D) / (R,C,D,M,H,I) / ...

✔ 기본 코드

class Tree {
  constructor(value) {
		// constructor로 만든 객체는 트리의 Node가 된다.
    //tree의 자식 노드들을 children으로 할당하여 노드의 자식 노드들을 담을 수 있게 설정한다.
    this.value = value;
    this.children = [];
  }

	// 트리의 삽입 메서드.
  //tree의 자식 노드를 생성 한 후에, 노드의 children에 push
  insertNode(value) {
    const childNode = new Tree(value);
    this.children.push(childNode);
  }

	// 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드.
  // tree에서 value값을 탐색 -> 현재 노드의 value 값이 찾는 값과 일치한다면 return.
  contains(value) {
    if (this.value === value) {
      return true;
    }

    // 노드가 가진 자식 노드를 순회하는 반복문으로 노드의 children 배열을 탐색
    for (let i = 0; i < this.children.length; i++) {
      const childNode = this.children[i];
      if (childNode.contains(value)) {
        return true;
      }
    }
		// 전부 탐색했음에도 불구하고 찾지 못했다면 false return.
    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

👀 실사용 예시

✔ 컴퓨터의 디렉토리 구조

어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더 또는 다운로드 폴더 등에서 다른 폴더에 진입하고, 그 안에서 또 다른 폴더에 진입하는 식으로 찾는데, 모든 폴더는 루트 폴더/에서 시작되어 가지를 뻗어나가는 형태이다.

• 그 외 월드컵 토너먼트 대진표, 가계도, 조직도 등

Reference: 코드스테이츠