[DA] Tree

트리

• 방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조
• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
• 정점이 N개인 트리는 반드시 N-1 개의 간선을 가진다.
• 루트에서 특정 정점으로 가는 경로는 유일하다.

이진 트리

• 이진 트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미한다.
• 완전 이진 트리는 마지막 Level 제외한 모든 정점이 채워져 있는 트리
• 정점 N 개 트리 높이 log N

Array

// 0번 인덱스는 비움
// Left = Index * 2
// Right = Index * 2 + 1
// Parent = floor(Index / 2)
const tree = [undefined, 1, 2, 3, 4, 5, 6];

Linked List

class Tree {
  constructor(node) {
    this.root = node;
  }

  display() {
    const queue = new Queue();
    queue.enqueue(this.root);
    while (queue.size) {
      const currentNode = queue.dequeue();
      console.log(currentNode.value);
      if (currentNode.left) queue.enqueue(currentNode.left);
      if (currentNode.right) queue.enqueue(currentNode.right);
    }
  }
}

const tree = new Tree(new Node(1));
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);