자바스크립트로 트리(Tree) 구현하기

트리 구조란?

트리(Tree)는 계층적인 구조를 나타내는 비선형 자료 구조이다.

이 구조는 노드(node)와 간선(edge)의 집합으로 이루어져 있다.

트리에서 한 노드는 부모(parent)와 그 자식(child) 노드들로 구성된다.

 

트리 구조에서는 최상위 노드를 루트(root) 노드라고 하고, 각 노드는 그 아래에 여러 자식 노드들을 가질 수 있다.

각 노드는 부모 노드로부터 연결된 간선을 통해 접근할 수 있다.

트리에서 각 노드는 서로 다른 자식을 가질 수 있지만, 각 노드는 하나의 부모를 가진다.

 

 

 

class Tree {
  constructor(value) {
    this.root = new Node(value);
  }
}

class Node {
  children = [];
  constructor(value) {
    this.value = value;
  }

  push(value) {
    this.children.push(new Node(value)); // 새로운 노드를 해당 노드에 추가
  }
}

// 실사용
const tree = new Tree(50);
tree.root.push(25);
tree.root.push(75);
tree.root.children[0].push(12); // 0번 노드에 12를 push
tree.root.children[0].push(37); // ...
tree.root.children[1].push(62); // 1번 노드에 62를 push
tree.root.children[1].push(87); // ...

console.log(tree);
// 결과
//       50
//   25      75
// 12  37  62  87

 

 

그리고 이 트리구조는 이진트리, AVL트리 등 여러 다른 알고리즘에도 기초로 쓰인다.

(둘 중 주로 이진트리가 많이 사용하는 알고리즘이긴 하다.)