[Data Structure] Tree

트리(Tree)는 노드로 구성된 계층적 자료구조이다. 트리 구조는 최상위 노드(Root)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 구현할 수 있다. HTML의 DOM 구조와 같다.

이미지 출처: codestates urclass

용어 정리

• 노드(Node): A, B, C, D 등 트리의 구성요소
• 루트(Root): A처럼 트리 구조에서 최상위에 존재하는 노드
• 노드의 깊이(Depth): 루트를 기준으로, 다른 노드로 접근하기 위한 거리(루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수), D의 깊이는 2
• 형제(Sibling): 같은 부모를 가지면서 같은 depth에 존재하는 노드들
• 부모, 자식(Parent, Child): A는 B와 C의 부모이고, B와 C는 A의 자식임
• 간선(Edge): 노드와 노드를 잇는 선
• 단말 노드(Leaf): 자식이 없는 노드
• 트리의 차수(degree of tree): 각 노드가 가진 간선의 수
• 트리의 높이(height): 루트를 기준으로 가장 아래에 있는 노드의 깊이, 위 그림에선 3

Tree vs. Graph

	Tree	Graph
경로	트리는 그래프의 특별한 형태로 두 개의 노드 사이에는 1개의 경로만 있음	1개 이상의 경로가 존재하며 노드 사이에 일방향, 양방향 경로가 있음
루트	한 개의 루트 노드만 존재하며, 모든 자식노드는 하나의 부모노드만 가짐	루트 노드라는 개념이 존재하지 않음
순회	전위순회(Pre-Order), 중위순회(In-Order), 후위순회(Post-Order)로 이루어지며, 3가지 모두 DFS/BFS 알고리즘이 존재	DFS 또는 BFS로 순회
종류	이진트리, 이진탐색트리, AVL트리, 힙(Heaps)	방향 그래프, 무방향 그래프
간선 개수	노드(정점)개수 - 1	그래프에 따라 다름
모델	계층 모델	네트워크 모델

출처: http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/ 내용 정리

JS 코드 구현

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
//트리에 노드를 추가
  insertNode(value) {
    let node = new TreeNode(value);
    this.children.push(node);
  }

//트리에 해당 노드가 존재하는지 여부를 반환
  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;
  }
}