JavaScript 트리(Tree)

트리(Tree)

  트리는 방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조를 갖고 있다.

  가장 상위에 존재하는 정점 노드를 루트 노드라 부른다. 각 정점은 노드가 되고 자식이 없는 노드를 Leaf Node라고 한다.

 트리에는 레벨이라는 개념이 존재한다. 레벨은 트리의 루트부터 몇 번째 깊이에 있는 노드인지를 나타낸다. 상위 노드에서 하위 노드로 뻗어나가는 간선의 수를 Degree 또는 차수라고 부른다.

 이런 트리의 특징으로

1. 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
2. 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
3. 루트에서 특정 정점으로 가는 경로는 유일하다.

가장 많이 사용되는 트리는 이진 트리다. 이진 트리는 각 노드에서 최대 2개의 자식 노드를 갖는 트리를 의미한다.

자바스크립트에서 이진 트리 구현하기

 자바스크립트에서 이진 트리를 구현하는 방법은 배열을 사용하는 방법과 연결 리스트를 사용하는 방법이 있다. 연결 리스트를 사용하는 방법에서는 큐(Queue)를 사용한다.
}

배열을 사용해서 이진 트리 구현하기

const tree = {
  undefined,
  9,
  3,8,
  2,5,undefined,7
  undefined, undefined, undefined, 4
}

 배열을 사용하면 간단하게 구현할 수 있다. 첫 번째 요소는 비워두고 첫 번째 요소는 루트 노드로 사용하고 그 밑으로 3, 8을 채우고 만약 레벨에 존재하지 않는 노드는 undefined로 초기화 한다. 여기서 4는 레벨 3에 해당하고 2의 왼쪽, 오른쪽, 5의 왼쪽 노드는 존재하지 않기 때문에 undefined로 설정한다.

0	1	2	3	4	5	6	7	8	9	10	11
0	9	3	8	2	5	undefined	7	undefined	undefined	undefined	4

  여기서 인덱스 곱하기 2를 하면 왼쪽 자식 노드가 되고 거기서 하나를 더하면 오른쪽 자식 노드가 된다. 특정 노드의 자식 노드를 알고 싶다면 인덱스를 2로 나누고 소수점을 버린다.

3([2])의 왼쪽 자식노드는 2([4]) 이고 오른쪽 자식 노드는 5([5])가 된다. 7번 노드의 부모 노드는 [7] / [2] = 8([3])이 된다.

연결 리스트를 사용해서 이진 트리 구현하기

  연결 리스트를 사용해서 이진 트리를 구현려면 연결 리스트로 큐를 사용한다.

연결 리스트로 구현한 큐 --> 연결 리스트

import Queue from "./queue_linkedList.js";

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

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

Tree.prototype.display = function () {
  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);
tree.display();

전위, 중위, 후위 순회를 구현해야 한다 (과제 ㅠ)