🌳

[JS] 트리와 이진트리


트리?

트리는 일종의 사이클이 없는 방향 그래프다. 트리는 항상 루트(root)에서 시작되며 부모 노드 밑에 여러 자식 노드가 연결되는 재귀적인 형태를 가진다. 이 형태에서 루트 노드를 제외한 모든 노드는 단 하나의 부모 노드만을 가진다는 속성을 알 수 있다.

이 속성 때문에 트리는 임의의 노드에서 다른 노드로 가는 경로가 유일하고 사이클이 존재하지 않는다는 성질을 가지게 된다.

루트부터 자식 노드들이 이어지며 펼쳐지는 모습이 마치 나무를 연상시켜서 트리라고 하는 것 같다.

트리의 끝에 있는, 자식이 없는 노드를 리프(leaf) 노드라고 하고 나머지는 내부(internal) 노드라고 한다.

현재 노드의 깊이(depth)는 루트에서부터 현재 노드까지 거리, 즉, 연결된 간선의 수를 의미한다. 레벨(level)은 특정 깊이를 가지는 노드의 집합을 의미한다. 트리의 높이(height)는 루트 노드에서 가장 먼 노드까지의 거리를 의미한다.

Binary Tree(이진트리)

이진트리는 트리 중에서도 자식 노드가 최대 두 개인 노드들로 구성된 트리다.

이진트리는 세 가지로 분류할 수 있다.

  1. 포화이진트리(full binary tree): 모든 레벨에서 노드들이 꽉 채워진 이진트리
  2. 완전이진트리(complete binary tree): 마지막 레벨을 제외한 모든 레벨의 노드들이 꽉 채워진 이진트리
  3. 균형이진트리(balanced binary tree): 리프 노드의 깊이 차가 1을 초과하지 않는 이진 트리

Tree Traverse(트리 순회)

트리의 순회는 트리 구조에서 각 노드를 한 번씩만, 체계적인 방법으로 방문하는 과정을 말한다. 트리 순회는 노드를 방문하는 순서에 따라 전위(preorder), 중위(inorder), 후위(postorder)로 나뉜다. 여기서는 이진 트리에서 순회를 작성했지만 다른 모든 트리에서도 일반화할 수 있다.

트리의 각 노드는 아래와 같다.

1class Node {
2 constructor(data) {
3 this.data = data;
4 this.left = null;
5 this.right = null;
6 }
7}
  • Preorder 루트부터 시작해서 노드 -> 왼쪽 -> 오른쪽 순서대로 방문한다. 전위 순회는 깊이 우선 순회라고도 한다.
1/**
2 * @params {Node} root - 트리의 루트
3 * @returns {Array} 방문 순서대로 노드를 넣은 배열
4 */
5const preorder = root => {
6 if(!root) return [];
7 return [root.data].concat(preorder(root.left), preorder(root.right));
8}
  • Inorder 루트부터 시작해서 왼쪽 -> 노드 -> 오른쪽 순서대로 방문한다.
1/**
2 * @params {Node} root - 트리의 루트
3 * @returns {Array} 방문 순서대로 노드를 넣은 배열
4 */
5const inorder = root => {
6 if(!root) return [];
7 return inorder(root.left).concat([root.data], inorder(root.right));
8}
  • Postorder 루트부터 시작해서 왼쪽 -> 오른쪽 -> 노드 순서대로 방문한다.
1/**
2 * @params {Node} root - 트리의 루트
3 * @returns {Array} 방문 순서대로 노드를 넣은 배열
4 */
5const preorder = root => {
6 if(!root) return [];
7 return preorder(root.left).concat(preorder(root.right), [root.data]);
8}

참조:
https://yoongrammer.tistory.com/68
https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/