트리

• 방향 그래프의 일종으로 정점을 가르키는 간선이 하나밖에 없는 구조를 가진다.

[자료구조] 트리(Tree)란 - Heee's Development Blog

이진트리

• 각 정점이 최대 2개의 자식을 가지는 트리를 의미한다.

• 정점이 N개인 이진트리는 최악의 경우 높이가 N이 될 수 있다.

• 정점이 N개인 포화 또는 완전 이진트리의 높이는 $logN$ 이다.

• 높이가 h인 포화 이진 트리는 $2^h-1$ 의 정점을 가진다.

• 일반적인 이진 트리를 사용하는 경우는 많지 않다.

  주로 다음과 같은 경우에 응용된다.

  • 이진 탐색 트리
  • 힙
  • AVL 트리
  • 레드 블랙 트리

이진 트리 구현 방법

• 자식의 노드가 2개로 제한되는 트징 때문에, 배열 혹은 요소 링크가 2개 존재하는 연결 리스트로 구현할 수 있다.

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

  class Queue {
    constructor() {
      this.head = null;
      this.tail = null;
      this.size = 0;
    }

    enqueue(newValue) {
      const newNode = new Node(newValue);
      if (this.head === null) {
        this.head = this.tail = newNode;
      } else {
        this.tail.next = newNode;
        this.tail = newNode;
      }
      this.size += 1;
    }

    dequeue() {
      const value = this.head.value;
      this.head = this.head.next;
      this.size -= 1;
      return value;
    }

    peek() {
      return this.head.value;
    }
  }

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(9));
tree.root.left = new Node(3);
tree.root.right = new Node(8);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(7);
tree.root.left.right.right = new Node(4);
console.log(tree.display());